第 112 章 连通性：强连通分量与割点¶
配套例题：BISHI98 谍中谍中谍中谍中谍…、BISHI99 我朋友的朋友不是我的朋友 来源：S3 day7《简单图论》第 72–103 页（求拓扑图的「割点」/ 强连通分量 / DFS 生成树 / Tarjan 算法 / LG P3916 图的遍历）；S4
模板.docx「图论 → 强连通分量 → tarjan」 前置：90-图的表示与遍历、93-拓扑排序与二分图、60-DFS深度优先搜索
112.0 这一章为什么存在¶
S3 day7 有整整 30 页讲 DFS 生成树、割点和 Tarjan 强连通分量， S4 的模板清单里也把「强连通分量 tarjan」列为 NOIP 复赛必备。 但牛客的 147 道笔试题里没有一道需要缩点。
这不奇怪：企业笔试的图论题止步于「最短路 + 拓扑排序 + 并查集」， Tarjan 属于 NOIP/ACM 的领域。
那为什么还要写这一章？
| 理由 | 说明 |
|---|---|
| 它是「有向图版的并查集」 | 无向图问连通性用并查集（38 章），有向图问强连通性只能用 Tarjan |
| 缩点后是 DAG | 把每个强连通分量捏成一个点后，图里再不会有环，变成 DAG（有向无环图，directed acyclic graph）；「有环图上的最长路 / 计数」的标准套路就是缩点 → DAG DP |
| 递归实现在 Python 里一定爆栈 | 这是 Python 选手必须解决的问题，本章给出完整迭代版 |
| 割点 / 桥是网络可靠性的标准建模 | 「删掉哪个点会让网络断开」 |
这一章最有价值的部分是迭代实现：Tarjan 的递归版在 C++ 里 20 行， 在 Python 里 \(n = 10^5\) 时必然段错误。把它改写成迭代需要一点技巧， 而这个技巧对所有深度可能到 \(10^5\) 的 DFS 都通用。
112.1 DFS 生成树与四类边¶
S3 day7 第 78、90 页：
从任意一个点开始 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¶
S3 day7 第 91–92 页：
还可以记录下 DFS 中每个节点首次访问的时间
dfn。dfn就是 DFS 序。在 DFS 树上，父亲节点的dfn比儿子要小。
dfn 是所有 Tarjan 系算法的地基。有了它，「\(v\) 是不是 \(u\) 的祖先」
可以在 \(O(1)\) 内回答（配合子树区间 [dfn[u], dfn[u]+sz[u])，见 94 章）。
112.2 low 数组¶
S3 day7 第 93、97 页：
除了
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. 无向图求割点时，必须跳过通往父亲的那条边，而且要按边编号跳，不是按点编号 （否则重边会被误判成桥）。
112.3 Tarjan 强连通分量¶
S3 day7 第 74–77 页给了定义：
弱连通：将有向边转为无向边，如果转换后的无向图是连通的，则原有向图是弱连通的。 强连通：如果对于任意两个点之间都至少有一条有向路径，则为强连通的。
Tarjan 老爷爷首先给出了找有向图中所有强连通分量的算法：一个简单的 DFS。 最简单的强连通分量就是一个环。Tarjan 算法的主要思想就是将找到的环全部缩起来， 最后每个强连通分量就会缩成一个点。同时，缩完点后的图由于没有环，所以是一个拓扑图。
第 97 页解释了终止条件：
当
low等于dfn时，说明此时已经没有能够走出 DFS 子树的路径了， 子树之外的部分对于子树而言是不可达的，因此强连通分量就此而止。 除去子树内部已经找出的强连通分量外，其余的部分属于同一个强连通分量。这个强连通分量内其余的点都是自己的后代，所以它们的 DFS 序都比自己大。 为了快速访问，使用一个栈来记录所有访问过的节点。 每当找到强连通分量时，就可以从栈的尾部依次弹出强连通分量里面的节点。
课件给的伪代码（第 99 页，原文照录）：
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，一律迭代。 见 60-DFS深度优先搜索。
递归 → 迭代的通用套路¶
递归函数的状态有三块：局部变量、参数、程序计数器（走到第几行了）。 改写成迭代就是把这三块显式存下来：
| 递归里的东西 | 迭代版的替身 |
|---|---|
| 调用栈 | 一个 call 列表存节点编号 |
| 「循环走到第几条边了」 | it[u] 数组：每个点一个出边游标 |
| 函数返回时的「回传」动作 | 弹栈后手动 low[父] = min(low[父], low[u]) |
it[u] 是整个改写的关键——它替代了「程序计数器」。
112.4 模板：迭代版 Tarjan 强连通分量¶
模板用 CSR（compressed sparse row，压缩稀疏行）存图：
两个扁平数组 start 和 to，点 \(u\) 的所有出边终点就是切片 to[start[u] : start[u+1]]。
它等价于邻接表，但只有两个整数列表，没有 \(n\) 个小 list。
建法见本节末尾的 build_csr，邻接表的常规写法见
90-图的表示与遍历。
# [片段]
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\) 顺序处理即可， 不需要再跑一次拓扑排序。
112.5 缩点与 DAG 上 DP¶
S3 day7 第 100–103 页给的例题（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，代码短一半。 拿到「有环图」的题，先问一句「有没有绕开缩点的做法」—— 反向图、按值排序后染色、并查集，往往都能替代。
112.6 无向图：割点与桥¶
有向图讲强连通，无向图讲割点（cut vertex / articulation point）和桥（bridge / cut edge）。
| 概念 | 定义 |
|---|---|
| 割点 | 删掉它（及其所有边）后，连通块数量增加 |
| 桥 | 删掉这条边后，连通块数量增加 |
判定条件¶
设 DFS 生成树上 \(u\) 是 \(v\) 的父亲：
| 对象 | 条件 |
|---|---|
| \(u\) 是割点（\(u\) 非根） | 存在儿子 \(v\) 使 \(low[v] \ge dfn[u]\) |
| \(u\) 是割点（\(u\) 是根） | 根在 DFS 树上有 \(\ge 2\) 个儿子 |
| 边 \((u,v)\) 是桥 | \(low[v] > dfn[u]\) |
记忆：
- 割点用 \(\ge\)：儿子最多只能回到 \(u\) 自己，回不到 \(u\) 的上面 → 拿掉 \(u\) 就断了；
- 桥用 \(>\)：儿子连 \(u\) 都回不到 → 只能靠这条边连着。
根节点的特判是最常见的 bug。根没有父亲，\(low[v] \ge dfn[root]\) 恒成立 （\(dfn[root] = 1\) 是全局最小），所以不特判会把所有有儿子的根都判成割点。
S3 day7 里的另一种「割点」¶
课件第 72 页讲了一个同名但完全不同的东西：
求拓扑图的「割点」：给出一张 \(n\) 个点的拓扑图，保证点 1 能够到达点 \(n\)。 找出所有的节点 \(x\)，满足删除 \(x\) 后，点 1 不能到达点 \(n\)。\(n \le 10^5\)。
DP 求出 \(S[x]\) 和 \(T[x]\)，分别表示从点 1 到 \(x\) 的路径总数，和 \(x\) 到 \(n\) 的路径总数。 所谓割点，就是每条从 1 到 \(n\) 的路径都会经过的点。 那么对于割点 \(x\)，\(S[x] \cdot T[x]\) 必定等于 \(S[n]\)。每个点都试一下就好了。
这是 DAG 上的「必经点」，和无向图的割点是两回事，别混淆。 它的做法是路径计数：正向 DP 一遍求 \(S\)，反向 DP 一遍求 \(T\)， 然后 \(S[x] \cdot T[x] = S[n]\) 就是必经点。 路径数会指数级增长，实现时要取模（用两个不同的模数降低碰撞概率）， Python 大整数虽然不会溢出，但位数爆炸后乘法会变慢，照样要取模。
模板：迭代版求割点与桥¶
# [片段]
def cut_and_bridge(n, start, to, eid):
"""迭代版求无向图的割点与桥。O(n + m)。
图用 CSR 存，且必须额外给出 eid：eid[i] 是第 i 条**有向半边**对应的
无向边编号（一条无向边的两个方向共用同一个编号）。
——这是正确处理**重边**的关键：跳过父边要按边编号跳，不能按点编号跳。
返回 (is_cut, bridges)：
is_cut[u] 为 1 表示 u 是割点；
bridges 是桥的**无向边编号**列表。
"""
dfn = [0] * (n + 1) # 0 兼作「未访问」标记
low = [0] * (n + 1) # low[u]：u 子树内经至多一条返祖边能爬到的最小 dfn
is_cut = bytearray(n + 1)
bridges = []
it = [0] * (n + 1) # 出边游标，替代递归的程序计数器
pe = [-1] * (n + 1) # pe[u] = u 的父边编号；根没有父边，记 -1
idx = 0
for s in range(1, n + 1):
if dfn[s]:
continue # 图可能有多个连通块，每块各跑一次 DFS
idx += 1
dfn[s] = low[s] = idx
it[s] = start[s]
pe[s] = -1
call = [s]
root_children = 0 # 根在 DFS 树上的儿子数，只对本轮的根 s 计数
while call:
u = call[-1]
if it[u] < start[u + 1]:
i = it[u]; it[u] += 1 # i 是半边下标，先推进游标再处理，避免死循环
v = to[i]; e = eid[i]
if e == pe[u]: # ★ 按边编号跳过父边，重边不会被误跳
continue # 换成 v == 父点 的写法，平行边会被一起跳掉而错判成桥
if dfn[v] == 0:
idx += 1
dfn[v] = low[v] = idx
pe[v] = e # 记下 v 是从哪条无向边下来的
it[v] = start[v]
call.append(v)
if u == s:
root_children += 1 # 只有从根直接长出的树边才算根的儿子
elif dfn[v] < low[u]: # 返祖边：无向图没有横跨边，不必判「在不在栈上」
low[u] = dfn[v]
else:
call.pop()
if call: # 有父亲才谈得上「u 能不能爬过父亲」
f = call[-1]
if low[u] < low[f]: # 先把 low 回传，等价于递归返回后父亲取 min
low[f] = low[u]
if low[u] >= dfn[f] and f != s: # 割点：>=，且父亲不是根
is_cut[f] = 1 # u 这一坨最高只爬到 f，删掉 f 就把 u 隔离了
if low[u] > dfn[f]: # 桥：>
bridges.append(pe[u]) # u 连 f 都爬不到，只能靠父边 pe[u] 连着
if root_children >= 2: # 根的特判：根没有父亲，low[儿子] >= dfn[根] 恒成立
is_cut[s] = 1 # 根只有靠「儿子数」判断：两棵子树全靠根串在一起
return is_cut, bridges
def build_undirected_csr(n, edges):
"""无向图 CSR，附带边编号 eid。edges 是 (u, v) 列表。"""
deg = [0] * (n + 2) # 无向边贡献两条半边，两端的度都要加
for u, v in edges:
deg[u] += 1; deg[v] += 1
start = [0] * (n + 2) # 度数的前缀和 = 每个点在 to 里的起始下标
acc = 0
for i in range(1, n + 1):
start[i] = acc
acc += deg[i]
start[n + 1] = acc # 哨兵位，使 start[u+1] 对 u = n 也可用
cur = start[:] # 各点的下一个空位
to = [0] * acc
eid = [0] * acc
for i, (u, v) in enumerate(edges): # 一条无向边拆成两条半边，共用编号 i
to[cur[u]] = v; eid[cur[u]] = i; cur[u] += 1
to[cur[v]] = u; eid[cur[v]] = i; cur[v] += 1
return start, to, eid
自测：环 \(1-2-3-1\) 接上环 \(4-5-6-4\)，中间用边 \(3-4\) 相连。 割点应是 \(\{3, 4\}\)，桥应是 \(\{(3,4)\}\)——上面的模板实测输出正是如此。 重边测试：\(1-2\) 有两条平行边、\(2-3\) 一条，割点只有 \(2\)，桥只有 \((2,3)\) （平行边不是桥，若按点编号跳父边就会错判）。
112.7 可行规模判断¶
| 任务 | 复杂度 | 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 值得写。
112.8 例题¶
BISHI98 谍中谍中谍中谍中谍…（中等）¶
\(n \le 1000\) 名学生，每人 \(i\) 指认一个 \(p_i\)，构成每点出度恰为 1 的有向图。 从起点 \(a\) 出发沿指认关系走，第一次遇到已被警告过的学生时该生退学。 对每个起点 \(a\)，输出最终退学的学生编号。 时限：C/C++ 1 秒，其他语言 2 秒。 题面见 BISHI98 原题（牛客）。
ℹ️
solutions/BISHI98.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/BISHI98.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 更重要的能力。
BISHI99 我朋友的朋友不是我的朋友（中等）¶
\(n, m \le 10^5\)。\(m\) 对朋友关系（字符串姓名，无向边）。 记 \(\deg(x)\) 为好友数，\(\operatorname{avg}(x) = \frac{\sum_{y\in N(x)}\deg(y)}{\deg(x)}\)。 若 \(\deg(x) > \operatorname{avg}(x)\) 则 \(x\) 是「社牛」。按字典序输出所有社牛，无则输出
None。 题面见 BISHI99 原题（牛客）。ℹ️
solutions/BISHI99.py已存在，下面的代码与它一致，并由scripts/verify_docs.py用官方样例实测通过。
先说清楚：这题的实际考点不是连通性，是「字符串建图 + 度数统计 + 避免浮点」。 大纲把它挂在本章，是因为它提供了一个标准的无向图读入与建图流程—— 把它当成 112.6 割点模板的输入预处理来读。
核心变形（避免浮点的通用技巧）：
两边同乘 \(\deg(x) > 0\)，不改变不等号方向，且全部变成整数比较。
import sys
def main():
data = sys.stdin.buffer.read().split() # 整份输入一次读完，按空白切成 bytes 列表
m = int(data[1]) # data[0] 是人数 n，本题用不到；data[1] 才是边数
idx = {} # 姓名(bytes) -> 编号
names = []
edges = []
p = 2 # 前两个 token 是 n 和 m，姓名从下标 2 开始
for _ in range(m):
a = data[p]; b = data[p + 1]; p += 2 # 每行两个姓名，指针一次前进 2
ia = idx.get(a, -1) # -1 当哨兵，比 in 判断再取值少一次哈希
if ia < 0:
ia = len(names); idx[a] = ia; names.append(a) # 首次出现的名字，分配下一个编号
ib = idx.get(b, -1)
if ib < 0:
ib = len(names); idx[b] = ib; names.append(b)
edges.append((ia, ib))
k = len(names) # 真正出现过的人数，可能少于题面给的 n
deg = [0] * k
for ia, ib in edges: # 第一遍：把所有人的度数统计完整
deg[ia] += 1
deg[ib] += 1
nbr = [0] * k # nbr[x] = 邻居度数之和
for ia, ib in edges: # 第二遍：此时 deg 已定稿，才能拿去累加
nbr[ia] += deg[ib]
nbr[ib] += deg[ia]
# deg(x) > avg(x) <=> deg(x)^2 > Σ deg(邻居)，全整数比较
res = [names[i] for i in range(k) if deg[i] * deg[i] > nbr[i]]
if not res:
sys.stdout.write("None\n")
return
res.sort() # bytes 排序 == 小写字母的字典序
sys.stdout.write(b" ".join(res).decode() + "\n")
main()
四个要点：
- 姓名先映射成整数编号，之后全在数组上做。
直接拿字符串当
dict的 key 反复读写会慢 3–5 倍； bytes不 decode 直接排序——小写字母的字节序就是字典序， 最后输出时才b" ".join(...).decode()；- 两遍扫边：第一遍统计
deg，第二遍才能累加邻居的deg。 一遍是做不到的（累加时对方的度数还没统计完）； - 度数为 0 的人 \(\operatorname{avg}\) 是 \(0/0\) 无定义，自然不是社牛，直接忽略。
「两边同乘化成整数比较」是通用武器，凡是「\(a > b/c\)」形式的判定都该这么做。 见 23-浮点与科学计数法。
接上本章主题：如果这题改成「删掉哪个人会让某两人失去联系」， 那就是真正的割点问题，直接把上面的
edges喂给 112.6 的build_undirected_csr+cut_and_bridge即可。 建图部分完全不用改——这就是把它放在本章的实际价值。
112.9 本章速查¶
| 要点 | 结论 |
|---|---|
| 有向图 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 分量数})\) |
| 割点（非根） | 存在儿子 \(v\) 使 \(low[v] \ge dfn[u]\) |
| 割点（根） | DFS 树上儿子数 \(\ge 2\) |
| 桥 | \(low[v] > dfn[u]\)（严格大于） |
| 跳过父边 | 按边编号跳，不能按点编号（否则重边被误判成桥） |
| DAG 的「必经点」 | 路径计数 \(S[x]\cdot T[x] = S[n]\)，和割点是两回事 |
| 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\) |