题解 CF1344C 【Quantifier Question】
pzc2004
2020-05-10 18:37:16
# 题目分析
建图+拓扑排序+dfs
先考虑-1的情况，如果存在一个环，那么一定不可以，否则就一定可以，判环可以用拓扑排序。
可以发现，如果 $X_i>X_j$ 或 $X_i<X_j(i<j)$ 那么 $Q_j$ 一定是E。
所以我们建两个图，一个图存正边，一个图存反边。然后从1扫到 $n$，对于当前的点 $i$，我们在正反图上都进行一次dfs，把遍历到的点都标记掉。如果点 $i$ 没有被标记，那么 $Q_i$ 就可以是A。
最后输出即可，复杂度 $O(N)$。
``` cpp
#include<bits/stdc++.h>
using namespace std;
#define N 200005
int n,m,ans,head1[N],head2[N],cnt1,cnt2,rd1[N],q[N],l=1,r,s,mi[N],ma[N];
int c[N],vis1[N],vis2[N];
struct sb//链式前向星存图
{
int a,b;
}e1[N],e2[N];
inline void add1(int a,int b)
{
e1[++cnt1].a=head1[a],e1[cnt1].b=b,head1[a]=cnt1;
}
inline void add2(int a,int b)
{
e2[++cnt2].a=head2[a],e2[cnt2].b=b,head2[a]=cnt2;
}
inline void dfs1(int x)//正图上dfs
{
vis1[x]=1;
for(int i=head1[x];i;i=e1[i].a)
{
if(vis1[e1[i].b])continue;
dfs1(e1[i].b);
}
}
inline void dfs2(int x)//反图上dfs
{
vis2[x]=1;
for(int i=head2[x];i;i=e2[i].a)
{
if(vis2[e2[i].b])continue;
dfs2(e2[i].b);
}
}
signed main()
{
scanf("%d%d",&n,&m);
for(int i=1,a,b;i<=m;i++)scanf("%d%d",&a,&b),add1(a,b),add2(b,a),++rd1[b];//建正反图
for(int i=1;i<=n;i++)//拓扑排序
{
ma[i]=i;
if(rd1[i])continue;
q[++r]=i;
}
while(l<=r)
{
++s;
int x=q[l++];
for(int i=head1[x];i;i=e1[i].a)
{
ma[e1[i].b]=min(ma[e1[i].b],ma[x]);
--rd1[e1[i].b];
if(rd1[e1[i].b]==0)q[++r]=e1[i].b;
}
}
if(s!=n){printf("-1");return 0;}//-1的情况
for(int i=1;i<=n;i++)//从1扫到n
{
if(!vis1[i] && !vis2[i])++ans,c[i]=1;//统计答案
dfs1(i),dfs2(i);//遍历
}
printf("%d\n",ans);
for(int i=1;i<=n;i++)if(c[i])printf("A");else printf("E");
return 0;
}
```