图系列第 13 篇：强连通分量——Kosaraju 与 Tarjan

嘿，朋友，欢迎回到图系列。这是第 13 篇，我们要攻克图论里一座非常有名的堡垒——强连通分量（Strongly Connected Component，简称 SCC）。

先说说为什么值得专门用一整篇来写它。前面几篇我们处理的大多是“从某个点出发能到哪里”的问题：BFS 管最短步数，DFS 管遍历与连通块，Dijkstra 管非负权最短路，Floyd 管全源最短路。这些问题都默认图是一张静态的地图，我们只关心路径本身。可是现实中很多图是有向的，而且有向图里最扎心的一件事是：A 能走到 B，B 却不一定能走回 A。单向的路，让“连通”这个词变得暧昧起来。

强连通分量就是来回答这个问题的：在一张有向图里，哪些顶点两两之间可以互相到达？这些互相可达的顶点聚在一起，就形成了一个个“铁打的小团体”。把小团体各自缩成一个点之后，整张复杂的图会瞬间变成一张简洁的有向无环图（DAG），而 DAG 上我们已经有了拓扑排序、动态规划等一整套趁手的工具。换句话说，强连通分量是很多难题的第一步“化简手术”。

本篇的主角是两位算法大神：Kosaraju 和 Tarjan。Kosaraju 的套路是“两次 DFS”，简单直白，正确性有一个非常漂亮的观察；Tarjan 则是“一次 DFS”搞定，用 dfn 和 low 两个时间戳在递归返回的路上切出一个个分量，常数更小、实现更精妙。两套思路都值得吃透，因为它们在很多高级算法里会不断借尸还魂。

在出发之前，先把前置知识对齐一遍。图系列第 2 篇讲过有向图、路径、环和连通性，里面明确区分过“可达”和“互相可达”的差别：可达是单向的，互相可达是双向的；第 5 篇讲 DFS 时引入了发现时间、完成时间（时间戳）和 DFS 树，还预告过“强连通分量”是 DFS 的招牌应用之一。今天这两个前置知识会像齿轮一样咬合在一起：Kosaraju 靠“完成时间”排序，Tarjan 靠“发现时间”做标尺。如果你对时间戳的印象已经模糊，别担心，本篇会在用到的地方重新讲一遍。

下面这张图就是本篇的知识地图：

flowchart LR
    P2["图系列第 2 篇：路径、环与连通性"] --> SCC["强连通分量 SCC"]
    P5["图系列第 5 篇：DFS 与时间戳"] --> SCC
    SCC --> K["Kosaraju：两次 DFS"]
    SCC --> T["Tarjan：一次 DFS"]
    K --> DAG["缩点成 DAG"]
    T --> DAG
    DAG --> APP["环检测 / 拓扑 / 最长路 / 2-SAT"]

第 1 章 回顾：有向图里“互相可达”才是真兄弟

1.1 单向可达与互相可达

我们先从日常直觉说起。假设你在一座单向通行的城市里，A 点有一条单向路通向 B 点，那么从 A 出发你确实能到达 B；但如果 B 点没有路可以回到 A，那么对 B 来说，A 只是一个“路过的地方”，而不是“兄弟”。在无向图里，有一条边就代表两边都能走，连通就是连通，谁也不欠谁；可在有向图里，每条边都带着方向，情况立刻分裂成了四种：

1. A 能到 B，B 也能到 A：双向互通，这是最强的连接；
2. A 能到 B，B 到不了 A：A 单方面指向 B；
3. A 到不了 B，B 能到 A：B 单方面指向 A；
4. A 到不了 B，B 也到不了 A：互不相干。

只有第一种情况，我们才说 A 和 B 是互相可达的。注意，“互相可达”并不要求 A 和 B 之间有一条直接的边，中间绕多少圈都行，只要存在一条从 A 到 B 的路径，同时也存在一条从 B 到 A 的路径。路径可以很长、可以穿过其他顶点，甚至路径之间共享顶点也没关系，关键是“去”和“回”都成立。

下面这个小例子可以帮你建立手感：

flowchart LR
    A((A)) --> B((B))
    B --> C((C))

这张图里，A 能到 B，B 能到 C，所以 A 也能到 C；但是 C 没有任何出边，C 到不了 A 也到不了 B，B 也到不了 A。于是整张图里没有任何一对顶点是互相可达的，A、B、C 各自孤零零地构成一个“只有一个成员”的强连通分量。别看这个例子简单，它说明了一件很重要的事：路径存在只代表单向连接，不等于强连通。

再看一个稍微复杂一点的例子：

flowchart LR
    A((A)) --> B((B))
    B --> C((C))
    C --> A
    C --> D((D))

这里 A、B、C 构成一个环，环上任意两点都能互相到达：A 到 C 走 A→B→C，C 到 A 走 C→A；所以 A、B、C 是强连通的。D 呢？C 能到 D，但 D 没有任何出边，D 到不了 A、B、C 中的任何一个，所以 D 只能自己成一个分量。注意 D 虽然“挂在”C 的后面，看上去离团体很近，但它永远无法回访，也就永远进不了这个圈子。

1.2 强连通分量的严格定义

现在给出正式定义。给定一张有向图 G = (V, E)，如果顶点 u 和 v 满足“存在从 u 到 v 的路径，且存在从 v 到 u 的路径”，我们就记作 u ↔ v，说 u 和 v 强连通。强连通关系具有三个重要性质：

1. 自反性：任何顶点 u 都可以通过长度为 0 的路径到达自己，所以 u ↔ u 恒成立；
2. 对称性：如果 u ↔ v，那么显然 v ↔ u；
3. 传递性：如果 u ↔ v 且 v ↔ w，那么从 u 出发先走到 v 再走到 w，就得到 u 到 w 的路径；反过来 w 也能先走到 v 再走到 u，所以 u ↔ w。

自反、对称、传递——这正是一个等价关系。等价关系最漂亮的地方在于：它会把整个集合切分成若干个互不重叠的等价类。强连通分量就是这些等价类，每一个等价类内部的顶点两两强连通，而不同等价类之间不存在任何一对互相可达的顶点。

于是我们可以给出等价但更常用的定义：强连通分量是极大的一组顶点，满足分量内任意两个顶点都互相可达。 关键词是“极大”：你不能再往这个集合里塞进任何一个顶点，同时仍然保持“两两互相可达”的性质。为什么强调极大？因为“任意两点互相可达”这个性质本身是单调的——如果一小组顶点满足它，那么把它们并入一个更大的、也满足它的集合，依然成立；极大性保证了划分是唯一的，不会出现“A、B 是一组，B、C 又是一组”这种重叠的糊涂账。

一个很容易犯的错觉是把“强连通分量”理解成“有环的顶点集合”。环确实会产生强连通分量，但分量不一定要呈一个简单环的形状，它可以是任意复杂的子图，只要内部两两互通。比如四个人之间互相发消息，形成一张密密麻麻的网络，其中可能同时存在十几个不同的环，但所有人依然属于同一个强连通分量。

1.3 和无向图连通分量的区别

无向图里也有“连通分量”，很多初学者会把两者搞混。这里用一张表把差别钉死：

对比项	无向图连通分量	有向图强连通分量
判断标准	任意两点之间存在路径即可	任意两点之间存在双向路径
边的方向	无所谓，边天然双向	方向是关键，单向不算数
一个分量内部	任意两点可达	任意两点互相可达
分量的样子	通常用 BFS/DFS 一碰就出来	需要专门的算法（本篇主角）
缩点之后	得到的是森林	得到的是 DAG

无向图的连通分量，随便挑一个起点做一次 DFS 就能全部圈出来；有向图不行，因为 DFS 只能告诉你“从起点能到哪”，回答不了“谁能回到起点”。这正是 SCC 算法比无向图连通分量算法难一个档次的原因——我们不仅要问“我能走到谁”，还要问“谁和我能互相走到”。

1.4 贯穿全文的运行示例

为了把两个算法都讲透，本篇固定使用同一张图。它有 8 个顶点，我们故意把它设计成 3 个强连通分量 + 3 条跨分量边：

• 分量 X：A、B、C，边 A→B、B→C、C→A；
• 分量 Y：D、E，边 D→E、E→D；
• 分量 Z：F、G、H，边 F→G、G→H、H→F；
• 跨分量边：C→D、E→F、C→G。

整张图画出来长这样（三个虚线框就是三个 SCC）：

flowchart LR
    subgraph X["SCC1：A、B、C"]
        A((A)) --> B((B))
        B --> C((C))
        C --> A
    end
    subgraph Y["SCC2：D、E"]
        D((D)) --> E((E))
        E --> D
    end
    subgraph Z["SCC3：F、G、H"]
        F((F)) --> G((G))
        G --> H((H))
        H --> F
    end
    C --> D
    C --> G
    E --> F

请先自己验证一下这三个集合确实是“极大”的：C 虽然能到 D，但 D 回不到 C（D→E→F→G→H→F，再没有别的路了），所以 D 进不了 X；E 能到 F，但 F 回不到 E（F→G→H→F 是个死循环），所以 F 进不了 Y。这样一来，每个分量都无法再吸收新成员，恰好构成三个 SCC。后面 Kosaraju 和 Tarjan 的所有走查，都会在这张图上进行，你可以随时回头对照。

1.5 几个容易踩的坑

在正式写算法之前，先把常见误区清一遍。第一，强连通分量是“点集”，不是“边集”。我们划分的是顶点，边只是用来判断可达性的工具。第二，单点也是一个合法的 SCC。任何顶点都能通过零长度路径到达自己，所以即使它没有任何边，也自成一分量；这意味着无论图多稀疏，每个顶点都一定属于某个 SCC，不存在“无家可归”的顶点。第三，强连通分量和弱连通分量不是一回事。把有向图的所有边都当成无向边来看，得到的连通块叫弱连通分量；一张有向图可能只有一个弱连通分量，却同时有几十个强连通分量。第四，强连通分量要求的是“路径”而不是“边”，中间经过别的分量完全合法，所以分量之间可以有复杂的穿越关系，不影响分量内部的判定。

理解到这里，你已经掌握了 SCC 的定义。但定义只是第一步——给定一张几百万顶点的图，怎么高效地把所有 SCC 找出来？下一章先解决一个更深刻的问题：找出来之后，这张图会变成什么样？答案是：一张 DAG。

第 2 章 缩点：把每个 SCC 变成一个“整体”

2.1 什么是缩点

假设我们已经通过某种方法拿到了图的所有强连通分量。接下来最自然的操作就是缩点（condensation）：把每一个 SCC 里的所有顶点合并成一个新的“超顶点”，然后保留分量之间的边。具体规则是：对于原图中的每一条边 u→v，如果 u 和 v 属于同一个 SCC，这条边就变成了超顶点内部的自环，缩点后通常直接丢弃；如果 u 和 v 属于不同的 SCC，就在这两个 SCC 对应的超顶点之间保留一条有向边。

缩点之后得到的图叫作缩点图（condensation graph）。对我们的运行示例来说，三个 SCC 缩成三个超顶点 X、Y、Z，跨分量的三条边 C→D、C→G、E→F 分别变成 X→Y、X→Z、Y→Z，于是缩点图长这样：

flowchart LR
    X["X：A、B、C"] --> Y["Y：D、E"]
    X --> Z["Z：F、G、H"]
    Y --> Z

