2018-team4-modules-有向图极大强连通分量(Tarjan)

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
//CNT为强连通分量总数
//Gt[i]为编号为i的强连通分量点数
//g[i]为节点i所属的强连通分量编号 

int g[N],Gt[N],dfn[N],low[N],ins[N],tme;
stack<int> sta;

struct Edge{int b,n;}e[M];
void link(int a,int b) {e[++cnt] = (Edge){b,h[a]}, h[a] = cnt;}

void Tarjan(int u) {
    low[u] = dfn[u] = ++tme;
    sta.push(u); ins[u] = 1;
    for (int i=h[u],v;v=e[i].b,i;i=e[i].n) {
        if (!dfn[v]) {
            Tarjan(v);
            low[u] = min(low[v], low[u]);
        } else if (ins[v]) {
            low[u] = min(dfn[v], low[u]);
        }
    }

    if (low[u] == dfn[u]) {
        ++CNT;
        do {
            int x = sta.top(); sta.pop();
            Gt[CNT]++, g[x] = CNT;
        } while (x != u);
    }
    return ;
}

}}}

//CNT为强连通分量总数
//Gt[i]为编号为i的强连通分量点数
//g[i]为节点i所属的强连通分量编号 
int g[N],Gt[N],dfn[N],low[N],ins[N],tme;
stack<int> sta;
struct Edge{int b,n;}e[M];
void link(int a,int b) {e[++cnt] = (Edge){b,h[a]}, h[a] = cnt;}
void Tarjan(int u) {
    low[u] = dfn[u] = ++tme;
    sta.push(u); ins[u] = 1;
    for (int i=h[u],v;v=e[i].b,i;i=e[i].n) {
        if (!dfn[v]) {
            Tarjan(v);
            low[u] = min(low[v], low[u]);
        } else if (ins[v]) {
            low[u] = min(dfn[v], low[u]);
        }
    }
    if (low[u] == dfn[u]) {
        ++CNT;
        do {
            int x = sta.top(); sta.pop();
            Gt[CNT]++, g[x] = CNT;
        } while (x != u);
    }
    return ;
}