【AtCoder Regular Contest 079 F】Namori Grundy | Mrsrz's blog

构造。

题目大意：

给定一张 $n$ 个点 $n$ 条边的有向图，保证每条边入度为 $1$，保证图弱连通。

现在要给每个点设置权值。一个点的权值定义为它的出边连的点的所有权值的 $\mathrm{mex}$。

问这样的图是否存在。

题解：

最后的图的形态是一棵基环外向树。

对于树点的权值，直接模拟即可，求 $\mathrm{mex}$ 的复杂度是和度数有关的，因此总和为 $n$。

我们已经确定环上每个结点的权值至少是多少了。

接下来考虑有多少种不同情况。

• 环上的权值都相同，且环是偶环。那么每隔一个就令其增加即可。因此有解。
• 环上的权值都相同，且环是奇环。那么无解。
• 环上的权值存在不同。我们找到一个权值最小的点（必须保证严格小于它连向的环上结点），从它开始往后一直加即可。最后绕回来的时候，这个权值最小的点一定不会变化。因此有解。

Code：

#include<cstdio>
#include<queue>
const int N=2e5+5;
int p[N],head[N],cnt,n,deg[N],val[N];
bool vis[N],ur[N];
struct edge{
    int to,nxt;
}e[N];
std::queue<int>q;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",p+i);
        e[++cnt]=(edge){i,head[p[i]]},head[p[i]]=cnt,++deg[p[i]];
    }
    for(int i=1;i<=n;++i)if(!deg[i])q.push(i);
    while(!q.empty()){
        int u=q.front();q.pop();
        vis[u]=1;
        for(int i=head[u];i;i=e[i].nxt)if(vis[e[i].to])
            ur[val[e[i].to]]=1;
        int&v=val[u];
        while(ur[v])++v;
        for(int i=head[u];i;i=e[i].nxt)ur[val[e[i].to]]=0;
        if(!--deg[p[u]])q.push(p[u]);
    }
    int len=0,mn=0;
    for(int u=1;u<=n;++u)if(!vis[u]){
        for(int i=head[u];i;i=e[i].nxt)if(vis[e[i].to])
            ur[val[e[i].to]]=1;
        int&v=val[u];
        while(ur[v])++v;
        for(int i=head[u];i;i=e[i].nxt)ur[val[e[i].to]]=0;
    }
    for(int i=1;i<=n;++i)if(!vis[i]){
        ++len;if(val[p[i]]<val[i])mn=p[i];
    }
    printf("%sPOSSIBLE\n",(len&1)&&!mn?"IM":"");
    return 0;
}