原来 8 个顶点、11 条边的图，一下子变成 3 个顶点、3 条边的图。如果原图有几百万个顶点、几千万条边，而强连通分量又比较“大块”，缩点后的图往往小得让人惊喜。更重要的是，缩点后丢失的只是“分量内部”的信息，而“分量之间怎么流动”的信息一条不少。

2.2 为什么缩点图一定是 DAG

这是本章最核心的定理：任意有向图的缩点图都是无环的，也就是 DAG。 证明用反证法，非常干净。

假设缩点图里存在一个有向环，环上的超顶点依次是 C₁ → C₂ → … → Cₖ → C₁，其中 k ≥ 2（k = 1 的自环已经被我们丢弃，因为自环只可能来自同一 SCC 内部的边）。按照缩点图的构造，C₁ 到 C₂ 有边，意味着原图里存在某个顶点 a₁ ∈ C₁ 和某个顶点 b₂ ∈ C₂，满足 a₁ → b₂。又因为 C₁ 是 SCC，C₁ 内部任意两点互相可达，所以 C₁ 里的任何顶点都能到达 a₁；同理，C₂ 是 SCC，b₂ 能到达 C₂ 里的任何顶点。

现在把环上的边首尾相接：从 C₁ 的任意顶点出发，可以到达 a₁，沿边 a₁→b₂ 进入 C₂，再在 C₂ 内部走到下一跳边的起点，继续沿着环走……如此一圈走下来，C₁ 的任意顶点都能到达 Cₖ 里的某个顶点，再沿最后一条边 Cₖ→C₁ 回到 C₁。这一整条路径把 C₁ 里的任意两个顶点都“缝合”了起来，甚至把 C₁ 和 C₂ 里的顶点也互相可达了——于是 C₁ 和 C₂ 其实应该合并成同一个 SCC，这与“C₁、C₂ 是不同的缩点”矛盾。

更通俗地说：如果两个 SCC 之间有一条“去”的边，又有一条“回”的路径，那么它们本质上就是同一个强连通分量；缩点图里出现环，恰好就等价于出现了这种“去而复返”的路径，而强连通分量的极大性不允许这种情况发生。所以缩点图必然无环。

2.3 缩点为什么有用

缩点图的 DAG 性质，让一堆原本棘手的问题变得豁然开朗。这里说四个层面的用处，后面第 6 章还会展开讲。

第一，语义上的“降维”。 强连通分量内部，任意两点互相可达，所以从外部看，分量内部谁是谁并不重要：只要有一条边进入这个分量，就能到达分量内所有顶点；只要有一条边离开这个分量，分量内任意顶点都能沿内部路径走到出口。于是 SCC 完全配得上“整体”二字——它们可以被当成一个原子单位来处理，就像编译原理里把一组互相依赖的函数看成一个模块一样。

第二，拓扑排序成为可能。 上一篇我们讲过拓扑排序要求图必须无环，而任意一张有向图都可能带环，没法直接拓扑排序。缩点之后问题消失了：缩点图是 DAG，必然存在拓扑序。于是“对任意有向图做拓扑分析”这件事，就规约为“先求 SCC，再对缩点图排序”。

第三，动态规划获得合法顺序。 DAG 上可以按拓扑序做动态规划：算状态、传依赖、求最长路，都不会出现循环依赖。原图里只要存在环，DP 的“先算依赖、再算自己”就无从谈起；缩点之后，依赖关系变成了严格的偏序，一切都顺理成章。

第四，信息无损的简化。 缩点图保留了分量之间的全部边关系，只是把内部结构打包了。很多图论问题的答案（比如可达性、最长路、最小反馈边集）在缩点图上计算，再映射回原图，结果完全一致。所以缩点不是“近似”，而是“等价变形”。

2.4 一个必须记住的视角：缩点图的拓扑序与 SCC 的“先后”

第 3 章讲 Kosaraju 时会反复用到缩点图，所以现在先建立一个关键视角。缩点图是 DAG，DAG 里有的 SCC 只有出边没有入边，称为源点分量；有的 SCC 只有入边没有出边，称为汇点分量。在缩点图里沿着有向边走，信息只能从源点流向汇点，绝不可能逆流而上。

再结合第 5 篇的时间戳知识：如果在原图上做一次 DFS，每个 SCC 里的顶点会得到各自的完成时间。把每个 SCC 的“最晚完成时间”挑出来，可以证明一个非常漂亮的规律——在缩点图里，如果有边 C → C′，那么 C 的“最晚完成时间”一定大于 C′ 的“最晚完成时间”。直觉是：DFS 一旦从 C 进入 C′，C′ 的所有顶点都会在 C 的顶点之前完成，所以“先被访问的那一侧”反而完成得更晚。

这个规律是 Kosaraju 的灵魂。本章先把它种下，下一章我们就会看到：完成时间如何像一把尺子，把 SCC 一个接一个地“从后往前”量出来。

2.5 缩点的代码视角

在实际工程里，缩点通常不需要真的新建一张图。求出每个顶点所属的 SCC 编号之后，我们只需要把原图扫一遍：对于每条边 u→v，如果 belong[u] ≠ belong[v]，就在缩点图上添加一条 belong[u] → belong[v] 的边。重复边无所谓，加一个去重集合或者接受重复都行。这一扫是 O(V + E) 的，相比求 SCC 本身的开销可以忽略不计。

缩点完成之后，原问题就切换到了一个新的战场：一张干干净净的 DAG。到这一步，我们手里已经握着“手术刀”了，但还缺“显微镜”——怎么高效地把 SCC 找出来？第 3 章先看最直觉的方案：Kosaraju，两次 DFS。

第 3 章 Kosaraju：两次 DFS，一次排序

3.1 整体思路：把“找分量”拆成两个子问题

Kosaraju 算法由印度计算机科学家 S. Rao Kosaraju 提出（1978 年，但直到 1981 年才被 Sharir 独立重新发现并发表，所以有时也叫 Kosaraju–Sharir 算法），它大概是所有 SCC 算法里最容易理解的一个。核心思想只有一句话：第一次 DFS 负责排序，第二次 DFS 负责切分。

为什么需要排序？因为单独一次 DFS 只能回答“从某个起点能到达哪些顶点”，而这个集合可能横跨好几个 SCC。我们真正想要的是：一次 DFS 恰好落在一个 SCC 内部，不串门。Kosaraju 的聪明之处在于，它先用完成时间给所有顶点排出一个“先后次序”，然后在反图上按这个次序逐个发起 DFS——神奇的是，这样每次 DFS 访问到的顶点恰好组成一个 SCC，一个不多，一个不少。

整个过程只有四步：

1. 在原图 G 上做一次 DFS，每当一个顶点完成访问（即它的所有邻居都处理完、即将回溯）时，把它记入一个列表；
2. 构造反图 Gᵀ（把所有边的方向反转）；
3. 按“完成时间从晚到早”的顺序遍历顶点，也就是倒着扫第 1 步得到的列表；
4. 在反图上从当前顶点发起 DFS，这次 DFS 访问到的所有顶点构成一个 SCC；全部访问完后，换下一个未访问顶点继续。

下面这张流程图把四步串起来：

flowchart TD
    S["原图 G"] --> P1["第一步：原图 DFS，记录完成顺序"]
    S --> P2["第二步：构造反图 Gᵀ"]
    P1 --> P3["第三步：按完成时间逆序遍历顶点"]
    P2 --> P4["第四步：在反图上 DFS，切出一个 SCC"]
    P3 --> P4
    P4 --> Q{"还有未访问顶点？"}
    Q -- "有" --> P3
    Q -- "没有" --> DONE["所有 SCC 已找到"]

3.2 第一步：原图 DFS 记录完成顺序

先回顾第 5 篇的时间戳体系。DFS 进入一个顶点时给它一个发现时间（discover time，也叫 dfn），离开一个顶点、也就是它的整棵 DFS 子树都处理完时，给它一个完成时间（finish time）。Kosaraju 用到的只是完成时间，而且不关心绝对数值，只关心先后顺序，所以我们用一个数组（或者栈）在顶点“完成”的瞬间把它记录下来即可。

对我们的运行示例，假设 DFS 从 A 出发，并且每个顶点的邻接表按照字母顺序访问。DFS 的过程是这样的：A 出发走到 B，B 走到 C，C 依次尝试 A（已访问）、D、G；从 D 走到 E，E 尝试 D（已访问）、F；从 F 走到 G（已访问），等等。我们关心的不是中途怎么绕，而是谁先“完工”。按上面的访问顺序，H 是最先完工的，然后是 G、F、E、D、C、B，最后才是 A。把完成顺序写下来就是：

完成次序	1	2	3	4	5	6	7	8
顶点	H	G	F	E	D	C	B	A

注意一个反直觉的规律：A 是最先被发现的，却最后才完成。这就是 DFS 的“后进先出”气质——最先进入的调用栈最深，也最后返回。把完成顺序倒过来看，我们得到逆序：A、B、C、D、E、F、G、H。这个逆序正是第 2 章提到的那个漂亮规律在起作用：A、B、C 所在的 SCC X 是缩点图的源点，它的“最晚完成时间”最大，所以在逆序里排最前。

下面这张图把完成时间标在了顶点旁边，方便你对照：

flowchart LR
    A["A（完成：8）"] --> B["B（完成：7）"]
    B --> C["C（完成：6）"]
    C --> A
    C --> D["D（完成：5）"]
    D --> E["E（完成：4）"]
    E --> D
    E --> F["F（完成：3）"]
    F --> G["G（完成：2）"]
    G --> H["H（完成：1）"]
    H --> F
    C --> G

请务必亲手把这张图走一遍：从 A 出发，按 A→B→C→D→E→F→G→H 的路径钻到底，再逐层回溯，你会发现 H 确实第一个“完工”。如果你在自己的实现里得到不同的完成顺序，别慌，那通常只是邻接表顺序不同导致的，Kosaraju 的正确性不依赖具体顺序，任何合法的 DFS 完成顺序都可以。

3.3 第二步：反图按完成时间逆序 DFS

接下来是整篇最“魔法”的一步。我们把原图所有边的方向反转，得到反图（reverse graph / transpose graph）Gᵀ：原图有一条 u→v，反图就有一条 v→u。反图的作用是让“回头路”变成“去路”：原图里 v 能回到 u 当且仅当反图里 u 能走到 v。换句话说，反图上的可达性，正好是原图可达性的镜像。

我们的运行示例的反图如下：

flowchart LR
    B["B"] --> A["A"]
    C["C"] --> B
    A --> C
    D["D"] --> C
    D --> E["E"]
    E --> D
    F["F"] --> E
    F --> H["H"]
    G["G"] --> F
    G --> C
    H --> G

请你先自己确认几件事：原图里 C→D，反图里就变成 D→C；原图里 E→F，反图里变成 F→E；原图里 C→G，反图里变成 G→C。整张图完全“掉了个头”。

第二步的操作是：按照完成时间的逆序（A、B、C、D、E、F、G、H）逐个检查顶点，如果某个顶点在反图上还没有被访问过，就从它开始对反图做一次 DFS；每轮 DFS 覆盖到的顶点集合，就是原图的一个 SCC。

我们来剧透一下结果：

1. 从 A 开始在反图上 DFS：访问到 A、B、C，得到 SCC1 = {A, B, C}；
2. 下一个未访问的是 D，从 D 开始在反图上 DFS：访问到 D、E，得到 SCC2 = {D, E}；
3. 下一个未访问的是 F，从 F 开始在反图上 DFS：访问到 F、G、H，得到 SCC3 = {F, G, H}；
4. 剩下的 G、H 已经被访问过，结束。

