LINK：Quantifier Question
题面过长 引起不适 读题花了好长时间 对于 和 存在符合不是很熟练 导致很懵逼的做完了。
好在还算很好想。不过wa到了一个坑点上面 自闭一大晌 还以为自己思路错了 看了某个强者的blog才知道自己有个地方没处理好。
题目中明确指出 这种关系运算符只能顺序的添加 也就是说 \(\forall x_2\exists x_1\) 这是不能被表达的 只能表达出\(\exists x_1\forall x_2\)
如果有题目中的f函数 那么后者将会被判定为错误的。再次定义 对于x<y 表达为x向y连了一条有向边。
考虑存在环的时候 容易证明是无解的 全是\(\exists\)都不行。
所以接下来考虑 有向无环的图 尝试给每个x赋上一个符号 容易想到 若对于一个较大的数字赋上\(\forall\)
一个显然的事实 两个\(\forall\)不能连在一起。一个显然的事实大的是\(\forall\)小的是\(\exists\)也不行。
而且尽可能多放\(\forall\)所以应该从小到大开始放。
放了一个\(\forall\)之后观察 和这个点相连的前驱和后继 容易发现都不能是\(\forall\) 继续考察 前驱和前驱 和后继的后继 容易想到 都不能放\(\forall\)
而那些点被连向的边则暂时合法 因为还有满足大小关系。
至此 没便利到一个点可以dfs一下前驱和后继 把他们都标记为不合法即可。
值得注意的是 对于标记后继 只能是反图上的后继 前驱同理 所以 如果使用一个vis数组的话 可能之前便利过了前驱 现在需要便利后继 便利不了了 所以需要开两个vis数组。
const int MAXN=200010;
int n,m,ans,len1,len;
int flag=0;
int vis[MAXN],ru[MAXN],vis1[MAXN],q[MAXN],mark[MAXN];
int lin[MAXN],nex[MAXN],ver[MAXN];
int lin1[MAXN],nex1[MAXN],ver1[MAXN];
inline void add(int x,int y)
{
ver[++len]=y;
nex[len]=lin[x];
lin[x]=len;++ru[y];
ver1[++len1]=x;
nex1[len1]=lin1[y];
lin1[y]=len1;
}
inline void topsort()
{
int t=0,h=0;
rep(1,n,i)if(!ru[i])q[++t]=i;
while(h++<t)
{
int x=q[h];
go(x)
{
--ru[tn];
if(!ru[tn])q[++t]=tn;
}
}
rep(1,n,i)if(ru[i])flag=1;
}
inline void dp(int x)
{
vis[x]=1;
go(x)if(!vis[tn])dp(tn);
}
inline void dp1(int x)
{
vis1[x]=1;
for(int i=lin1[x];i;i=nex1[i])
{
int tn=ver1[i];
if(vis1[tn])continue;
dp1(tn);
}
}
int main()
{
freopen("1.in","r",stdin);
get(n);get(m);
rep(1,m,i)
{
int get(x),get(y);
add(x,y);
}
topsort();
if(flag){puts("-1");return 0;}
rep(1,n,j)
{
if(vis[j]||vis1[j]){dp(j);dp1(j);continue;}
dp1(j);dp(j);mark[j]=1;++ans;
}
put(ans);
rep(1,n,i)if(mark[i])putchar('A');
else putchar('E');
return 0;
}