强连通分量
一句话说明
在有向图里，如果一组点彼此都能互相到达，这组点就属于同一个强连通分量；Tarjan 的关键就是用一次 DFS 把这些环状结构整批切出来。
先理解什么叫强连通
无向图里讲“连通”比较简单，只要能走到就行。
但有向图里方向会卡人，所以要更严格：
u 能到 v，且 v 也能回到 u只有这样，u 和 v 才算处在同一个强连通分量里。
Tarjan 真正厉害在哪
它不是先缩点、再反复找环，而是：
- 一次 DFS
- 同时维护访问时间和回溯能力
- 在恰当时机把一整个 SCC 从栈里弹出来
时间复杂度直接做到：
O(V + E)先记住两个数组
dfn[u]
表示点 u 第一次被 DFS 访问到的时间戳。
low[u]
表示从 u 出发，沿 DFS 树边往下，再加上一条返祖边，最早能回到哪个时间戳。
这两个量是 Tarjan 的灵魂。
什么时候能弹出一个 SCC
如果某个点满足：
dfn[u] == low[u]说明它就是当前这批强连通分量的“顶部边界”。
从栈顶一路弹到它自己，弹出的那一整段就是一个 SCC。
Go 代码：Tarjan 模板
func TarjanSCC(graph [][]int) [][]int {
n := len(graph)
dfn := make([]int, n)
low := make([]int, n)
inStack := make([]bool, n)
for i := range dfn {
dfn[i] = -1
low[i] = -1
}
stack := []int{}
timestamp := 0
sccs := [][]int{}
var dfs func(u int)
dfs = func(u int) {
dfn[u] = timestamp
low[u] = timestamp
timestamp++
stack = append(stack, u)
inStack[u] = true
for _, v := range graph[u] {
if dfn[v] == -1 {
dfs(v)
low[u] = min(low[u], low[v])
} else if inStack[v] {
low[u] = min(low[u], dfn[v])
}
}
if dfn[u] == low[u] {
scc := []int{}
for {
x := stack[len(stack)-1]
stack = stack[:len(stack)-1]
inStack[x] = false
scc = append(scc, x)
if x == u {
break
}
}
sccs = append(sccs, scc)
}
}
for i := 0; i < n; i++ {
if dfn[i] == -1 {
dfs(i)
}
}
return sccs
}
func min(a, b int) int {
if a < b {
return a
}
return b
}为什么 inStack 不能省
因为 Tarjan 只关心：
还能回到当前 DFS 路径上的祖先吗？如果一个点已经被弹出栈，它所在 SCC 已经确定，再遇到它时就不能再把它当成“当前可回溯目标”。
所以：
- 访问过，不等于还在当前 SCC 搜索链里
inStack就是专门区分这两件事
一个直觉理解
你可以把 DFS 栈想成“当前还没结案的一串点”。
只要某个点还能回到这串点里的更早祖先，它就还不能独立成块。
直到 dfn[u] == low[u]，才说明以 u 为界，这一整段可以封成一个 SCC。
Tarjan 为什么常和“缩点”一起出现
因为求出 SCC 之后，可以把每个分量缩成一个点。
缩点后的图一定是 DAG，这对很多题非常关键，比如：
- 有向图上的 DP
- 判环后的依赖分析
- 组件级拓扑处理
常见题型
- 求所有强连通分量
- 有向图缩点
- 2-SAT
- 有向图中环结构分析
易错点
Tarjan 最容易错的地方
low[u]更新时，两种来源要分清：树边用low[v]，返祖边用dfn[v]。- 只有
v仍在栈中时，才能用它更新low[u]。dfn[u] == low[u]时，要一路弹栈直到u为止。
复杂度
| 指标 | 复杂度 |
|---|---|
| 时间复杂度 | O(V + E) |
| 空间复杂度 | O(V) |
相关主题
返回：图算法