和我们在第 1 章手算的三个 SCC 完全一致。你现在一定很好奇：凭什么？凭什么是 A 而不是 H 第一个“切”？为什么反图 DFS 不会像原图 DFS 那样串门？下面就来揭开魔法。

3.4 为什么两次遍历能行：从“源点侧”一个接一个地剥

要理解 Kosaraju，最好的视角是缩点图。把原图缩点后得到 DAG，DAG 里的每个顶点对应一个 SCC，而“完成时间最晚”的 SCC 一定位于缩点图的源点侧：它没有来自其他 SCC 的入边（严格说，是“不存在从别的 SCC 指向它的边”）。为什么？如果存在别的 SCC C′ 有一条边指向 C，那么 DFS 进入 C′ 后必然会顺着这条边进入 C，C 里所有顶点的完成时间都会早于 C′ 里那些尚未完成的部分，于是 C 的“最晚完成时间”不可能比 C′ 大——这和“C 是最晚完成的 SCC”矛盾。所以，完成时间最晚的 SCC 一定“无入边”。

在反图里，事情发生了戏剧性的反转：原图里无入边的 SCC，在反图里变成“无出边”的 SCC。于是，从完成时间最晚的那个顶点出发，在反图上做 DFS，能走到哪里呢？反图的边是原图的回程边，所以反图上从 x 出发能到达 y，等价于原图上 y 能到达 x。x 属于那个无入边的 SCC C，原图里没有任何其他 SCC 能到达 C，因此反图上从 x 出发也走不出 C——所有能“回到”x 的顶点都在 C 内部。第一次反图 DFS 就精确地圈出了 C 这个完整的 SCC。

第一刀切下去之后，把这个 SCC 从图上“拿掉”，剩下的图仍然是一张更小的缩点 DAG，而剩余顶点中完成时间最晚的那个，又变成了剩余 DAG 的“无入边”分量。于是第二轮反图 DFS 又精确地切出第二个 SCC。如此循环，每次都是“从源点侧剥洋葱”，剥完一层，再剥下一层。这就是 Kosaraju 全部正确性的来源：完成时间确定“剥”的顺序，反图保证每次只“剥”出一个完整分量。

让我们把这个直觉用一张图固化下来：原图缩点后是 X→Y→Z 的链条（外加 X→Z 这条直达边），完成时间从晚到早是 X、Y、Z；反图缩点后方向全部反转，变成 Z→Y→X 加 Z→X，于是从 X 出发只能待在 X 里，从 Y 出发只能到达 X（已访问）和 Y，从 Z 出发才能把剩下的都串起来。每一步都严格地“剥”下一个分量：

flowchart LR
    subgraph cut1["第一刀：从 X 出发"]
        X1["X（A、B、C）"]
    end
    subgraph cut2["第二刀：从 Y 出发"]
        Y1["Y（D、E）"]
    end
    subgraph cut3["第三刀：从 Z 出发"]
        Z1["Z（F、G、H）"]
    end
    X1 -.->|"反图里指向 X 的边？没有，剥出 X"| Y1
    Y1 -.->|"反图里指向 Y 的只有 X（已剥掉）"| Z1

如果你喜欢更形式化的表述，关键引理可以写成一句话：设 C 和 C′ 是原图的两个不同 SCC，若缩点图中有边 C→C′，则 C 的“最晚完成时间”大于 C′ 的“最晚完成时间”。 这个引理的证明只需要分两种情形：DFS 先进入 C 还是先进入 C′。先进入 C 时，C′ 的所有顶点都在 C 的内部调用中完成，自然更早；先进入 C′ 时，因为 C′ 没有边到 C，DFS 完成整个 C′ 后才会从外层进入 C，此时 C′ 早已完成，C 的完成时间必然更晚。两种情形下结论都成立。

有了这个引理，Kosaraju 的正确性就水到渠成：逆序完成时间第一个顶点所在的 SCC 在缩点图中没有入边；反图 DFS 从它出发恰好访问它所属的 SCC；把已访问顶点删掉后归纳，每次循环都重复同样的事实，直到全部顶点被划分完毕。

3.5 完整走查：把每一步都摊开

光讲道理还不够，我们用运行示例把两个 DFS 完整走一遍。先明确邻接表（为了可复现，我们规定每个顶点的邻居按字母序访问）：

顶点	邻接表（原图）	邻接表（反图）
A	B	C
B	C	A
C	A, D, G	B
D	E	C, E
E	D, F	D
F	G	E, H
G	H	F, C
H	F	G

第一次 DFS（原图）。 从 A 开始：

1. 访问 A，进入 A 的邻接表；
2. A→B：访问 B，进入 B 的邻接表；
3. B→C：访问 C，进入 C 的邻接表；
4. C→A：A 已访问，跳过；
5. C→D：访问 D，进入 D 的邻接表；
6. D→E：访问 E，进入 E 的邻接表；
7. E→D：已访问，跳过；
8. E→F：访问 F，进入 F 的邻接表；
9. F→G：访问 G，进入 G 的邻接表；
10. G→H：访问 H，进入 H 的邻接表；
11. H→F：已访问，跳过；H 的邻居处理完，H 完成（第 1 个）；
12. 回溯到 G，邻居处理完，G 完成（第 2 个）；
13. 回溯到 F，F 完成（第 3 个）；
14. 回溯到 E，E 完成（第 4 个）；
15. 回溯到 D，D 完成（第 5 个）；
16. 回到 C，继续 C→G：G 已访问，跳过；C 完成（第 6 个）；
17. 回到 B，B 完成（第 7 个）；
18. 回到 A，A 完成（第 8 个）。

完成顺序为 H、G、F、E、D、C、B、A，逆序为 A、B、C、D、E、F、G、H。这一遍的时间复杂度是 O(V + E)，因为我们把每个顶点和每条边都恰好处理了一次。

第二次 DFS（反图，按逆序）。 逆序的第一个顶点是 A。在反图上从 A 出发：

flowchart LR
    subgraph pass1["从 A 出发的 DFS"]
        A1((A)) --> C1((C))
        C1 --> B1((B))
        B1 --> A1
    end
    D1["D"] -.->|"反图 D→C 指向已访问顶点"| C1
    E1["E"] -.-> D1
    F1["F"] -.->|"F→E 指向已访问顶点"| E1
    G1["G"] -.->|"G→C 指向已访问顶点"| C1
    H1["H"] -.-> G1

A 在反图里的邻居只有 C（原图 C→A 的反向边）；访问 C 后，C 的邻居只有 B（原图 B→C 的反向边）；访问 B 后，B 的邻居只有 A，而 A 已经访问过。于是这一刀只访问到 A、B、C，SCC1 = {A, B, C}。为什么没有串到 D？因为反图里从 A、B、C 出发的边只能回到它们自己内部——这正是“原图里没有任何别的 SCC 能到达 X”的镜像。

下一个未访问顶点是 D。从 D 出发在反图上 DFS：

flowchart LR
    subgraph pass2["从 D 出发的 DFS"]
        D2((D)) --> E2((E))
        E2 --> D2
    end
    C2["C（已访问）"] -.->|"D→C 指向已访问顶点"| D2
    F2["F"] -.->|"F→E 指向已访问顶点"| E2

D 在反图里的邻居是 C 和 E：C 已经访问过，跳过；E 未访问，访问 E；E 的邻居只有 D，已经访问过。这一刀圈出 SCC2 = {D, E}。

最后，下一个未访问顶点是 F。从 F 出发在反图上 DFS：

flowchart LR
    subgraph pass3["从 F 出发的 DFS"]
        F3((F)) --> H3((H))
        H3 --> G3((G))
        G3 --> F3
    end
    E3["E（已访问）"] -.->|"F→E 指向已访问顶点"| F3
    C3["C（已访问）"] -.->|"G→C 指向已访问顶点"| G3

F 的反图邻居是 E（已访问）和 H；访问 H 后，H 的邻居是 G；G 的邻居是 F（已访问）和 C（已访问）。这一刀圈出 SCC3 = {F, G, H}。至此所有顶点都访问完毕，算法结束。

注意一个细节：第二刀从 D 出发时，反图里 D→C 明明能走到 C，但 C 已经被第一刀访问过了，所以 DFS 不会把它算进新的分量。这正是“每次剥一个 SCC”的体现：已经剥掉的洋葱层不会再次被碰到。

3.6 Kosaraju 的 JS/TS 实现

实现分三个部分：第一次 DFS 记录完成顺序、构造反图、第二次 DFS 切分量。下面的 TypeScript 版本把三个部分拆成清晰的函数：

type Graph = number[][]; // 邻接表：graph[u] 是 u 的所有出边终点

function kosaraju(n: number, graph: Graph): number[] {
  // 1. 构造反图
  const reverse: Graph = Array.from({ length: n }, () => []);
  for (let u = 0; u < n; u++) {
    for (const v of graph[u]) reverse[v].push(u);
  }

  const visited = new Array<boolean>(n).fill(false);
  const finishOrder: number[] = [];

  // 2. 第一次 DFS：原图，记录完成顺序
  function dfs1(u: number) {
    visited[u] = true;
    for (const v of graph[u]) {
      if (!visited[v]) dfs1(v);
    }
    finishOrder.push(u); // 后序：所有邻居处理完，u 才算完成
  }

  for (let u = 0; u < n; u++) {
    if (!visited[u]) dfs1(u);
  }

  // 3. 第二次 DFS：反图，按完成时间逆序
  const belong = new Array<number>(n).fill(-1);
  let compCount = 0;

  function dfs2(u: number, comp: number) {
    belong[u] = comp;
    for (const v of reverse[u]) {
      if (belong[v] === -1) dfs2(v, comp);
    }
  }

  for (let i = finishOrder.length - 1; i >= 0; i--) {
    const u = finishOrder[i];
    if (belong[u] === -1) {
      dfs2(u, compCount);
      compCount++;
    }
  }

  return belong; // belong[u] 表示顶点 u 所属的 SCC 编号
}

几个实现要点。第一，finishOrder.push(u) 必须放在递归返回之前，也就是后序位置；如果放在进入顶点时（前序），算法立刻失效。第二，第二次 DFS 用的是反图，visited 状态用 belong[u] === -1 代替，省一个数组。第三，递归实现会消耗调用栈，顶点数到十万级、图是一条长链时可能爆栈；工程上可以把 DFS 改成显式栈的迭代版。下面给出迭代版的核心思路：第一次 DFS 用一个栈模拟“进入顶点”和“离开顶点”两个事件，第二次 DFS 用普通栈做显式遍历，代码略长但栈溢出风险归零。

