那个问一下有人可以解释以下这个做法嘛，看不太懂QwQ~
Description
有一个n个点n条边的有向图，点的编号为从1到n。
给出一个数组p，表明有（p，1），（p，2），…，（p，n）这n条单向边，这n条边必定构成弱连通图。
每个点均有一个权值a，满足以下性质：
（1）所有a均为非负整数；
（2）对于任意边（i，j），有a≠a；
（3）对于任意i，x（0≤x＜a），均有（i，j）满足a=a。
判断这样的图是否存在。（“POSSIBLE”/“IMPOSSIBLE”）
Solution
（早上花了三个小时还打挫了，心态爆炸）
弱连通图：若该有向图所有边为双向边时，满足该图为连通图，则该有向图为弱连通图。
我们容易发现，当一个点的出度为0时，它的权值也为0。我们可以对每一条边建反向边，然后进行拓扑排序，每次对新图中入度为0的点求出权值，然后删去。
若最后有剩余的点，由于原图中每个点的入度均为1，则这些点形成一个环，取其中任意一个点开始遍历即可。特别地，若原图n个点构成环，则偶环存在而奇环不存在。
下面讲一下如何求出每个点的权值：
拓扑排序：
若该点在原图中为叶子节点，则权值为0；
若不为叶子节点，则权值为原图子节点权值中未出现的数的最小值。
环：
记录原图中该点不在环上的子节点权值中未出现的数的最小值a与次小值b。若该点权值为a，则下一点无限制；若该点权值为b，则下一点权值必为a。在跑环的时候，注意判断相邻两点权值不相等以及子节点权值满足条件（2）（3）即可。
Code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;
#define next _next
struct edge{
int to,next;
}e[],g[];
int n,ehead[],ghead[];
int m=,a[]={},out[]={};
int val[];
bool vis[]={false};
queue<int>q;
stack<int>s[];
bool dfs(int u,int w,int cannot){
for(int i=ehead[u];~i;i=e[i].next)
if(vis[e[i].to])
s[val[e[i].to]].push(u);
int v=-;
for(int i=ehead[u];~i;i=e[i].next)
if(!vis[e[i].to]){
v=e[i].to;
break;
}
if(v==-){
if(w==-){
for(int i=;;i++)
if(s[i].top()!=u){
val[u]=i;
break;
}
}
else{
val[u]=w;
for(int i=;i<w;i++)
if(s[i].top()!=u){
for(int i=ehead[u];~i;i=e[i].next)
if(vis[e[i].to])
s[val[e[i].to]].pop();
return false;
}
}
bool ret=(val[u]!=cannot&&s[val[u]].top()!=u);
for(int i=ehead[u];~i;i=e[i].next)
if(vis[e[i].to])
s[val[e[i].to]].pop();
return ret;
}
if(w==-){
int flag=-;
bool ret=false;
for(int i=;;i++)
if(s[i].top()!=u){
vis[u]=true;
if(i!=cannot)
ret|=dfs(v,flag,val[u]=i);
vis[u]=false;
if(flag>-)
break;
flag=i;
}
for(int i=ehead[u];~i;i=e[i].next)
if(vis[e[i].to])
s[val[e[i].to]].pop();
return ret;
}
int flag=-;
for(int i=;i<w;i++)
if(s[i].top()!=u){
if(flag>-){
for(int i=ehead[u];~i;i=e[i].next)
if(vis[e[i].to])
s[val[e[i].to]].pop();
return false;
}
flag=i;
}
bool ret=(w!=cannot&&s[w].top()!=u&&dfs(v,flag,val[u]=w));
for(int i=ehead[u];~i;i=e[i].next)
if(vis[e[i].to])
s[val[e[i].to]].pop();
return ret;
}
int main(){
memset(ehead,-,sizeof(ehead));
memset(ghead,-,sizeof(ghead));
memset(val,-,sizeof(val));
while(!q.empty())q.pop();
scanf("%d",&n);
for(int i=;i<=n;i++){
while(!s[i].empty())
s[i].pop();
s[i].push(0x3f3f3f3f);
}
for(int i=,x;i<=n;i++){
scanf("%d",&x);
e[i]=(edge){i,ehead[x]};
g[i]=(edge){x,ghead[i]};
ehead[x]=ghead[i]=i;
a[x]++;out[x]++;
}
for(int i=;i<=n;i++)
if(out[i]==){
vis[i]=true;
q.push(i);
}
while(!q.empty()){
int u=q.front();
q.pop();m++;
for(int i=ehead[u];~i;i=e[i].next)
s[val[e[i].to]].push(u);
for(int i=;;i++)
if(s[i].top()!=u){
val[u]=i;
break;
}
for(int i=ehead[u];~i;i=e[i].next)
s[val[e[i].to]].pop();
for(int i=ghead[u];~i;i=g[i].next)
out[g[i].to]--;
for(int i=ghead[u];~i;i=g[i].next)
if(out[g[i].to]==){
vis[g[i].to]=true;
q.push(g[i].to);
}
}
if(m==n){
puts("POSSIBLE");
return ;
}
if(m==){
puts(n&?"IMPOSSIBLE":"POSSIBLE");
return ;
}
for(int i=;i<=n;i++)
if(!vis[i]){
puts(dfs(i,-,-)?"POSSIBLE":"IMPOSSIBLE");
return ;
}
return ;
}
（话说环套树的题是真的烦[○･｀Д´･ ○]）