强连通分量 Tarjan：有向图里的环与缩点

这篇来自我补“强连通分量 Tarjan：有向图里的环与缩点”基础时的一次复盘。我之前的问题是：Tarjan 里的时间戳、low 值和栈让我反复看了很多遍，真正的难点是分清返祖边如何把一组节点留在同一个环里。等我把输入、状态变化和边界条件分别写出来之后，原来看似突然出现的规则就有了来路。

强连通分量用于有向图。一个强连通分量内，任意两个点都能互相到达。把每个强连通分量缩成一个点后，原图会变成 DAG，也就是有向无环图。

它从哪里来

Robert Tarjan 在 1972 年发表线性时间强连通分量算法。它用 DFS 序号、low 值和栈识别有向图中互相可达的最大区域，再把这些区域缩成点，复杂依赖关系便能转化为 DAG。

强连通分量是什么

Tarjan 强连通分量

图：圈内节点互相可达，可以缩成一个超级节点

强连通分量适合处理：

有向图环结构分析。
依赖系统中互相依赖的一组模块。
社交网络中的闭环关系。
编译依赖或任务依赖中的循环检测。

Tarjan 的核心变量

Tarjan 算法常用三个结构：

dfn[u]：节点第一次被访问的时间戳。
low[u]：从 u 出发能回到的最早时间戳。
stack：保存当前还没有确定归属的节点。

当 dfn[u] == low[u] 时，u 是一个强连通分量的根，可以从栈中弹出一组节点。

简化代码

class Tarjan {
    List<List<Integer>> graph;
    int[] dfn, low;
    boolean[] inStack;
    Deque<Integer> stack = new ArrayDeque<>();
    int time = 0;
    List<List<Integer>> components = new ArrayList<>();

    void dfs(int u) {
        dfn[u] = low[u] = ++time;
        stack.push(u);
        inStack[u] = true;

        for (int v : graph.get(u)) {
            if (dfn[v] == 0) {
                dfs(v);
                low[u] = Math.min(low[u], low[v]);
            } else if (inStack[v]) {
                low[u] = Math.min(low[u], dfn[v]);
            }
        }

        if (dfn[u] == low[u]) {
            List<Integer> component = new ArrayList<>();
            while (true) {
                int x = stack.pop();
                inStack[x] = false;
                component.add(x);
                if (x == u) break;
            }
            components.add(component);
        }
    }
}

缩点

找到 SCC 后，可以给每个节点分配一个组件编号。原图中如果有边 u -> v，并且 component[u] != component[v]，就在组件图中加一条边。

缩点后的图一定是 DAG。很多复杂有向图问题，可以先缩点，再在 DAG 上做 DP 或拓扑排序。

我的分析

Tarjan 难在 low 的含义。它不是“子树里最小编号”，而是当前节点通过 DFS 树边和返祖边能回到的最早访问时间。理解这句话，比背代码重要。

工程里，如果服务之间出现循环依赖，SCC 思想也很有用：先找出互相依赖的一团，再决定拆模块、打破依赖或合并部署。

面试题

强连通分量和连通分量有什么区别？
dfn 和 low 分别表示什么？
为什么 dfn[u] == low[u] 时可以弹出一个 SCC？
缩点后的图为什么一定是 DAG？
强连通分量在工程依赖分析中有什么价值？