function kosarajuIterative(n: number, graph: Graph): number[] {
  const reverse: Graph = Array.from({ length: n }, () => []);
  for (let u = 0; u < n; u++) {
    for (const v of graph[u]) reverse[v].push(u);
  }

  const state = new Array<number>(n).fill(0); // 0=未访问 1=已进入 2=已完成
  const finishOrder: number[] = [];

  for (let s = 0; s < n; s++) {
    if (state[s] !== 0) continue;
    const stack: Array<[number, number]> = [[s, 0]]; // (顶点, 下一个要访问的邻居下标)
    state[s] = 1;
    while (stack.length > 0) {
      const [u, i] = stack[stack.length - 1];
      if (i < graph[u].length) {
        const v = graph[u][i];
        stack[stack.length - 1][1] = i + 1;
        if (state[v] === 0) {
          state[v] = 1;
          stack.push([v, 0]);
        }
      } else {
        state[u] = 2;
        finishOrder.push(u);
        stack.pop();
      }
    }
  }

  const belong = new Array<number>(n).fill(-1);
  let compCount = 0;
  for (let i = finishOrder.length - 1; i >= 0; i--) {
    const s = finishOrder[i];
    if (belong[s] !== -1) continue;
    const stack = [s];
    belong[s] = compCount;
    while (stack.length > 0) {
      const u = stack.pop()!;
      for (const v of reverse[u]) {
        if (belong[v] === -1) {
          belong[v] = compCount;
          stack.push(v);
        }
      }
    }
    compCount++;
  }

  return belong;
}

两个版本的复杂度完全一样：时间 O(V + E)，空间 O(V + E)。时间上，两次 DFS 各扫一遍全部顶点和边，构造反图又是一遍 O(V + E)；空间上，邻接表、反图、完成顺序数组、belong 数组加起来是 O(V + E)。

Kosaraju 的优点是正确性直观、代码不易写错，缺点是要存一张完整的反图（多一倍边），并且要跑两遍 DFS。如果你觉得“两次遍历”有点奢侈，下一章看看只跑一遍的 Tarjan 是怎么用两个时间戳完成同样壮举的。

3.7 形式化证明：把“直觉”升级成“定理”

如果你打算在面试里讲清楚 Kosaraju，光有直觉还不够，最好能背出下面这条定理链。它由三个引理和一个主定理组成，每一步都简短干净。

引理一：缩点图是 DAG。 第 2 章已经用反证法证明：如果两个 SCC 之间有“去”又有“回”的路径，它们必然合并。所以缩点图中任意两点之间最多只有单向路径，不可能存在环。这个引理是后面一切讨论的舞台。

引理二（完成时间引理）：设 C 和 C′ 是缩点图的两个不同顶点（即两个 SCC），若缩点图中有边 C → C′，则 C 中任意顶点的完成时间都晚于 C′ 中至少一个顶点的完成时间；更精确地说，max{f(v) : v ∈ C} > max{f(v) : v ∈ C′}。 证明分两种情形。情形一：DFS 先进入 C 的某个顶点。由于 DFS 会递归地探索完一条边到达的所有顶点，一旦从 C 进入 C′，C′ 的所有顶点都会在 C 的这次调用结束前完成，因此 C′ 里所有顶点的完成时间都早于 C 里最后一个完成顶点的完成时间。情形二：DFS 先进入 C′。此时 C′ 内部所有顶点都完成后，DFS 才可能从外层进入 C，于是 C′ 所有顶点的完成时间都早于 C 中第一个被访问顶点的完成时间。两种情形都推出 max-finish(C) > max-finish(C′)。

引理三（源点引理）：设 C 是缩点图中 max-finish 最大的 SCC，则 C 在缩点图中没有入边。 反证：如果存在 C′ → C，由引理二，max-finish(C′) > max-finish(C)，与 C 的最大性矛盾。

主定理：第二次 DFS 按完成时间逆序进行时，从当前未访问顶点 u 出发的反图 DFS，恰好访问 u 所在 SCC 的全部顶点。 证明分两步。第一步，“不串门”：设 u 所在 SCC 为 C。由于 C 是当前剩余缩点图中 max-finish 最大的 SCC（归纳假设），C 没有入边；反图中 C 没有出边，所以反图 DFS 从 u 出发永远走不出 C。第二步，“不漏人”：反图 DFS 从 u 出发能到达的顶点，就是原图中能到达 u 的顶点；而 SCC 的定义保证 C 内任意顶点都能到达 u，所以 C 的每个顶点都会被访问。两步合起来，这次反图 DFS 访问的集合恰好等于 C。

主定理的“当前剩余缩点图”需要一句解释：第一轮剥掉 C 之后，剩余 SCC 构成的图依然是 DAG，而剩余顶点中 max-finish 最大的 SCC 在剩余图中依然没有入边（注意引理二只依赖缩点图本身，删掉已访问顶点不会破坏它）。所以归纳可以一路走到底，直到所有顶点被划分完毕。至于孤立顶点和单点 SCC，它们天然满足“没有入边”，在任何一轮都可能被选中，算法对它们一视同仁。

这套证明最妙的地方在于：它没有用到任何“图是连通的”之类的假设。Kosaraju 对不连通图同样成立，因为外层 for 循环会从每个连通部分分别开始 DFS，而完成时间引理在多个 DFS 树之间依然成立（不同的树之间没有边，缩点图中它们互不相连，引理二的两种情形都不会被触发）。

第 4 章 Tarjan：一次 DFS，两个时间戳

4.1 从“剥洋葱”到“现场切分”

Kosaraju 的思路是“先排序、再切分”，把问题拆成两个独立的阶段。Tarjan 算法（Robert Tarjan，1972 年提出）则更激进：在第一次 DFS 的回溯路上，当场把已经完整的 SCC 切出来。它不需要反图，不需要完成时间排序，只需要两个数组和一个栈，却能在一次遍历里完成同样的划分。

为什么“一次”也能行？关键在于 DFS 本身的结构。一次 DFS 会生成一棵 DFS 树，树上的每条边都代表着“发现新顶点”；除此之外，图里还有三类“非树边”：指向祖先的回边、指向后代的前向边、指向另一棵子树顶点的横叉边。在无向图里，回边意味着环；在有向图里，回边和能绕回祖先的路径意味着“某个环的雏形”。强连通分量的本质就是“环的闭包”：一组顶点互相可达，等价于它们可以被若干条路径织成一个整体。Tarjan 的思路是，在 DFS 回溯时不断向上“汇报”自己这棵子树能到达的最浅祖先，一旦发现某个顶点无法再向更浅处汇报，就说明以它为根的那部分已经自成一派，可以整体出栈。

为了实现这个“汇报”机制，Tarjan 维护三样东西：

1. dfn：发现时间，也叫编号。DFS 第几个进入这个顶点，dfn 就是几；
2. low：当前顶点通过“DFS 树内的后代 + 一条非树边”能到达的最浅祖先的 dfn；
3. 栈：存放“还没确定归属”的顶点，也就是当前正在 DFS 栈中、尚未被切进任何 SCC 的顶点。

三个成员各司其职：dfn 是标尺，low 是汇报结果，栈是候选池。下面把每一块都讲透。

4.2 dfn：给每个顶点盖一个“发现章”

dfn 就是第 5 篇里的发现时间，只不过我们不关心绝对时间，只关心相对顺序，所以直接按访问次序编号：第一个访问的顶点 dfn = 1，第二个 dfn = 2，依此类推。dfn 有两个用途：第一，它唯一标识一个顶点在 DFS 树里的“深浅”，dfn 越小表示越靠近树根；第二，它作为 low 的比较基准——low 永远是一个 dfn 值，表示“我能回到的最浅处”。

对我们的运行示例，如果仍然从 A 开始，按 A→B→C→D→E→F→G→H 的顺序访问，那么 dfn 就是：

顶点	A	B	C	D	E	F	G	H
dfn	1	2	3	4	5	6	7	8

这个编号本身没有任何魔法，它就是 DFS 的脚印。真正的魔法在 low 上。

4.3 low：我能“绕”回多浅的地方

low 的定义稍微绕一点，但非常重要：low[u] = min( dfn[u], 所有能从 u 的 DFS 子树内出发、通过一条非树边到达的顶点的 dfn )。翻译成人话：以 u 为根的那棵 DFS 子树里，所有顶点加上它们往外连的“非树边”，最远能把我们“拉回”到哪个祖先？

初始时，u 刚被访问，还没探索任何邻居，所以 low[u] = dfn[u]，意思是一开始只能回到自己。随着 DFS 深入，u 的后代们会陆续汇报它们的 low，u 取最小值作为自己的 low；如果某个邻居是已经访问过、而且还在栈里的顶点（也就是 u 的祖先或者“同一条 DFS 链”上的顶点），u 也可以直接用这个邻居的 dfn 来压低自己的 low。整个计算过程发生在回溯阶段：先递归地访问完所有邻居，回来时再用邻居的 low 更新自己的 low。

这个“汇报”机制可以用一句话概括：low 是子树里所有人共同抬回来的“最低可达 dfn”。子树的根 u 的 low 越低，说明这棵子树和越浅的祖先有联系；如果 low[u] == dfn[u]，说明这棵子树“够不着”任何比 u 更浅的顶点——它已经是一棵完整的、封闭的强连通块了。

4.4 栈：正在“发育”的 SCC 候选池

Tarjan 的栈和 DFS 调用栈不是一回事，但高度相关。每当访问一个新顶点，就把它压入 Tarjan 栈；每当切出一个 SCC，就把栈顶一直到该 SCC 根的顶点全部弹出。栈里始终存放的是“访问过、但还没有确定所属 SCC”的顶点，它们按访问顺序从栈底到栈顶排列。

为什么要用栈来维护？因为 DFS 的调用关系是一层套一层的，如果 u 是 v 的祖先，那么 v 在栈里一定压在 u 上面；而一个 SCC 里的顶点，在 DFS 树里必然是“一串祖先—后代”的连续段落，不会出现“一个 SCC 的顶点在栈里被另一个 SCC 的顶点隔开”的情况。栈的“后进先出”特性刚好能保证：当 low[u] == dfn[u] 时，从栈顶一直弹到 u 为止，弹出的这一整段恰好就是 u 所属的 SCC。

一个关键细节是判断“能不能用邻居的 dfn 更新 low”时，必须先检查邻居是否还在栈里。如果邻居已经访问过、但已经出栈，说明它属于一个已经切好的 SCC，此时即使 u 有一条边指向它，这条边也只是“跨分量边”，不能用来压低 u 的 low。这个检查是 Tarjan 最容易写错的地方，很多 bug 都出在这里。

4.5 三条规则和切分时机

把上面所有内容收拢成算法，Tarjan 对每个顶点 u 只做三件事：

1. 访问 u：dfn[u] = low[u] = 新的时间戳，把 u 压栈；
2. 遍历 u 的每个邻居 v：
   • 如果 v 未访问：递归处理 v，回来后 low[u] = min(low[u], low[v])；
   • 如果 v 已访问且仍在栈中：low[u] = min(low[u], dfn[v])；
   • 如果 v 已访问但已出栈：忽略，这是一条指向已完成 SCC 的边；
3. 全部邻居处理完后，如果 low[u] == dfn[u]：从栈顶一路弹出顶点，直到弹出 u 为止，这些顶点构成一个新的 SCC。

第 3 步是“收获时刻”。为什么 low[u] == dfn[u] 就意味着“可以收割”？因为 u 的整棵子树都汇报过了，它们能到达的最浅处就是 u 自己；换句话说，子树里没有任何一条路径能逃出 u 的势力范围。既然逃不出去，子树中那些和 u 互相可达的顶点只能待在 u 下面，形成一个封闭的圈子；把它们全部弹出，正好是这个圈子的全体成员。

下面这张图把 Tarjan 的完整流程画出来，方便你把它和 Kosaraju 的两阶段流程对比：

