题目描述：
题解：
好多细节，比如说每个点有且仅有一条入边。
所以说这个图一定是一个基环外向树。
考虑只是一个环的情况，我们可以发现，当环长为偶数时我们可以$01$交替染色，但环长为奇数时没有合法方案。
而且不在环上的点的$a$值是可以直接求的。
所以只需要考虑环为奇数的基环树的环上的点。
当环上所有点的$a$值都相同时才会卡死。
代码：
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 200050; template<typename T> inline void read(T&x) { T f = 1,c = 0;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){c=c*10+ch-‘0‘;ch=getchar();} x = f*c; } int n,fa[N],hed[N],cnt; struct EG { int to,nxt; }e[N]; void ae(int f,int t) { e[++cnt].to = t; e[cnt].nxt = hed[f]; hed[f] = cnt; } bool cir[N]; int sta[N],tl; void get_cir() { int u = 1; while(!cir[u])cir[u]=1,u=fa[u]; memset(cir,0,sizeof(cir)); while(!cir[u])sta[++tl]=u,cir[u]=1,u=fa[u]; } int sg[N]; int vis[N],tim; void dfs(int u) { for(int j=hed[u];j;j=e[j].nxt) { int to = e[j].to; if(!cir[to])dfs(to); } tim++; for(int j=hed[u];j;j=e[j].nxt) { int to = e[j].to; if(!cir[to])vis[sg[to]]=tim; } sg[u]=0; while(vis[sg[u]]==tim)sg[u]++; } int main() { read(n); for(int i=1;i<=n;i++) { read(fa[i]); ae(fa[i],i); } get_cir(); int mx = -1,mn = n+1; for(int i=1;i<=tl;i++) dfs(sta[i]),mx=max(mx,sg[sta[i]]),mn=min(mn,sg[sta[i]]); if(mx==mn&&(tl&1))puts("IMPOSSIBLE"); else puts("POSSIBLE"); return 0; }
原文：https://www.cnblogs.com/LiGuanlin1124/p/10804614.html
