第 112 章 强连通分量¶
无向图问连通性用并查集（并查集），有向图问强连通性只能用 Tarjan。 把每个强连通分量捏成一个点之后，图里再不会有环——缩点 → DAG DP 是 「有环图上的最长路 / 计数」的标准套路。
这一章最有价值的部分是迭代实现：Tarjan 的递归版在 C++ 里 20 行， 在 Python 里 \(n = 10^5\) 时必然段错误。把它改写成迭代需要一点技巧， 而这个技巧对所有深度可能到 \(10^5\) 的 DFS 都通用。
前两节讲的 DFS 生成树、四类边、dfn 与 low 是整个 Tarjan 系的共同地基，
割点与桥 以及后续的双连通分量、支配树都建立在它们之上。
1 DFS 生成树与四类边¶
从任意一个点开始 DFS，保留所有走过的边，构成一棵树。 上图中绿色边构成了 DFS 生成树，虚线边是非树边。
有向图的非树边分为两类：一类是返祖边，边的终点是起点的祖先；其余的是横跨边。 每条返祖边都代表一个环，所以在 Tarjan 算法中是需要被缩点的。 横跨边一般不会构成环，但是返祖边缩环之后，横跨边也有可能成为返祖边。
严格地讲，有向图 DFS 生成树上的边有四类：
| 类型 | 定义 | 用 dfn / dfs 状态判定 |
是否成环 |
|---|---|---|---|
| 树边（tree edge） | DFS 真正走过的边 | 目标点未访问 | — |
| 返祖边（back edge） | 指向当前栈上的祖先 | 目标点已访问且在栈上 | ✅ 必成环 |
| 前向边（forward edge） | 指向已完成的后代 | 目标点已访问、不在栈上、dfn 更大 |
❌ |
| 横跨边（cross edge） | 指向已完成的其他子树 | 目标点已访问、不在栈上、dfn 更小 |
❌ 但缩点后可能变成返祖边 |
无向图只有两类：树边和返祖边（无向图不可能有横跨边—— 若存在 \(u\to v\) 的横跨边，DFS 到 \(u\) 时一定会从 \(v\) 那边先走过来）。 这个差别正是「无向图的割点/桥」比「有向图的 SCC（strongly connected component，强连通分量： 分量内任意两点互相可达的极大点集）」好判的原因。
DFS 序 dfn¶
还可以记录下 DFS 中每个节点首次访问的时间
dfn。dfn就是 DFS 序。在 DFS 树上，父亲节点的dfn比儿子要小。
dfn 是所有 Tarjan 系算法的地基。有了它，「\(v\) 是不是 \(u\) 的祖先」
可以在 \(O(1)\) 内回答（配合子树区间 [dfn[u], dfn[u]+sz[u])，见 树的基础与遍历）。
2 low 数组¶
除了
dfn数组外，算法还会记录low数组，用于记录「返祖路径」。 正如字面意思low[x]记录的是从 \(x\) 出发能到达的 DFS 序最小的祖先。 DFS 序越小，找到的强连通分量越大。
low[u] 的精确定义（有向图版）：
从 \(u\) 的子树内出发，经过至多一条非树边（且该非树边必须指向仍在栈上的点），
能到达的最小 dfn。
递推：
用大白话说 low[u] 是什么：站在 \(u\) 上，允许往下走任意多条树边（进自己的子树），
最后允许「抄一条近路」跳回一条非树边，问这样最高能爬到树上的哪个位置。
dfn 越小代表位置越高，所以 low[u] 就是「\(u\) 这一坨最高能爬到哪」。
由此得到两个直觉，后面所有判定都从它们出来：
low[u] == dfn[u]：\(u\) 这一坨爬不出 \(u\) 自己，\(u\) 是它那个强连通分量的根；low[v] >= dfn[u]（\(u\) 是 \(v\) 的父亲）：\(v\) 这一坨最高只能爬到 \(u\)， 拿掉 \(u\) 就上不去了，于是 \(u\) 是割点。
三个高频错误： 1. 对返祖边写成
low[u] = min(low[u], low[v])——必须用dfn[v]。 用low[v]在有横跨边的图上会把不该合并的分量合并； 2. 忘记判断「\(v\) 在栈上」，导致横跨边被当成返祖边； 3. 无向图求割点时，必须跳过通往父亲的那条边，而且要按边编号跳，不是按点编号 （否则重边会被误判成桥）。
3 Tarjan 强连通分量¶
先把定义摆清楚：
弱连通：将有向边转为无向边，如果转换后的无向图是连通的，则原有向图是弱连通的。 强连通：如果对于任意两个点之间都至少有一条有向路径，则为强连通的。
Tarjan 老爷爷首先给出了找有向图中所有强连通分量的算法：一个简单的 DFS。 最简单的强连通分量就是一个环。Tarjan 算法的主要思想就是将找到的环全部缩起来， 最后每个强连通分量就会缩成一个点。同时，缩完点后的图由于没有环，所以是一个拓扑图。
终止条件：
当
low等于dfn时，说明此时已经没有能够走出 DFS 子树的路径了， 子树之外的部分对于子树而言是不可达的，因此强连通分量就此而止。 除去子树内部已经找出的强连通分量外，其余的部分属于同一个强连通分量。这个强连通分量内其余的点都是自己的后代，所以它们的 DFS 序都比自己大。 为了快速访问，使用一个栈来记录所有访问过的节点。 每当找到强连通分量时，就可以从栈的尾部依次弹出强连通分量里面的节点。
伪代码（原文照录）：
int cur = 0, dfn[], low[]
bool ok[] // 是否已经出栈
function dfs(int x):
dfn[x] = low[x] = ++cur
stk.push(x)
for v in G[x]: // 邻接表实现：遍历 x 的所有出边 x -> v
if dfn[v] == 0: // 还未访问过
dfs(v)
if not ok[v]: // 还未出栈
low[x] = min(low[x], low[v])
if low[x] == dfn[x]:
do:
int u = stk.pop() // 弹出来的所有 u 在同一个强连通分量内
ok[u] = true
until u == x
这份代码用「未出栈」统一处理了树边和返祖边（都取
low[v]）， 这是可行的写法（对树边取low[v]、对栈上的非树边取low[v]也正确， 因为栈上点的low不会小于它所在分量根的dfn）。 但更主流、更不容易错的写法是显式区分：树边取low[v]，栈上非树边取dfn[v]。 下面的模板用后者。
★ 为什么必须写迭代版¶
| 问题 | 后果 |
|---|---|
| 递归深度 = DFS 树高，链状图上可达 \(n\) | \(n = 10^5\) 时必然爆 C 栈 |
sys.setrecursionlimit(300000) |
只改计数器，C 栈照样溢出 → 段错误，没有任何报错 |
换成大栈线程（threading.stack_size） |
可行但麻烦，且牛客部分判题机会拒绝 |
| 函数调用开销 | \(10^5\) 次递归 \(\approx\) 0.1 秒，不是主要矛盾但也不小 |
结论：Python 写 Tarjan，一律迭代。 见 DFS深度优先搜索。
递归 → 迭代的通用套路¶
递归函数的状态有三块：局部变量、参数、程序计数器（走到第几行了）。 改写成迭代就是把这三块显式存下来：
| 递归里的东西 | 迭代版的替身 |
|---|---|
| 调用栈 | 一个 call 列表存节点编号 |
| 「循环走到第几条边了」 | it[u] 数组：每个点一个出边游标 |
| 函数返回时的「回传」动作 | 弹栈后手动 low[父] = min(low[父], low[u]) |
it[u] 是整个改写的关键——它替代了「程序计数器」。
4 模板：迭代版 Tarjan 强连通分量¶
模板用 CSR（compressed sparse row，压缩稀疏行）存图：
两个扁平数组 start 和 to，点 \(u\) 的所有出边终点就是切片 to[start[u] : start[u+1]]。
它等价于邻接表，但只有两个整数列表，没有 \(n\) 个小 list。
建法见本节末尾的 build_csr，邻接表的常规写法见
图的表示与遍历。
# [片段]
def tarjan_scc(n, start, to):
"""迭代版 Tarjan 强连通分量。点编号 1..n，图用 CSR (start, to) 存。
返回 (comp, nc)：
comp[u] 是 u 所在分量的编号（0..nc-1）；
分量编号按**完成顺序**给出，因此 comp 序是缩点后 DAG 的一个**反拓扑序**
（即若存在边 c1 -> c2，则 comp 编号满足 c2 < c1）。
复杂度 O(n + m)。Python 下 n + m <= 3e5 约 1-2 秒。
"""
dfn = [0] * (n + 1) # dfn[u]=0 兼作「u 未访问」标记，所以时间戳从 1 开始发
low = [0] * (n + 1) # low[u]：u 子树内经至多一条非树边能爬到的最小 dfn
comp = [-1] * (n + 1) # -1 = 还没被划入任何分量
onstk = bytearray(n + 1) # onstk[u]=1 表示 u 在分量栈上，即所属分量尚未定下来
it = [0] * (n + 1) # ★ 出边游标：迭代版的「程序计数器」
stk = [] # Tarjan 的分量栈
call = [] # 显式递归栈
idx = 0 # 时间戳计数器
nc = 0 # 已确定的分量数，同时也是下一个分量的编号
for s in range(1, n + 1):
if dfn[s]:
continue # 图可能不连通，每个点都要当一次起点；已访问的跳过
idx += 1
dfn[s] = low[s] = idx # 刚访问时 low 只能取自己，之后单调变小
stk.append(s); onstk[s] = 1
it[s] = start[s] # 游标指向 s 的第一条出边
call.append(s)
while call:
u = call[-1] # 栈顶 = 「当前正在执行的那一层递归」
if it[u] < start[u + 1]: # 还有出边没走
v = to[it[u]]; it[u] += 1 # 取一条出边并推进游标，等价于 for 循环走一步
if dfn[v] == 0: # 树边：「递归」下去
idx += 1
dfn[v] = low[v] = idx
stk.append(v); onstk[v] = 1
it[v] = start[v]
call.append(v) # 压栈代替函数调用，下一轮 while 就从 v 接着走
elif onstk[v]: # 返祖边 / 指向栈内的横跨边：v 与 u 可能同属一个分量
if dfn[v] < low[u]: # ★ 用 dfn[v] 不是 low[v]
low[u] = dfn[v] # 取 low[v] 会把 v 抄近路到的别人家分量也粘进来
# 剩下一种情况：v 已访问且不在栈上，说明 v 的分量已经封闭，u 到不了 u 自己头上，忽略
else: # 出边走完，「函数返回」
call.pop()
if low[u] == dfn[u]: # u 这一坨爬不出 u 自己 -> u 是分量的根
while True: # 栈上 u 以及压在 u 之上的点，正好构成一个分量
w = stk.pop(); onstk[w] = 0; comp[w] = nc
if w == u:
break # 弹到 u 本身为止，u 也算这个分量里的一员
nc += 1
if call: # 把 low 回传给父亲，等价于递归返回后父亲取 min
f = call[-1]
if low[u] < low[f]:
low[f] = low[u]
return comp, nc
配套的 CSR 建图（比 list of list 省一半内存，且遍历更快）：
# [片段]
def build_csr(n, us, vs):
"""有向边 us[i] -> vs[i] 压成 CSR。返回 (start, to)，
点 u 的出边是 to[start[u] : start[u+1]]。"""
deg = [0] * (n + 2) # 第一遍：数出每个点有几条出边
for u in us:
deg[u] += 1
start = [0] * (n + 2) # 第二遍：出度的前缀和，就是每个点的起始下标
acc = 0
for i in range(1, n + 1):
start[i] = acc # 先写下标再累加，得到的是「不含自己」的前缀和
acc += deg[i]
start[n + 1] = acc # 多留一位哨兵，让 start[u+1] 对最后一个点也有定义
cur = start[:] # cur[u] 是 u 的下一个空位，随着填入不断右移
to = [0] * acc # acc 此时等于总边数，一次开够，不用 append
for i in range(len(us)): # 第三遍：把每条边放进它该在的槽位
u = us[i]
to[cur[u]] = vs[i]
cur[u] += 1
return start, to
comp编号天然是反拓扑序，这是 Tarjan 相对 Kosaraju 的一大便利： 缩点后想在 DAG 上做 DP，按comp编号从 0 到 \(nc-1\) 顺序处理即可， 不需要再跑一次拓扑排序。
5 缩点与 DAG 上 DP¶
一道典型例题（LG P3916 图的遍历）：
给出一张有向图，求出每个点能到达的点中编号最大者。\(n, m \le 10^5\)。
之前提到过，将所有找出的强连通分量缩点后，会得到一张拓扑图。 对于每个强连通分量，内部的点是互相可达的。此外还需要在拓扑图上 DP，找到其他可到达的点。
这题还有一个贪心的做法：将图反着建，然后按编号从大到小依次 DFS，填充答案数组。
缩点的标准三步：
# [片段]
comp, nc = tarjan_scc(n, start, to)
# 1) 分量内部信息聚合（求和 / 取最值 / 计数）
val = [0] * nc
for u in range(1, n + 1):
c = comp[u]
if w[u] > val[c]:
val[c] = w[u]
# 2) 建缩点后的 DAG（去掉分量内部的边，重边一般不影响求最值，求和时要去重）
eus = []; evs = []
for u in range(1, n + 1):
cu = comp[u]
for i in range(start[u], start[u + 1]): # 遍历 u 的每条出边，CSR 里就是一段下标区间
cv = comp[to[i]]
if cu != cv: # 同分量内的边缩没了，留着会在 DAG 上造出自环
eus.append(cu); evs.append(cv)
dstart, dto = build_csr(nc, eus, evs) # 注意 build_csr 是 1..n 的，需按 0..nc-1 调整
# 3) 按 comp 编号**升序**处理（反拓扑序：所有后继的编号都更小）
dp = val[:]
for c in range(nc):
for i in range(dstart[c], dstart[c + 1]):
d = dto[i]
if dp[d] > dp[c]: # 后继 d 的编号 < c，此时 dp[d] 已算完
dp[c] = dp[d]
缩点能解决的经典问题：
| 问题 | 缩点后 |
|---|---|
| 每个点能到达的点权最大值 | DAG 上取后继 max |
| 有向图上的最长路（有环时无意义，缩点后有意义） | DAG 最长路 |
| 「至少加几条边使整个图强连通」 | \(\max(\text{入度为 0 的分量数},\ \text{出度为 0 的分量数})\)（图本身强连通时答案为 0） |
| 2-SAT | 判 \(x\) 与 \(\lnot x\) 是否同分量 |
| 「有多少点能被所有点到达」 | 出度为 0 的分量唯一时，即该分量大小 |
还有一个贪心做法值得记住：P3916 这题反向建图 + 按编号从大到小 DFS， 完全不需要 Tarjan，代码短一半。 拿到「有环图」的题，先问一句「有没有绕开缩点的做法」—— 反向图、按值排序后染色、并查集，往往都能替代。
6 可行规模判断¶
| 任务 | 复杂度 | Python 可行规模 |
|---|---|---|
| 递归版 Tarjan | \(O(n+m)\) | ❌ 深度 \(\ge 10^4\) 就危险，\(10^5\) 必崩 |
| 迭代版 Tarjan | \(O(n+m)\) | \(n+m \le 3\times10^5\) ✅（约 1–2 秒） |
| 迭代版 Tarjan | \(O(n+m)\) | \(n+m \le 10^6\) ⚠️ 约 5–8 秒，需要 5 秒以上时限 |
| 迭代版割点/桥 | \(O(n+m)\) | 同上 |
| 缩点 + DAG DP | \(O(n+m)\) | 同上（再乘 1.5 倍，因为要重建图） |
| CSR 建图 | \(O(n+m)\) | 比 list of list 快约 2 倍、省一半内存 |
估算方法：迭代 Tarjan 的主 while 循环，每条有向边执行一次，每个点额外执行两次
（进栈、出栈），总迭代次数 \(\approx m + 2n\)，每次约 6–10 条 Python 字节码。
按 \(10^7\) 次简单迭代/秒算，\(n+m = 3\times10^5\) 约 0.3–0.5 秒的循环，
加上建图和读入，整体 1–2 秒。
建图往往比算法本身还慢。\(m = 10^5\) 条边，
adj = [[] for _ in range(n+1)]再adj[u].append(v)要做 \(10^5\) 次方法调用 + \(n\) 次列表分配，通常和整个 Tarjan 一样耗时。CSR 值得写。
7 例题¶
| 题号 | 题名 | 难度 | 题解 |
|---|---|---|---|
| BISHI98 | 谍中谍中谍中谍中谍... | 中等 | 题解 |
BISHI98 谍中谍中谍中谍中谍…（中等）¶
\(n \le 1000\) 名学生，每人 \(i\) 指认一个 \(p_i\)，构成每点出度恰为 1 的有向图。 从起点 \(a\) 出发沿指认关系走，第一次遇到已被警告过的学生时该生退学。 对每个起点 \(a\)，输出最终退学的学生编号。 时限：C/C++ 1 秒，其他语言 2 秒。 题面见 原题。
ℹ️
solutions/nowcoder/BISHI98/sol.py已存在（用的是更直白的 \(O(n^2)\) 时间戳染色）。 下面给的是用 Tarjan 缩点的 \(O(n)\) 版本，已由scripts/verify_docs.py用官方样例实测通过，但未提交判题机。
建模：每点出度为 1 的有向图叫函数图（functional graph）。 从任意点出发的路径必然形如「一条尾巴 + 一个环」的 \(\rho\) 形。
关键观察：第一个被重复访问的点，就是路径进入环的那个点（环的入口）—— 进环之前每个点都是新的，进环之后绕一圈回到入口才第一次撞车。
这是 Tarjan 的完美练习场，因为在函数图上：
所以「\(u\) 在环上」\(\iff\)「\(u\) 所在 SCC 大小 \(> 1\)，或 \(p_u = u\)」。
import sys
def tarjan_scc(n, start, to):
"""迭代版 Tarjan 强连通分量，见 112.4 的模板。"""
dfn = [0] * (n + 1) # 首次访问时间；0 兼作「未访问」标记
low = [0] * (n + 1) # 子树内经至多一条非树边能爬到的最小 dfn
comp = [-1] * (n + 1) # 所属分量编号，-1 = 尚未确定
onstk = bytearray(n + 1) # 是否还在分量栈上
it = [0] * (n + 1) # 出边游标，替代递归的程序计数器
stk = []
call = []
idx = 0
nc = 0
for s in range(1, n + 1):
if dfn[s]:
continue # 图不一定连通，逐点当起点，已访问的跳过
idx += 1
dfn[s] = low[s] = idx
stk.append(s); onstk[s] = 1
it[s] = start[s]
call.append(s)
while call:
u = call[-1] # 栈顶就是当前这层「递归」
if it[u] < start[u + 1]:
v = to[it[u]]; it[u] += 1 # 取一条出边，游标右移
if dfn[v] == 0: # 树边：压栈代替递归调用
idx += 1
dfn[v] = low[v] = idx
stk.append(v); onstk[v] = 1
it[v] = start[v]
call.append(v)
elif onstk[v]: # 返祖边：只有仍在栈上的点才和 u 同分量
if dfn[v] < low[u]:
low[u] = dfn[v] # 用 dfn[v] 而非 low[v]
else:
call.pop() # 出边走完，「函数返回」
if low[u] == dfn[u]: # u 爬不出自己，是分量的根
while True:
w = stk.pop(); onstk[w] = 0; comp[w] = nc
if w == u:
break # 弹到 u 为止，弹出来的就是一整个分量
nc += 1
if call:
f = call[-1] # 把 low 回传给父亲
if low[u] < low[f]:
low[f] = low[u]
return comp, nc
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
p = [0] + [int(v) for v in data[1:1 + n]]
# 函数图：每点恰一条出边，CSR 退化成 start[u] = u、to[u] = p[u]
start = list(range(n + 2))
to = p[:]
comp, nc = tarjan_scc(n, start, to)
csz = [0] * nc # 每个分量的点数
for u in range(1, n + 1):
csz[comp[u]] += 1
ans = [0] * (n + 1) # 0 表示答案未知，题目点号从 1 起，不会歧义
for u in range(1, n + 1): # 环上的点（含自环）答案是自己
if csz[comp[u]] > 1 or p[u] == u: # 函数图里分量大小 > 1 只可能是环；自环单独判
ans[u] = u
for s in range(1, n + 1): # 尾巴上的点继承后继的答案
if ans[s]:
continue
path = []
u = s
while ans[u] == 0: # 一路走到已知答案的点
path.append(u); u = p[u] # 记下沿途的点，等会儿一次性填答案
r = ans[u] # 终点的答案就是这条尾巴上所有点的答案
for w in path:
ans[w] = r # 回填让每个点只被走一次，总复杂度 O(n)
sys.stdout.write(" ".join(map(str, ans[1:])) + "\n")
main()
样例复核：\(n=3\)，\(p = [2,3,1]\) 构成一个三元环，
SCC 只有一个、大小为 3，所以三个点都在环上，答案 1 2 3 ✓。
手工验证一个带尾巴的例子：\(n=5\)，\(p = [2,3,4,3,4]\)。
环是 \(3 \to 4 \to 3\)，尾巴是 \(1\to2\to3\) 和 \(5\to4\)。
输出 3 3 3 4 4——起点 1、2、3 都在 3 处撞车，起点 4、5 都在 4 处撞车 ✓。
两种做法的取舍：
做法 复杂度 代码量 什么时候用 时间戳染色（ solutions/nowcoder/BISHI98/sol.py）\(O(n^2)\) 15 行 \(n \le 3000\)，首选 迭代 Tarjan + 继承 \(O(n)\) 60 行 \(n \ge 10^5\)，或本来就要缩点 \(n = 1000\) 时 \(O(n^2) = 10^6\)，Python 里 0.2 秒，完全够。 这题选 Tarjan 是为了练手，不是因为必须。 拿到题先看数据范围——这是比会写 Tarjan 更重要的能力。
8 本章速查¶
| 要点 | 结论 |
|---|---|
| 有向图 DFS 树的边 | 树边 / 返祖边 / 前向边 / 横跨边 |
| 无向图 DFS 树的边 | 只有树边和返祖边（没有横跨边） |
dfn[u] |
首次访问时间（DFS 序），父亲一定比儿子小 |
low[u] |
子树内经至多一条非树边能到的最小 dfn |
| 返祖边更新 low | low[u] = min(low[u], dfn[v])，不是 low[v] |
| SCC 判定 | low[u] == dfn[u] → 弹栈弹出一整个分量 |
| 栈的作用 | 记录「还没被划入任何分量」的点 |
comp 编号顺序 |
反拓扑序，DAG DP 直接按编号升序做 |
| 缩点后 | 一定是 DAG（拓扑图） |
| 「加几条边使强连通」 | \(\max(\text{入度 0 分量数},\ \text{出度 0 分量数})\) |
| Python 的铁律 | Tarjan 一律写迭代，递归 \(n \ge 10^4\) 就危险 |
| 迭代改写的关键 | it[u] 出边游标，替代递归的程序计数器 |
setrecursionlimit |
救不了，C 栈照样溢出（段错误、无报错） |
| 建图 | 用 CSR，比 list of list 快 2 倍、省一半内存 |
| 数据规模 → Python 现实性 |
|---|
| 递归 Tarjan，深度 \(\ge 10^4\) |
| 迭代 Tarjan，\(n+m \le 3\times10^5\) |
| 迭代 Tarjan，\(n+m \le 10^6\) |
| 缩点 + DAG DP，\(n+m \le 3\times10^5\) |
| 函数图找环，\(n \le 3000\) |
割点与桥的速查条目在 割点与桥 章末。