那个问一下有人可以解释以下嘛，看不太懂QwQ~

---

Description

有一个n个点n条边的有向图，点的编号为从1到n。

给出一个数组p，表明有（p₁，1），（p₂，2），…，（p_n，n）这n条单向边，这n条边必定构成弱连通图。

每个点均有一个权值a_i，满足以下性质：

（1）所有a_i均为非负整数；

（2）对于任意边（i，j），有a_i≠a_j；

（3）对于任意i，x（0≤x＜a_i），均有（i，j）满足a_j=a_i。

判断这样的图是否存在。（“POSSIBLE”/“IMPOSSIBLE”）

---

Solution

（早上花了三个小时还打挫了，心态爆炸）

弱连通图：若该有向图所有边为双向边时，满足该图为连通图，则该有向图为弱连通图。

我们容易发现，当一个点的出度为0时，它的权值也为0。我们可以对每一条边建反向边，然后进行拓扑排序，每次对新图中入度为0的点求出权值，然后删去。

若最后有剩余的点，由于原图中每个点的入度均为1，则这些点形成一个环，取其中任意一个点开始遍历即可。特别地，若原图n个点构成环，则偶环存在而奇环不存在。

下面讲一下如何求出每个点的权值：

拓扑排序：

若该点在原图中为叶子节点，则权值为0；

若不为叶子节点，则权值为原图子节点权值中未出现的数的最小值。

环：

记录原图中该点不在环上的子节点权值中未出现的数的最小值a与次小值b。若该点权值为a，则下一点无限制；若该点权值为b，则下一点权值必为a。在跑环的时候，注意判断相邻两点权值不相等以及子节点权值满足条件（2）（3）即可。

Code

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 using namespace std;  7 #define next _next  8 struct edge{  9     int to,next; 10 }e[200010],g[200010]; 11 int n,ehead[200010],ghead[200010]; 12 int m=0,a[200010]={
   0},out[200010]={
   0}; 13 int val[200010]; 14 bool vis[200010]={
   false}; 15 queue
          
           q; 16 stack
           
            s[200010]; 17 bool dfs(int u,int w,int cannot){ 18 for(int i=ehead[u];~i;i=e[i].next) 19 if(vis[e[i].to]) 20 s[val[e[i].to]].push(u); 21 int v=-1; 22 for(int i=ehead[u];~i;i=e[i].next) 23 if(!vis[e[i].to]){ 24 v=e[i].to; 25 break; 26 } 27 if(v==-1){ 28 if(w==-1){ 29 for(int i=0;;i++) 30 if(s[i].top()!=u){ 31 val[u]=i; 32 break; 33 } 34 } 35 else{ 36 val[u]=w; 37 for(int i=0;i
            
             -1) 61 break; 62 flag=i; 63 } 64 for(int i=ehead[u];~i;i=e[i].next) 65 if(vis[e[i].to]) 66 s[val[e[i].to]].pop(); 67 return ret; 68 } 69 int flag=-1; 70 for(int i=0;i
             
              -1){ 73 for(int i=ehead[u];~i;i=e[i].next) 74 if(vis[e[i].to]) 75 s[val[e[i].to]].pop(); 76 return false; 77 } 78 flag=i; 79 } 80 bool ret=(w!=cannot&&s[w].top()!=u&&dfs(v,flag,val[u]=w)); 81 for(int i=ehead[u];~i;i=e[i].next) 82 if(vis[e[i].to]) 83 s[val[e[i].to]].pop(); 84 return ret; 85 } 86 int main(){ 87 memset(ehead,-1,sizeof(ehead)); 88 memset(ghead,-1,sizeof(ghead)); 89 memset(val,-1,sizeof(val)); 90 while(!q.empty())q.pop(); 91 scanf("%d",&n); 92 for(int i=0;i<=n;i++){ 93 while(!s[i].empty()) 94 s[i].pop(); 95 s[i].push(0x3f3f3f3f); 96 } 97 for(int i=1,x;i<=n;i++){ 98 scanf("%d",&x); 99 e[i]=(edge){i,ehead[x]};100 g[i]=(edge){x,ghead[i]};101 ehead[x]=ghead[i]=i;102 a[x]++;out[x]++;103 }104 for(int i=1;i<=n;i++)105 if(out[i]==0){106 vis[i]=true;107 q.push(i);108 }109 while(!q.empty()){110 int u=q.front();111 q.pop();m++;112 for(int i=ehead[u];~i;i=e[i].next)113 s[val[e[i].to]].push(u);114 for(int i=0;;i++)115 if(s[i].top()!=u){116 val[u]=i;117 break;118 }119 for(int i=ehead[u];~i;i=e[i].next)120 s[val[e[i].to]].pop();121 for(int i=ghead[u];~i;i=g[i].next)122 out[g[i].to]--;123 for(int i=ghead[u];~i;i=g[i].next)124 if(out[g[i].to]==0){125 vis[g[i].to]=true;126 q.push(g[i].to);127 }128 }129 if(m==n){130 puts("POSSIBLE");131 return 0;132 }133 if(m==0){134 puts(n&1?"IMPOSSIBLE":"POSSIBLE");135 return 0;136 }137 for(int i=1;i<=n;i++)138 if(!vis[i]){139 puts(dfs(i,-1,-1)?"POSSIBLE":"IMPOSSIBLE");140 return 0;141 }142 return 0;143 }
             
            
           
          
         
        
       
      
     

（话说环套树的题是真的烦[○･｀Д´･ ○]）