杀戮 jantar

Qcfff · 2024-11-27 14:25:21 · 算法·理论

OI Wiki

我根本就不会塔尖。

所以直接背模板吧。

SCC：

void tarjan(int x){
    dfn[x]=++timer;
    low[x]=dfn[x];
    in[x]=true;
    st[++top]=x;
    for(int j=hd[x];j;j=nxt[j]){
        int y=ver[j];
        if(!dfn[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }else{
            if(in[y]){
                low[x]=min(low[x],dfn[y]);
            }
        }
    }
    if(dfn[x]==low[x]){
        int z=-1;
        cnt++;
        while(z!=x){
            z=st[top--];
            col[z]=cnt;
            in[z]=false;
        }
    }
    return;
}

注意：in[x] 代表其是否在栈中。SCC 的判断条件：dfn[x]==low[x]。

e-DCC：

void tarjan(int x,int in){
    dfn[x]=++timer;
    low[x]=dfn[x];
    st[++top]=x;
    for(int j=hd[x];j;j=nxt[j]){
        int y=ver[j];
        if(!dfn[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }else{
            if(j!=(in^1)){
                low[x]=min(low[x],dfn[y]);
            }
        }
    }
    if(dfn[x]==low[x]){
        int z=-1;
        cnt++;
        while(z!=x){
            z=st[top--];
            col[z]=cnt;
        }
    }
    return;
}

注意：记录 in 代表搜索树父亲边。e-DCC 判断条件：dfn[x]==low[x]；割边判断条件：low[y]>dfn[x]。

v-DCC：

void tarjan(int x){
    dfn[x]=++timer;
    low[x]=dfn[x];
    st[++top]=x;
    if(x==root&&(!hd[x])){
        cut[x]=true;
        col[x]=++cnt;
        return;
    }
    int flag=0;
    for(int j=hd[x];j;j=nxt[j]){
        int y=ver[j];
        if(!dfn[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
            if(low[y]>=dfn[x]){
                flag++;
                if(x!=root||flag>=2){
                    cut[x]=true;
                }
                int z=-1;
                cnt++;
                while(z!=y){
                    z=st[top--];
                    col[z]=cnt;
                }
            }else{
                low[x]=min(low[x],dfn[y]);
            }
        }
    }
    return;
}

注意：v-DCC / 割点判断条件：low[y]>=dfn[x]（注意特判割点在根处 !hd[x] 和 ++flag>=2）。

附：v-DCC 对边的染色，考虑把边也塞进栈里，缩点时顺便把边也出栈。