flowchart TD
    S["访问 u，dfn[u] = low[u] = 时间戳，u 入栈"] --> N{"遍历 u 的邻居 v"}
    N -->|"v 未访问"| R["递归处理 v"]
    R --> U["low[u] = min(low[u], low[v])"]
    N -->|"v 已访问且仍在栈中"| U2["low[u] = min(low[u], dfn[v])"]
    N -->|"v 已访问且已出栈"| I["忽略"]
    U --> Q{"邻居都处理完了？"}
    U2 --> Q
    I --> Q
    Q -- "没有" --> N
    Q -- "有" --> C{"low[u] == dfn[u]？"}
    C -- "否" --> DONE["返回，把 low[u] 交给父顶点"]
    C -- "是" --> P["弹出栈顶到 u，组成一个 SCC"]
    P --> DONE

如果你读过树系列或者图系列里关于桥、割点的内容，会发现 Tarjan 的 low 思想和它们一脉相承：都是“子树能回到多浅”的度量。桥的判定是 low[v] > dfn[u]，割点是 low[v] ≥ dfn[u]，而 SCC 的判定是 low[u] == dfn[u]——三个判定共用同一套骨架，区别只在“等于、大于、不小于”的细节上。理解了 Tarjan，等于同时复习了一遍连通性问题全家桶。

4.6 完整走查：同一张图，一次 DFS

还是那张 8 顶点的图，还是从 A 出发、邻居按字母序访问。我们一步步跟踪 dfn、low 和栈的变化。下面这张表记录了关键节点（每个顶点“入栈”和“出栈”都单独成行，方便你对照）：

步骤	动作	dfn / low	栈（栈底→栈顶）	说明
1	访问 A	dfn=1, low=1	[A]	入栈
2	访问 B	dfn=2, low=2	[A, B]	入栈
3	访问 C	dfn=3, low=3	[A, B, C]	入栈
4	C→A	low[C]=1	[A, B, C]	A 在栈中，用 dfn[A]=1 压低
5	访问 D	dfn=4, low=4	[A, B, C, D]	入栈
6	访问 E	dfn=5, low=5	[A, B, C, D, E]	入栈
7	E→D	low[E]=4	[A, B, C, D, E]	D 在栈中，用 dfn[D]=4 压低
8	访问 F	dfn=6, low=6	[A, B, C, D, E, F]	入栈
9	访问 G	dfn=7, low=7	[A, B, C, D, E, F, G]	入栈
10	访问 H	dfn=8, low=8	[A, B, C, D, E, F, G, H]	入栈
11	H→F	low[H]=6	[A, B, C, D, E, F, G, H]	F 在栈中，用 dfn[F]=6 压低
12	H 回溯	low[H]=6	同上	6 ≠ 8，不切分
13	G 回溯	low[G]=6	同上	取 H 的 low，7→6
14	F 回溯	low[F]=6	弹出 H、G、F	low[F] == dfn[F] == 6，切出 SCC3
15	E 回溯	low[E]=4	[A, B, C, D, E]	取 F 的 low 仍为 4
16	D 回溯	low[D]=4	弹出 E、D	low[D] == dfn[D] == 4，切出 SCC2
17	C 回溯	low[C]=1	[A, B, C]	取 D 的 low 仍为 1
18	B 回溯	low[B]=1	[A, B, C]	取 C 的 low 仍为 1
19	A 回溯	low[A]=1	弹出 C、B、A	low[A] == dfn[A] == 1，切出 SCC1

注意第 14 步那个瞬间。F 处理完所有邻居后，low[F] 等于 dfn[F] 等于 6，说明 F 的子树（F、G、H）能到达的最浅处就是 F 自己。虽然 H 有一条边指向 F（原图 H→F），但 F 的 dfn 就是 6，这条回边只是把 low 压到 6，压不过 F。于是从栈顶开始弹出 H、G、F，SCC3 = {F, G, H} 诞生。弹出之后，栈变成了 [A, B, C, D, E]，而 D、E 继续留在栈里等待它们自己的“收获时刻”。

我们可以把第 14 步前后的栈状态画出来，你会看到“切分”是如何把栈拦腰截断的：

flowchart LR
    subgraph before["切分前：完整栈"]
        direction TB
        S1["A"] --> S2["B"]
        S2 --> S3["C"]
        S3 --> S4["D"]
        S4 --> S5["E"]
        S5 --> S6["F（low=dfn=6）"]
        S6 --> S7["G"]
        S7 --> S8["H"]
    end
    subgraph after["切分后：弹出 H、G、F"]
        direction TB
        T1["A"] --> T2["B"]
        T2 --> T3["C"]
        T3 --> T4["D"]
        T4 --> T5["E"]
    end

再看第 16 步：D 回溯时，D 的子树只汇报回 low = 4（E 通过回边 D→E 被压到 4，但 D 自己就是 4），所以 low[D] == dfn[D]，从栈顶弹出 E、D，SCC2 = {D, E}。这里有个很容易困惑的点：D 明明有一条反图边 D→C（原图 C→D），为什么不能把 low 压到 1？因为 C→D 是跨分量边，方向是 C 指向 D，D 无法利用它“回到” C；在 DFS 中，C 是 D 的祖先，D→C 这条边根本不存在。Tarjan 里能压低 low 的边只有两种：树边（后代汇报）和指向“栈中祖先”的回边。指向已出栈顶点的边一律忽略，指向栈中但非祖先的横叉边也要小心处理——如果 v 在栈中且 dfn[v] < dfn[u]，说明 v 确实是 u 能绕到的“更浅处”，可以用；如果 v 在栈中但 dfn[v] > dfn[u]，则 v 是 u 的后代，这时用 low[v] 已经涵盖，直接用 dfn[v] 也不会错（因为 dfn[v] ≥ dfn[u]，取 min 无影响）。这就是为什么很多实现里看到“v 在栈中就直接 low[u] = min(low[u], dfn[v])”也正确的原因。

最后看第 19 步：A 是整个 DFS 的根，它的低能回到 1（通过 C→A 这条回边），而 1 正是它自己，所以 low[A] == dfn[A]，把栈里剩下的 C、B、A 全部弹出，SCC1 = {A, B, C}。至此，三次“收获”分别发生在 F、D、A 上，切出的三个 SCC 与 Kosaraju 的结果一模一样，但只做了一次 DFS。

下面这张图把最终每个顶点的 dfn 和 low 标在图上，你可以对照表格逐项检查：

flowchart LR
    A["A<br/>dfn=1, low=1"] --> B["B<br/>dfn=2, low=1"]
    B --> C["C<br/>dfn=3, low=1"]
    C --> A
    C --> D["D<br/>dfn=4, low=4"]
    D --> E["E<br/>dfn=5, low=4"]
    E --> D
    E --> F["F<br/>dfn=6, low=6"]
    F --> G["G<br/>dfn=7, low=6"]
    G --> H["H<br/>dfn=8, low=6"]
    H --> F
    C --> G

注意 low 的三个“阵营”：A、B、C 的 low 都是 1，D、E 的 low 都是 4，F、G、H 的 low 都是 6。每个阵营里恰好有一个顶点 low == dfn（分别是 A、D、F），它们就是三次收获的“切口”。这个规律很漂亮：一个 SCC 的 low 值全部相等，且等于该 SCC 内最早被发现的那个顶点的 dfn；其余顶点在回溯时都不满足 low == dfn，只有那个“根”顶点在最后触发弹出。

4.7 Tarjan 的 JS/TS 实现

Tarjan 的实现比 Kosaraju 紧凑得多，全部状态只需要 dfn、low、栈和“是否在栈中”标记：

function tarjan(n: number, graph: number[][]): number[] {
  const dfn = new Array<number>(n).fill(-1);
  const low = new Array<number>(n).fill(0);
  const inStack = new Array<boolean>(n).fill(false);
  const stack: number[] = [];
  const belong = new Array<number>(n).fill(-1);

  let timer = 0;
  let compCount = 0;

  function dfs(u: number) {
    dfn[u] = low[u] = ++timer;
    stack.push(u);
    inStack[u] = true;

    for (const v of graph[u]) {
      if (dfn[v] === -1) {
        // 树边：先递归，再用子树的 low 更新
        dfs(v);
        low[u] = Math.min(low[u], low[v]);
      } else if (inStack[v]) {
        // v 还在栈中：可能是祖先或同链顶点，用 dfn 压低 low
        low[u] = Math.min(low[u], dfn[v]);
      }
      // v 已出栈：跨分量边，忽略
    }

    if (low[u] === dfn[u]) {
      // 收获：从栈顶弹到 u，组成一个 SCC
      while (true) {
        const w = stack.pop()!;
        inStack[w] = false;
        belong[w] = compCount;
        if (w === u) break;
      }
      compCount++;
    }
  }

  for (let u = 0; u < n; u++) {
    if (dfn[u] === -1) dfs(u);
  }
  return belong;
}

这段代码的骨架只有 25 行左右，比 Kosaraju 短，但每一行的位置都生死攸关。最容易出错的三个地方：一是 low[u] = Math.min(low[u], low[v]) 必须放在递归调用返回之后，不能放在进入递归之前；二是 inStack[v] 的检查不能省，否则会把已切好的 SCC 重新拉进来；三是“收获”时要先标记出栈再判断是否到达 u，顺序颠倒会导致死循环。

和 Kosaraju 一样，递归版在深图上可能爆栈。迭代化稍麻烦一点，因为需要在回溯时执行“更新 low”和“检查 low == dfn”两段逻辑，常见做法是给栈里的帧加一个状态位（进入/离开）。由于核心思想相同，这里不展开完整迭代代码，只提醒一点：如果你需要处理十万甚至百万级的深图，优先选择显式栈版本，或者干脆用 Kosaraju 的迭代版——正确性优先于常数。

Tarjan 的复杂度同样是 O(V + E) 时间、O(V + E) 空间（邻接表 + 三个数组 + 栈），但常数比 Kosaraju 小：不需要反图，不需要第二遍 DFS，数组访问也更紧凑。对于一亿条边的大图，这个常数差异是实打实的。

4.8 Tarjan 的迭代实现：给深图加保险

递归版 Tarjan 好读，但有一个现实风险：DFS 深度等于图的“最深路径长度”，如果一张图有十万个顶点排成一条链，递归调用栈会先于算法崩溃。把递归改写成显式栈需要一点技巧，核心是把“进入顶点”和“离开顶点”两个时刻都压进栈里，用一个状态标记区分。下面给出一个完整可跑的迭代版 TypeScript 实现：

function tarjanIterative(n: number, graph: number[][]): number[] {
  const dfn = new Array<number>(n).fill(-1);
  const low = new Array<number>(n).fill(0);
  const inStack = new Array<boolean>(n).fill(false);
  const stack: number[] = [];
  const belong = new Array<number>(n).fill(-1);

  let timer = 0;
  let compCount = 0;

  for (let s = 0; s < n; s++) {
    if (dfn[s] !== -1) continue;
    // 帧结构：顶点、下一个邻居下标、是否处于“离开”阶段
    const frames: Array<[number, number, boolean]> = [[s, 0, false]];
    dfn[s] = low[s] = ++timer;
    stack.push(s);
    inStack[s] = true;

    while (frames.length > 0) {
      const frame = frames[frames.length - 1];
      const [u, nextIndex, leaving] = frame;

      if (leaving) {
        // 离开阶段：所有邻居已处理，检查是否收获
        if (low[u] === dfn[u]) {
          while (true) {
            const w = stack.pop()!;
            inStack[w] = false;
            belong[w] = compCount;
            if (w === u) break;
          }
          compCount++;
        }
        frames.pop();
        continue;
      }

      if (nextIndex < graph[u].length) {
        const v = graph[u][nextIndex];
        frame[1] = nextIndex + 1;
        if (dfn[v] === -1) {
          // 树边：推进到 v，并登记离开帧
          dfn[v] = low[v] = ++timer;
          stack.push(v);
          inStack[v] = true;
          frame[2] = true; // 先挂起 u 的“离开”
          frames.push([v, 0, false]);
        } else if (inStack[v]) {
          low[u] = Math.min(low[u], dfn[v]);
        }
      } else {
        // 邻居全部处理完：向上汇报 low，然后进入离开阶段
        if (frames.length >= 2) {
          const parent = frames[frames.length - 2][0];
          low[parent] = Math.min(low[parent], low[u]);
        }
        frame[2] = true;
      }
    }
  }
  return belong;
}

