【agc004f】Namori Grundy

那個問一下有人可以解釋以下這個做法嘛，看不太懂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

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;
#define next _next
struct edge{
    int to,next;
}e[200010],g[200010];
int n,ehead[200010],ghead[200010];
int m=0,a[200010]={0},out[200010]={0};
int val[200010];
bool vis[200010]={false};
queue<int>q;
stack<int>s[200010];
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=-1;
    for(int i=ehead[u];~i;i=e[i].next)
        if(!vis[e[i].to]){
            v=e[i].to;
            break;
        }
    if(v==-1){
        if(w==-1){
            for(int i=0;;i++)
                if(s[i].top()!=u){
                    val[u]=i;
                    break;
                }
        }
        else{
            val[u]=w;
            for(int i=0;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==-1){
        int flag=-1;
        bool ret=false;
        for(int i=0;;i++)
            if(s[i].top()!=u){
                vis[u]=true;
                if(i!=cannot)
                    ret|=dfs(v,flag,val[u]=i);
                vis[u]=false;
                if(flag>-1)
                    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=-1;
    for(int i=0;i<w;i++)
        if(s[i].top()!=u){
            if(flag>-1){
                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,-1,sizeof(ehead));
    memset(ghead,-1,sizeof(ghead));
    memset(val,-1,sizeof(val));
    while(!q.empty())q.pop();
    scanf("%d",&n);
    for(int i=0;i<=n;i++){
        while(!s[i].empty())
            s[i].pop();
        s[i].push(0x3f3f3f3f);
    }
    for(int i=1,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=1;i<=n;i++)
        if(out[i]==0){
            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=0;;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]==0){
                vis[g[i].to]=true;
                q.push(g[i].to);
            }
    }
    if(m==n){
        puts("POSSIBLE");
        return 0;
    }
    if(m==0){
        puts(n&1?"IMPOSSIBLE":"POSSIBLE");
        return 0;
    }
    for(int i=1;i<=n;i++)
        if(!vis[i]){
            puts(dfs(i,-1,-1)?"POSSIBLE":"IMPOSSIBLE");
            return 0;
        }
    return 0;
}

（話說環套樹的題是真的煩[○･｀Д′･ ○]）