有向图的强连通分量

一 算法步骤

1 深度优先遍历节点，在第一次访问节点x时，将 x 入栈，且 dfn[x]=low[x]=++num

2 遍历 x 的所有邻接点y。

若 y 没被访问，则递归访问 y，返回时更新 low[x]=min(low[x],low[y])

若 y 已被访问且在栈中，则令 low[x]=min(low[x],dfn[y])

3 在x回溯之前，如果判断 low[x]=dfn[x],则从栈中不断弹出节点，直到 x 出栈时停止。弹出的节点就是一个连通分量。

二 举例

1 从节点 1 出发进行深度优先搜索，dfn[1]=low[1]=1,1入栈；

2 遍历1的所有邻接点

2 没有被访问，递归访问 2，2 入栈，返回时，更新 dfn[2]=low[2]=2。

3 回溯时，因为 dfn[2]=low[2],2 出栈，得到强连通分量2。

4 回溯到 1 后，继续访问1的下一个邻接点3，接着访问 3-4-5,5 的邻接点 1 的已经访问，且 1 在栈中，更新low[5]=min(low[5],dfn[1])=1,回溯时更新 low[4]=min(low[4],low[5])=1, low[3]=min(low[3],low[4])=1,low[1]=min(low[1],low[3])=1.节点 1 的所有邻接点都已访问完毕，因为 dfn[1]=low[1],所以开始出栈，直到遇到1，得到强连通分量 5 4 2 1。

三 代码

package graph.tarjanscc;

import java.util.Scanner;
import java.util.Stack;

public class TarjanSCC {
    static final int maxn = 1000 + 5;
    static int n;
    static int m;
    static int head[];
    static int cnt;
    static int root;
    static int low[];
    static int dfn[];
    static int num;
    static Edge e[] = new Edge[maxn << 1];
    static Stack<Integer> s = new Stack<>();
    static boolean ins[] = new boolean[maxn];

    static {
        for (int i = 0; i < e.length; i++) {
            e[i] = new Edge();
        }
    }

    static void add(int u, int v) { // 添加一条边u--v
        e[++cnt].next = head[u];
        e[cnt].to = v;
        head[u] = cnt;
    }

    static void tarjan(int u) { // 求强连通分量
        low[u] = dfn[u] = ++num;
        System.out.println("low[" + "]=" + low[u] + "\tdfn[" + u + "]=" + dfn[u]);
        ins[u] = true;
        s.push(u);
        for (int i = head[u]; i != 0; i = e[i].next) {
            int v = e[i].to;
            if (dfn[v] == 0) {
                tarjan(v);
                low[u] = Math.min(low[u], low[v]);
                System.out.println("update1:low[" + u + "]=" + low[u]);
            } else if (ins[v]) {
                low[u] = Math.min(low[u], dfn[v]);
                System.out.println("update2:low[" + u + "]=" + low[u]);
            }
        }
        if (low[u] == dfn[u]) {
            int v;
            System.out.println("强连通分量：");
            do {
                v = s.peek();
                s.pop();
                System.out.print(v + " ");
                ins[v] = false;
            } while (v != u);
            System.out.println();
        }
    }

    static void init() {
        head = new int[maxn];
        low = new int[maxn];
        dfn = new int[maxn];
        ins = new boolean[maxn];
        cnt = num = 0;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        init();
        int u, v;
        while (m-- > 0) {
            u = scanner.nextInt();
            v = scanner.nextInt();
            add(u, v);
        }
        for (int i = 1; i <= n; i++)
            if (dfn[i] == 0) {
                tarjan(i);
            }
    }
}

class Edge {
    int to;
    int next;
}

四 测试

绿色为输入，白色为输出。