这段代码的要点有三个。第一，每个顶点以 [u, i, leaving] 的形式入栈，leaving = false 表示“正在遍历邻居”，leaving = true 表示“邻居都处理完了，该做收尾了”。第二，当发现一个新邻居 v 时，先把当前帧标记为 leaving 再压入 v 的帧，这样 v 返回后，u 的帧会从“离开阶段”继续，而 low 的汇报放在进入离开阶段之前——这正好模拟了递归版里“dfs(v) 返回后 low[u] = min(low[u], low[v])”的时机。第三，parent = frames[frames.length - 2][0] 取得的是显式栈里的上一帧，也就是 DFS 意义上的父顶点；只有父顶点的 low 需要被子顶点的 low 更新，横叉边和回边已经在遍历邻居时处理过了。

迭代版的正确性和递归版完全一致，但它不会爆栈，可以放心处理百万级深度的图。代价是代码长度翻倍、可读性下降，所以很多工程团队的做法是：默认写递归版，只在压测发现爆栈时切换迭代版。如果你用的是支持“增加线程栈大小”的语言（比如 C++ 的 -Wl,--stack 或者给线程分配大栈），也可以继续用递归版，只是要记得把栈容量调大。

4.9 两个算法合体：用 Tarjan 的 dfn/low 反推“谁先谁后”

Tarjan 除了给出 SCC 划分，还附带了一个隐藏福利：SCC 的“发现顺序”天然携带缩点图的拓扑信息。具体来说，Tarjan 弹出分量的顺序，恰好是缩点图逆拓扑序的某种合法实现——先弹出的 SCC 在缩点图中不会指向后弹出的 SCC（否则后弹出的会顺着边访问到先弹出的顶点，从而把它们合并）。因此，如果你在弹栈时给 SCC 从 0 开始编号，编号越小越接近汇点侧；缩点图中的边总是从编号大的 SCC 指向编号小的 SCC。

这个性质在做“缩点后 DP”时非常省事：不需要再单独跑一次拓扑排序，直接从编号 0 到 compCount-1 按序处理，就相当于按拓扑序从汇点往源点递推。很多竞赛选手把这一招当作 Tarjan 的“默认套餐”，缩点、编号、DP 一气呵成。Kosaraju 没有这个福利，它需要再显式地对缩点图做一次拓扑排序。

第 5 章 两个算法面对面：怎么选

5.1 逐项对比

Kosaraju 和 Tarjan 都能在 O(V + E) 时间内求出所有 SCC，时间复杂度完全相同，但在“怎么用掉这些复杂度”上差别很大。下面把关键维度逐项摆出来：

对比项	Kosaraju	Tarjan
遍历次数	两次 DFS	一次 DFS
需要的额外结构	反图（存储反向边）	dfn、low、栈、inStack
空间开销	O(V + E)，反图占大头	O(V)，数组加栈
实现难度	低，思路直白	中，回溯逻辑需仔细
正确性理解成本	低，剥洋葱直觉清晰	中高，low 的含义要反复咀嚼
常数因子	较大（两次遍历 + 反图构建）	较小
迭代化难度	容易（两段独立遍历）	较难（回溯时混合两段逻辑）
依赖 DFS 顺序	不依赖，任意合法顺序都行	不依赖，任意合法顺序都行
额外产出	无	顺手得到 dfn、low，可复用于割点/桥
典型场景	教学、面试手写、工程迭代版	竞赛、性能敏感、需要 dfn/low 的场景

一个常见的误解是“Tarjan 一定比 Kosaraju 快两倍”。实际并不是：两者渐近复杂度相同，Tarjan 只赢在常数，而且赢的幅度取决于图的形态。链状图里 Tarjan 的递归深度很大，栈操作频繁，Kosaraju 的两次遍历也可能因为缓存友好而追平；稠密图里 Tarjan 的数组访问更紧凑，优势才明显。所以“快两倍”是错觉，“常数更小”才是准确的表述。

5.2 什么时候选 Kosaraju

如果你是第一次写 SCC，或者要在面试的十几分钟里把代码完整写对，选 Kosaraju。理由很实在：它的每一步都有独立的含义，第一次 DFS 做排序，第二次 DFS 做切分，写错了一步可以单独调试；反图构造是无脑的双重循环，几乎不可能写错。而且它的迭代版实现简单，面对深图（比如十万个顶点串成一条链）也能轻松改造成显式栈版本，不需要在递归回调里塞状态机。

另一个推荐 Kosaraju 的场景是：你已经有了现成的 DFS 工具函数，只想要“最短的改动”接入。比如在一个大工程里，图以邻接表和反邻接表两种形式同时存在（很多库会同时维护两者），那么 Kosaraju 几乎是零成本的。

5.3 什么时候选 Tarjan

如果你在写竞赛题、做性能敏感的系统、或者图大到“多存一份反图”都心疼，选 Tarjan。它的空间优势在顶点多、边多时尤其明显：Kosaraju 要存反图，边数翻倍，内存可能从“刚好放下”变成“放不下”；Tarjan 只需要几个数组和栈，内存可控。此外，Tarjan 的 dfn 和 low 是“买一送一”的副产品——如果你接下来还要算桥、割点，或者做无向图的边双连通分量，同一套 low 思想直接复用，不用再写一遍。

5.4 一个折中的建议

很多经验丰富的选手会这样搭配：会手写 Kosaraju 保底，性能敏感时用 Tarjan，两者都留一份模板。因为它们的正确性互相独立，当你在一个算法上卡了 bug 时，可以用另一个算法交叉验证结果——两个独立实现输出相同的 SCC 划分，基本可以断定图本身或输入数据出了问题。这种“双算法对拍”的技巧在工程和竞赛里都极其好用。

下面这张决策图可以帮你快速做选择：

flowchart TD
    Q1{"目标是快速写对？"} -- "是" --> K["Kosaraju：两次 DFS + 反图"]
    Q1 -- "否" --> Q2{"内存紧张或图极大？"}
    Q2 -- "是" --> T["Tarjan：一次 DFS"]
    Q2 -- "否" --> Q3{"之后还要算桥/割点？"}
    Q3 -- "是" --> T
    Q3 -- "否" --> K

5.5 别忘了还有第三个算法

除了 Kosaraju 和 Tarjan，图论里还有一个著名的 SCC 算法叫 Gabow 算法，思路与 Tarjan 类似，但用两个栈替代 dfn/low 的比较，实际中较少用到。另外，如果图特别大、无法整张放进内存，还可以用并行的 SCC 算法或者基于 BFS 的 Forward-Backward 算法（从随机顶点出发，正反各做一次 BFS 收缩搜索空间），这些属于工程优化范畴，理解 Kosaraju 和 Tarjan 之后再去读会非常顺畅。

最后说一句选择哲学：算法对比的终点不是“谁赢了”，而是“在什么约束下选谁”。你的图多大、内存多紧、代码要活多久、会不会被改成迭代版、后续还要不要别的连通性信息——这些问题比“Tarjan 常数小 30%”重要得多。

第 6 章 应用：SCC 在真实世界里抓什么

6.1 循环依赖检测：构建系统的“死锁报警器”

先讲一个所有程序员都遇到过的场景。现代构建工具（npm、Maven、Gradle、Webpack、Make 等）都把“模块”和“模块之间的依赖”建模成一张有向图：每个模块是顶点，模块 A 依赖模块 B 就画一条 A→B 的边。构建系统拿到这张图之后，必须按依赖顺序编译：先编译被依赖的模块，再编译依赖它们的模块。

问题来了：如果模块 A 依赖 B，B 又依赖 A，那么“先编译谁”就没有答案——这是一个循环依赖，构建系统会直接报错。更隐蔽的是，循环依赖可能绕一大圈：A 依赖 B，B 依赖 C，C 又依赖 A。肉眼在一万多个模块的依赖图里找这种圈是不可能的，但 SCC 一出手就解决了：只要任何 SCC 的顶点数大于 1，就存在循环依赖；每个多顶点 SCC 就是一个需要报告的依赖环。

举个例子，假设我们有四个模块：utils 被 app 和 api 依赖，db 被 api 依赖，而 db 反过来又依赖 utils 的某个部分，同时 app 和 api 之间也互相依赖：

flowchart LR
    app["app"] --> api["api"]
    api --> app
    api --> db["db"]
    app --> utils["utils"]
    api --> utils
    db --> utils

这张图里有几个 SCC？app 和 api 互相依赖，构成一个 2 顶点的 SCC；utils 和 db 都是单点 SCC。构建系统会报告：“检测到循环依赖：app ⇄ api，请拆分层级。”而在工程实践中，常见的修复方式是打破依赖环：要么把公共代码抽到一个更底层的新模块，要么把循环中的一边改成“运行时依赖”或“事件通知”，让依赖图重新变成 DAG。

注意一个细节：SCC 报告的是“环的闭包”，而不是“最小环”。比如 app、api、auth 三者两两互相依赖，再加上一条 app→db、db→api 的边，它们可能合并成同一个大 SCC。构建工具通常会把整个 SCC 的成员全部列出来，让开发者自己判断从哪一刀切开最合理。

6.2 社交网络：谁和谁是“铁圈子”

社交网络天然是有向图：用户 A 关注了用户 B，就有一条 A→B 的边。单向关注很常见（明星有大量粉丝，却很少回关），而“互关”代表更紧密的关系。如果把“互关”看作双向可达，那么一个强连通分量就是一群“互相都能连上”的人——他们之间的信息可以沿着关注链传播一圈再回到起点，形成真正的闭环社区。

举个具体例子。假设一个小型社交网络有六个人：

flowchart LR
    Alice["Alice"] --> Bob["Bob"]
    Bob --> Alice
    Alice --> Carol["Carol"]
    Carol --> Dave["Dave"]
    Dave --> Carol
    Bob --> Eve["Eve"]
    Eve --> Frank["Frank"]
    Frank --> Eve
    Carol --> Frank

这里 Alice ⇄ Bob 是一个 2 人 SCC，Carol ⇄ Dave 是另一个 2 人 SCC，Eve ⇄ Frank 是第三个 2 人 SCC，加上 Alice→Carol→Frank 的跨圈关注。SCC 算法给出的社区划分是 {Alice, Bob}、{Carol, Dave}、{Eve, Frank}。这三个圈子内部消息可以互相到达，而圈子之间只有单向流动。平台可以做很多事：给每个 SCC 打上“核心圈”标签，推荐时优先推荐圈内用户；在传播分析里，一个圈子里只要有一个人收到消息，整个圈子都会收到，所以可以把一个 SCC 当成一个传播单元，大大压缩传播模型的状态空间。

