Tarjan 算法如何求有向图的强连通分量？

简化版

强连通分量是有向图中任意两个点都能互相到达的最大节点集合。

Tarjan 算法用一次 DFS 维护 dfn、low 和栈。当发现某个节点 u 满足 low[u] == dfn[u] 时，说明 u 是一个强连通分量的根，可以从栈中弹出节点直到 u，这些节点组成一个 SCC。

复杂度是 O(V + E)。

详细版

Tarjan SCC 的核心字段：

字段	含义
`dfn[u]`	访问时间戳
`low[u]`	能追溯到的最早栈内节点时间戳
`stack`	保存当前 DFS 路径上还没归属 SCC 的节点
`inStack`	判断节点是否仍在栈中

当遍历边 u -> v：

如果 v 没访问，DFS 后用 low[v] 更新 low[u]；
如果 v 在栈中，用 dfn[v] 更新 low[u]。

low[u] == dfn[u] 时弹栈形成一个 SCC。

完整版教学

1. 什么是强连通分量

在有向图中，如果节点集合内任意两个点都可以互相到达，这个集合就是强连通的。

强连通分量是最大强连通子图。

例如：

A -> B -> C -> A

这三个点互相可达，构成一个 SCC。

2. 为什么 SCC 有用

强连通分量能把有向图中的环状区域压缩成一个点。

压缩后得到的图是 DAG。

用途	说明
依赖分析	找循环依赖
编译器	分析模块依赖
图压缩	SCC 缩点后做拓扑 DP
可达性分析	简化有向图结构

SCC 缩点是很多有向图问题从“有环”变“无环”的关键步骤。

3. dfn 和 low 在 SCC 中是什么意思

dfn[u] 是访问顺序。

low[u] 表示从 u 出发，通过 DFS 树边和返祖边，能到达的最早的仍在栈中的节点。

和无向图桥割点类似，但 SCC 场景下特别强调「仍在栈中」。

如果一个节点已经出栈，说明它已经属于某个确定 SCC，不应该再影响当前 SCC 的 low。

4. 栈的作用是什么

栈保存当前还没确定 SCC 的节点。

DFS 进入节点时入栈；当发现 SCC 根时，连续弹出直到根节点。

push(u)
...
if low[u] == dfn[u]:
  repeat pop x
  until x == u

被弹出的这一批节点互相可达，组成一个 SCC。

5. 为什么 low[u] == dfn[u] 表示 SCC 根

如果 low[u] == dfn[u]，说明 u 的子树无法回到比 u 更早的栈内节点。

也就是说，以 u 为根的这批节点已经形成一个封闭的强连通区域，不能再并入更早节点的 SCC。

因此可以从栈顶弹出直到 u。

6. 遍历边时如何更新 low

对边 u -> v：

if v 未访问:
  dfs(v)
  low[u] = min(low[u], low[v])
else if v 在栈中:
  low[u] = min(low[u], dfn[v])

如果 v 已访问但不在栈中，它已经归属别的 SCC，不更新 low[u]。

这是 Tarjan SCC 里很容易写错的点。

7. 和 Kosaraju 算法有什么区别

Kosaraju 也能求 SCC，但需要两次 DFS 和反图。

算法	DFS 次数	是否需要反图	复杂度
Tarjan	1 次	不需要	`O(V + E)`
Kosaraju	2 次	需要	`O(V + E)`

Tarjan 实现细节更绕，但只需要一次 DFS。

8. 常见误区与追问

误区：强连通分量等于无向图连通分量。 SCC 是有向图概念，要求双向可达。
误区：已访问节点都能更新 low。 只有还在栈中的节点才用于更新 SCC 的 low。
误区：low[u] == dfn[u] 只说明 u 自己一个点。 它表示可以弹出一个完整 SCC，可能包含多个点。
追问：Tarjan 复杂度是多少？ 每个点和边处理常数次，复杂度 O(V + E)。
追问：SCC 缩点后图有什么性质？ 缩点后是有向无环图。

简化版

详细版