§06 图结构
Tarjan 强连通分量
一次 DFS 求出所有强连通分量：dfn 时间戳 + low 回溯值，dfn == low 处切分分量。
Tarjan 强连通分量
伪代码
1
procedure Tarjan(u):
2
dfn[u] ← low[u] ← ++index; push(u); inStack[u] ← true
3
for each (u, v) do
4
if v 未访问: Tarjan(v); low[u] = min(low[u], low[v])
5
else if inStack[v]: low[u] = min(low[u], dfn[v])
6
if dfn[u] == low[u]:
7
弹栈直到 u —— 这些点构成一个强连通分量
8
end procedure