当然，真实社交网络的 SCC 划分更复杂：有些平台存在一个巨大的“核心强连通分量”（被称为 giant strongly connected component），大部分用户要么能到它、要么被它到达。这个“巨型 SCC + 外围用户”的结构是研究网络演化的重要指标，也是 SCC 算法在大数据场景下的经典应用之一。

6.3 2-SAT：SCC 的一句话应用

你可能听过“2-SAT”问题，它是逻辑可满足性问题的一个特例：有一组布尔变量，每个约束都是“两个文字之间至少一个为真”的形式，问是否存在一组赋值让所有约束同时成立。这个问题听起来和图的连通性八竿子打不着，但它有一个极其优雅的转化：

每个变量 x 拆成两个顶点：x 和 ¬x；每个约束“x 为真或 y 为真”变成两条蕴含边 ¬x→y 和 ¬y→x。然后求整个蕴含图的 SCC：如果某个变量 x 和它的否定 ¬x 落在同一个 SCC 里，问题无解；否则一定有解，且可以按拓扑序给每个 SCC 赋值。

为什么？因为蕴含图里 x→…→¬x 且 ¬x→…→x 意味着“x 为真”和“x 为假”互相推出，逻辑爆炸，必然无解；如果不存在这种双向推导，就可以沿着缩点 DAG 的拓扑序从“未定”到“已定”逐层赋值，永不冲突。一句话总结：2-SAT 的判定就是一次 SCC 查询。这一节只能给出一句话级别的介绍，等图系列讲完网络流之后，如果读者呼声高，我们可以单独开一篇把 2-SAT 的构造、赋值和实现完整走一遍。

6.4 缩点之后：拓扑排序与最长路

第 2 章说过，缩点图是 DAG，而 DAG 上可以做拓扑排序和动态规划。这一节把两个最实用的组合讲清楚。

组合一：缩点 + 拓扑排序，求“全局顺序”。 很多流程问题要求“先做的事”和“后做的事”有严格顺序，但流程里存在成组的互相依赖。比如课程表：先修关系是 A→B 表示“先修 A 才能选 B”，如果两门课互相依赖（A 先修 B，B 又先修 A），它们必须被当成一个整体来排课。把 SCC 缩点后，课程组之间就有了合法的拓扑序，教务处可以按组排课：先排入度为零的组，再排下一层。这就是“缩点把不可能排序的图变成可排序的图”。

组合二：缩点 + DAG 最长路，求“最大传播/最长时间”。 DAG 上的最长路问题可以用记忆化搜索或拓扑序 DP 在 O(V + E) 内解决：dp[v] = max(0, max(dp[u] + w(u→v)))。但原图一旦有环，最长路定义就会出问题（可以在环里无限绕圈）。缩点之后，环被压成点，DAG 上的最长路就有明确意义了。

举一个信息传播的例子：一张有向图表示“消息可以从 u 传到 v”，我们想知道“从任意起点出发，消息最多能覆盖多少个顶点”。在缩点图上，每个 SCC 的权重就是它包含的顶点数，问题变成求缩点 DAG 上的最大权路径。下面这张图是运行示例缩点后的带权 DAG，X 有 3 个顶点，Y 有 2 个，Z 有 3 个：

flowchart LR
    X["X：权 3（A、B、C）"] --> Y["Y：权 2（D、E）"]
    X --> Z["Z：权 3（F、G、H）"]
    Y --> Z

从 X 出发的最长覆盖是 X→Y→Z，总权重 3 + 2 + 3 = 8，恰好覆盖全图；从 Y 出发是 Y→Z，覆盖 5；从 Z 出发只有 3。这个数字在压缩前的原图上很难直接算——因为原图有环，路径可以“在 SCC 内部绕圈”，而缩点后一切都变得清清楚楚。

工程上类似的问题还有：编译流水线的最长构建时间（每个 SCC 内部并行编译、SCC 之间串行）、数据血缘图的最大影响范围、病毒传播模型中的最坏扩散路径。它们的共同模板都是：先 SCC 缩点，再在 DAG 上做一次拓扑 DP。

6.5 更多脑洞：SCC 还能做什么

篇幅所限，最后再列几个真实场景，作为你日后遇到“有向图 + 成团结构”问题时的检索关键词。

• 数据库死锁检测：把“事务等待锁”建模成有向图，等待图中出现环就意味着死锁；SCC 可以一次性找出所有可能死锁的等待环，而不是只报第一个。
• 游戏任务链设计：任务 A 完成后解锁 B，B 完成后解锁 A，会形成玩家永远卡死的任务环；策划用 SCC 检查任务依赖图，确保没有不可完成的任务组。
• 编译器的调用图分析：递归调用会形成 SCC，编译器据此决定哪些函数必须一起内联、哪些可以分别优化。
• PageRank 与网络分析：搜索引擎的网页图里，强连通分量对应“互相引用的核心站群”，是识别垃圾站群和权威社区的重要特征。
• 依赖注入容器：Spring 这类框架初始化 Bean 时也要检测循环依赖，SCC 是背后的数学本质。

看到规律了吗？几乎所有应用都是同一个故事的不同版本：有向图里的环，就是逻辑上的“互相等待”；SCC 把环和环的闭包一次性揪出来，缩点之后，剩下的问题就交给 DAG 上的成熟工具。

6.6 综合案例：从依赖图到执行计划

把前面所有招式串起来，做一个完整的综合案例。假设你负责一个数据流水线系统，任务是安排 8 个任务的执行顺序。任务之间的依赖关系画成有向图，恰好就是我们全文反复使用的运行示例：A、B、C 互相依赖，D、E 互相依赖，F、G、H 互相依赖，外加 C→D、C→G、E→F 三条跨组依赖。业务上，每组互相依赖的任务必须同时部署、同时启动（因为它们彼此引用，单独启动任何一个都会报错）。

处理流程分四步。第一步，跑 Tarjan（或 Kosaraju）求出三个 SCC：{A,B,C}、{D,E}、{F,G,H}。第二步，缩点得到 DAG：X→Y、X→Z、Y→Z，其中 X 权重 3、Y 权重 2、Z 权重 3。第三步，对缩点 DAG 做拓扑排序，得到合法执行顺序 X → Y → Z（注意 X→Z 直达边不影响顺序，因为 Y 也必须在 Z 之前）。第四步，把 SCC 内部的并行信息加回来：X 的三个任务在同一批执行，Y 的两个任务同一批，Z 的三个任务同一批。最终执行计划是三波：第一波启动 A、B、C，第二波启动 D、E，第三波启动 F、G、H。

这个案例浓缩了 SCC 的全部价值：环内的任务被正确地“捆成一捆”，跨环的顺序由 DAG 的拓扑排序决定，而“每一捆要花多少时间”则由 SCC 内部结构决定。如果你的系统还要考虑“整条流水线最长要多久”，就把每个 SCC 的工期作为点权，在缩点 DAG 上跑一遍最长路——6.4 节的传播例子用的正是同一个模板。

值得一提的是，真实系统里“同一批启动”可能还会遇到资源限制：SCC 内部任务太多，同一批放不下。这时候可以把 SCC 内部再拆成“按依赖层分批”，即对 SCC 的内部子图再做一次拓扑排序（SCC 内部也可能有环，但任务少时通常可以人工约定启动顺序，或者按运行时注入解环）。无论怎么拆，第一刀永远是 SCC，后面的优化都是在它的产物上做文章。

第 7 章 常见错误与调试技巧

写对 Kosaraju 和 Tarjan 并不难，但写错的方式五花八门。这一章把最容易踩的坑集中排一遍，每一条都是真实代码里反复出现的 bug。

7.1 Kosaraju 的三个经典坑

坑一：完成顺序记成了发现顺序。 这是 Kosaraju 最常见的错误。finishOrder.push(u) 必须放在递归返回之后、也就是“后序”位置；如果放在函数开头，你得到的不是完成顺序而是发现顺序，第二次 DFS 会输出一堆乱七八糟的“伪 SCC”。调试方法很简单：打印第一次 DFS 的完成顺序，对比手工计算；如果 H 没有排在第一个完成，说明后序位置写错了。

坑二：第二次 DFS 忘了用反图。 如果第二次 DFS 还在原图上跑，那么从完成时间最晚的顶点出发，往往会一次访问好几个 SCC（因为原图里它可能有出边串到别处），得到的分量数量会少于真实值。检查方法：看结果里 SCC 的数量是否和缩点 DAG 的顶点数一致；再用一个已知例子（比如 A→B、B→A、B→C）验证，正确结果是 {A,B} 和 {C} 两个分量。

坑三：遍历顺序写反。 第二次 DFS 的主循环必须按“完成时间从晚到早”的顺序遍历。如果你正着扫 finishOrder，等于从最早完成的顶点开始，同样会得到错误划分。一个稳妥的写法是让第一次 DFS 往数组末尾 push，第二次 DFS 从数组末尾倒着遍历，就像 3.6 节的代码那样，逻辑一目了然。

7.2 Tarjan 的三个经典坑

坑四：inStack 检查缺失。 如果 v 已经访问过但不在栈里，说明它属于一个已经切好的 SCC，这时用它更新 low 会污染当前分量的 low 值，导致两个分量被错误地合并。这个 bug 尤其隐蔽，因为小图不一定能暴露它；构造一张“分量 A 指向分量 B，B 内部有回边”的图，就能复现。

坑五：low 的更新顺序颠倒。 对树边 v，必须等 dfs(v) 返回之后再用 low[v] 更新 low[u]。如果写成先更新再递归，那么 low[v] 还是初始值，更新的其实是垃圾数据。递归版里这个顺序肉眼可见，但改成迭代版后，很多人会把“进入”和“离开”两个时刻的处理混在一起，同样会踩中。

坑六：弹栈时先判断再弹出。 正确顺序是“弹出 → 标记出栈 → 记录归属 → 判断是否等于 u”。如果先判断 w === u 再弹出，会漏掉根顶点本身，或者陷入死循环。另一个常见变体是忘记在弹栈时把 inStack[w] 置为 false，导致后续顶点错误地复用旧分量的栈信息。

7.3 通用的调试三板斧

第一板斧是小图手工验证。准备三张固定测试图：一张纯链（1→2→3），预期三个单点 SCC；一张双向环加尾巴（1⇄2，2→3），预期 {1,2} 和 {3}；一张双向环加尾巴再加回头边（1⇄2，2→3，3→1），预期整图一个 SCC。三张图分别考验“无环”“单环”“全局环”三种形态，能覆盖绝大多数实现错误。

第二板斧是与朴素算法对拍。写一个暴力参考实现：对每个顶点做一次可达性 BFS，得到 n×n 的可达矩阵，然后两两合并互相可达的顶点。n 小时暴力法完全可行；随机生成几百张 20 个顶点左右的有向图，把暴力结果和 Kosaraju/Tarjan 的结果逐一比对，任何 bug 都会在几分钟内暴露。

第三板斧是打印状态而不是只打印答案。Kosaraju 打印完成顺序和每轮反图 DFS 访问的顶点；Tarjan 打印 dfn、low 和每次弹栈的顶点序列。把状态流和手工走查表并排对比，出错的那一行几乎会自己跳出来。

7.4 高频问答

问：SCC 会不会把一个“只是路过”的顶点误并进来？ 不会。可达性沿着路径传播，如果 x 能到 u，u 也能到 x，那么 x 就是 SCC 的合法成员，不存在“路过但不属于”的顶点。反之，如果 x 只是单向连到 u，u 回不到 x，任何正确算法都不会把它们分到同一组。

