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

从 Trac 迁移的文章

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

原文章内容如下：

{{{
//x[i]：反向图的后序遍历 
//CNT：强连通分量总数 
//g[i]：记录i点所在强连通分量的编号
//Gt[i]：记录编号为i的强连通分量的点数 
struct Edge{int b,n;}e[N];
int vis[N],x[N],h[N],g[N],Gt[N],t[N],tp,CNT;

void link(int a,int b) {e[++cnt] = (Edge){b,h[a]}, h[a] = cnt;}
//将边反向 
void edgerev() {
    for (int i=1;i<=n;i++) t[i] = h[i], h[i] = 0;
    for (int u=1;u<=n;u++)
        for (int i=t[u],v,w;i;i=w) {
            v=e[i].b, w=e[i].n;
            e[i] = (Edge){u,h[v]}, h[v] = i;
        }
}

void dfs0(int u) {
    vis[u] = 1;
    for (int i=h[u],v;v=e[i].b,i;i=e[i].n)
        if (!vis[v]) dfs0(v);
    x[++tp] = u; 
}

void dfs1(int u) {
    vis[u] = 1;
    for (int i=h[u],v;v=e[i].b,i;i=e[i].n)
        if (!vis[v]) dfs1(v);
    g[u] = CNT, Gt[CNT]++;
}

void solve() {
    tp = cnt = CNT = 0;

    edgerev();
    for (int i=1;i<=n;i++) vis[i] = 0;
    for (int i=1;i<=n;i++) if (!vis[i]) dfs0(i);

    edgerev();
    for (int i=1;i<=n;i++) vis[i] = 0;
    for (int i=n;i>=1;i--) if (!vis[x[i]]) ++CNT, dfs1(x[i]);
}
}}}

//x[i]：反向图的后序遍历 
//CNT：强连通分量总数 
//g[i]：记录i点所在强连通分量的编号
//Gt[i]：记录编号为i的强连通分量的点数 
struct Edge{int b,n;}e[N];
int vis[N],x[N],h[N],g[N],Gt[N],t[N],tp,CNT;
void link(int a,int b) {e[++cnt] = (Edge){b,h[a]}, h[a] = cnt;}
//将边反向 
void edgerev() {
    for (int i=1;i<=n;i++) t[i] = h[i], h[i] = 0;
    for (int u=1;u<=n;u++)
        for (int i=t[u],v,w;i;i=w) {
            v=e[i].b, w=e[i].n;
            e[i] = (Edge){u,h[v]}, h[v] = i;
        }
}
void dfs0(int u) {
    vis[u] = 1;
    for (int i=h[u],v;v=e[i].b,i;i=e[i].n)
        if (!vis[v]) dfs0(v);
    x[++tp] = u; 
}
void dfs1(int u) {
    vis[u] = 1;
    for (int i=h[u],v;v=e[i].b,i;i=e[i].n)
        if (!vis[v]) dfs1(v);
    g[u] = CNT, Gt[CNT]++;
}
void solve() {
    tp = cnt = CNT = 0;
    edgerev();
    for (int i=1;i<=n;i++) vis[i] = 0;
    for (int i=1;i<=n;i++) if (!vis[i]) dfs0(i);
    edgerev();
    for (int i=1;i<=n;i++) vis[i] = 0;
    for (int i=n;i>=1;i--) if (!vis[x[i]]) ++CNT, dfs1(x[i]);
}