问：无向图的连通分量能不能用 Kosaraju？ 能跑，但完全没必要。无向图的反图就是自己（每条边反转后还是原图），完成时间引理退化成无意义的陈述；而无向图连通分量只需要一次 DFS 就能圈出，根本不需要两次。Kosaraju 的舞台是有向图，别拿它去杀鸡。

问：图不连通时，两个算法还能用吗？ 能用，而且不需要任何修改。外层 for 循环会从每个未访问顶点重新开始 DFS，Kosaraju 的完成时间引理在不同连通部分之间不产生干扰，Tarjan 的每个 DFS 根最终都会触发一次弹栈。不连通图的 SCC 划分就是各连通部分 SCC 的并集。

问：自环算不算一个“额外的 SCC”？ 不算。自环只是从顶点到自身的边，而任何顶点都能通过零长度路径到达自己，所以自环不改变 SCC 划分。它可以影响桥和割点的判断，但对 SCC 没有影响。

问：Tarjan 一定比 Kosaraju 快吗？ 不一定。渐近复杂度相同，Tarjan 只在常数上占优；具体快多少取决于图的形态、语言的递归开销、缓存的友好程度。如果代码里 Tarjan 写成了递归版而图又很深，性能可能反而不如迭代版 Kosaraju。

问：求 SCC 时，边的存储顺序会影响结果吗？ 不会影响划分本身，但会影响完成顺序、dfn 编号、弹栈时机这些“过程数据”。所以调试时不要拿“我的完成顺序和别人的不一样”当 bug——只要 SCC 划分一致，过程不同完全正常。

问：缩点之后，原来的点还需要吗？ 取决于后续问题。如果后续只关心分量之间的流动（拓扑、最长路），缩点图就够；如果还要回答“某个具体顶点是否可达另一个具体顶点”，可以保留原图，在缩点图上判断分量间可达性，再在分量内部判断点间可达性。工程上通常是“原图留着、缩点图另建”，两边都不丢。

第 8 章 复杂度与正确性的最后一块拼图

8.1 为什么两个算法都是 O(V + E)

简单过一遍复杂度账。Kosaraju：第一次 DFS 每个顶点进一次、每条边看一次，O(V + E)；构造反图再扫一遍所有边，O(V + E)；第二次 DFS 又是每个顶点、每条反图边一次，O(V + E)。三次线性扫描合起来仍然是 O(V + E)。Tarjan：一次 DFS 里每个顶点进栈出栈各一次、每条边最多被看两次（一次作为树边递归前的检查，一次作为回边/横叉边的判断），所以也是 O(V + E)。

两者的下限都是线性的吗？是的，任何 SCC 算法至少要读一遍所有顶点和边，所以 Ω(V + E) 是信息论意义上的硬下限；两个算法都达到了这个下限，这也是它们能长期统治教科书的原因。

8.2 正确性证明的一句话版本

把两章的证明浓缩成两句话。Kosaraju：缩点图是 DAG，完成时间最晚的 SCC 没有入边；反图把它变成“无出边”，所以反图 DFS 恰好圈住它；剥掉后归纳。Tarjan：栈里待定顶点按 DFS 访问顺序排列，low[u] 是 u 的子树能回到的最浅 dfn；当 low[u] == dfn[u] 时，u 的子树无法逃出 u，栈顶到 u 的这一段恰好构成一个极大互相可达集合。如果你能不看资料把这两句话复述出来，这篇的核心就算真正吃透了。

8.3 关于“极大性”的一个补充证明

有人会问：Tarjan 弹栈得到的一定是“极大”的 SCC 吗？会不会只是某个 SCC 的子集？答案是不会。反证：假设弹出的集合 S 只是某个更大 SCC T 的真子集，那么 T 里存在顶点 x ∉ S 与 S 中的顶点互相可达。x 一定在栈里更深的位置（x 先于 S 的根 u 入栈，否则 x 会被弹出）；x 能与 u 互相可达意味着 u 的子树中存在一条路径能到达 x，于是 low[u] 至多等于 dfn[x] < dfn[u]，与 low[u] == dfn[u] 矛盾。所以弹出的集合必然极大。这个证明值得读两遍，它把“low 相等”和“极大性”之间的缝隙彻底焊死了。

8.4 内存优化的进阶话题

最后提一个进阶优化：Kosaraju 的“反图”可以不用真的存。如果我们按逆拓扑序（从汇点侧）在原图上跑第二次 DFS，同样能切出 SCC——因为缩点图里“无出边”的分量在原图上也是封闭的。于是可以把第二次 DFS 放回原图，只改变遍历顺序，省掉反图的内存。不过这个变种要求你先求出缩点图的拓扑序，反而绕远路，所以工程上还是“存反图”更直接。Tarjan 在内存上天然占优，这也是它在大图上更流行的原因之一。

8.5 复杂度误区三连

关于复杂度，有三个高频误区值得单独点一下。第一个误区是“Tarjan 是 O(V) 的，因为只遍历一次”。错。一次遍历也要把每条边至少看一遍，所以是 O(V + E)；在稀疏图里 O(V + E) ≈ O(V)，在稠密图里 E 可以高达 V² 量级，省略 E 会严重误判。第二个误区是“Kosaraju 是 O(V + E) 的两倍，所以更差”。错。常数倍的线性复杂度还是线性，在渐近意义上两者平级；真正拉开差距的是内存和实现复杂度，不是“两倍”。第三个误区是“SCC 算法能顺便求出所有环”。错。SCC 是“点集”层面的划分，它报告的是强连通块，不是环的枚举；一个 SCC 内部可能有指数多个环，想要具体环必须另写回溯算法。

把这三个误区记牢，面试里被问到复杂度时就不会翻车。

第 9 章 两算法速查表

把全篇最值得背下来的内容收进一张表。建议你把这张表抄在笔记本上，或者存进自己的算法模板库：

项目	Kosaraju	Tarjan
核心思想	原图 DFS 定完成序，反图逆序 DFS 切分量	一次 DFS，dfn + low + 栈
关键判定	无显式判定，顺序即答案	low[u] == dfn[u] 时弹栈
需要反图	是	否
额外数组	完成序、visited、belong	dfn、low、inStack、belong
时间复杂度	O(V + E)	O(V + E)
空间复杂度	O(V + E)	O(V + E)
实现难度	★☆☆	★★☆
常数因子	较大	较小
迭代化	简单	较复杂
典型用途	教学、面试、快速实现	竞赛、大图、需 dfn/low
一句话口诀	正图定序，反图切块	后序汇报，low 到根即出栈

再附一张“什么时候想起 SCC”的快速清单：见到“有向图”“互相可达”“循环依赖”“强连通”“缩点”这些关键词，先问自己——是不是要把环压成点？如果是，SCC 就是第一反应。见到“无向图”，则优先想桥、割点、边双连通，那是另一套但同源的招式。

第 10 章 自测题：检验你的理解

10.3 自测小结

如果你 7 道题都答得顺畅，恭喜，SCC 这块地基已经扎实了。如果某道题卡住，建议回到对应章节重读一遍：题 1、2 回第 1 章，题 3、4 回第 3 章，题 5、6 回第 4 章，题 7 回第 6 章。学习算法最忌讳“好像懂了”，用题目把“好像”磨掉，才是真的懂。

10.4 进阶挑战（选做）

如果基础题已经不能满足你，这里还有三个进阶挑战，它们不追求“新知识”，而是强迫你把本篇的工具用出花样。

挑战一：反向输出 SCC。 修改 Kosaraju 和 Tarjan 的实现，让它们不仅返回每个顶点属于哪个 SCC，还返回每个 SCC 包含哪些顶点，并且按“缩点图拓扑序从源点到汇点”的顺序输出。提示：Tarjan 可以直接利用 4.9 节的编号性质，Kosaraju 则需要先建缩点图再拓扑排序。完成后把两个实现的输出对齐，你会对“算法结果等价”有更深的体会。

挑战二：带权 SCC 覆盖。 给定一张有向图和每个顶点的权重，求“覆盖所有 SCC 的最少点集”，使得每个 SCC 至少有一个代表被选中。提示：先缩点，再看缩点图；这个问题的答案和“没有入边的源点分量数量”有关。想清楚为什么后，你可以再尝试把条件改成“每个 SCC 恰好一个代表”。

挑战三：随机图对拍器。 写一个随机生成器：随机顶点数（10 到 30），以给定概率随机生成有向边，然后分别用暴力两两可达法、Kosaraju、Tarjan 求 SCC，比对三份结果。多跑几千轮，直到三种实现的结果始终一致。这个挑战没有“标准答案”，但它会逼你把每个实现的边界条件（空图、单点、全连通、多连通部分、重复边）全部踩一遍，是性价比最高的收尾练习。

完成三个挑战之后，你基本可以自信地说：Kosaraju 和 Tarjan 不是“背下来的模板”，而是“长在手上的工具”。

附录：本篇术语表

最后附一份术语表，方便你日后查阅和复习：

术语	含义
有向图	边带方向的图，每条边只能沿指定方向通行
可达	存在一条从起点到终点的路径
互相可达	两个顶点之间存在双向路径，记作 u ↔ v
强连通分量（SCC）	极大顶点集合，内部任意两点互相可达
缩点图	把每个 SCC 合并成超顶点后得到的图，必为 DAG
源点分量	缩点图中没有入边的 SCC
汇点分量	缩点图中没有出边的 SCC
完成时间	DFS 离开顶点（子树处理完）的时刻
反图 / 转置图	所有边方向反转后得到的图 Gᵀ
Kosaraju 算法	原图 DFS 定序 + 反图逆序 DFS 切分的两遍算法
dfn	Tarjan 中顶点的发现时间（访问编号）
low	Tarjan 中子树能到达的最浅祖先的 dfn
树边	DFS 树中“发现新顶点”的边
回边	指向栈中祖先的边，能压低 low
横叉边	指向已访问但不在当前 DFS 链上的边，可能忽略或按栈判断
2-SAT	用蕴含图 SCC 判定布尔约束可满足性的经典问题

这份表也是全篇的“索引”：如果你看到一个术语想不起细节，回到对应章节十分钟就能找回状态。

结语与下一篇预告

到这里，图系列第 13 篇就接近尾声了。我们做了一件很酷的事：从“互相可达”这个朴素概念出发，定义了 SCC；证明了缩点图必然是 DAG；然后用两种风格迥异的算法——Kosaraju 的“两次 DFS、一次排序”和 Tarjan 的“一次 DFS、两个时间戳”——把 SCC 高效地找了出来；最后用构建系统、社交网络、2-SAT、DAG 最长路等应用展示了它的威力。往后你再看任何带环的有向图，第一反应应该是：环里藏着 SCC，SCC 可以缩成 DAG，DAG 上什么都能算。

下一篇，《图系列第 14 篇：网络流》，我们将进入图论里最“硬核”也最华丽的领域。网络流研究的是“容量受限的网络上如何运输最多/最省”，从最大流到最小割，从二分图匹配到费用流，它会把前面学过的 BFS、DFS、最短路全部重新武装一遍。SCC 里的“缩点”思想也还会登场——有些网络流问题要先缩点再流。我们下篇见。

最后送上一句本篇的“一句话总结”：有向图里，能互相到达的才是兄弟；把兄弟圈成一个点，剩下的路就是一条清晰的 DAG。