课前零食：从互相绕路到缩点

这杯零食给“会 DFS、但一看到 low 就想把电脑合上”的同学。先把图压成更好理解的形状，再进正式课学严谨的一次 DFS 写法。

本节目标

学完后，你能：

用“能去也能回来”辨认强连通分量（Strongly Connected Component, SCC）；
明白为什么一群互相可达的点可以缩成一个点，且缩完一定没有有向环；
用删边、删点的小实验认识桥（bridge）和割点（articulation point）；
知道正式课里的 dfn/low/栈 各在避免什么重复工作。

前置知识与课前自测

前置：有向边、无向边、DFS/BFS、连通块。请先回答：

有向边 $A\to B$ 存在时，$B$ 一定能回到 $A$ 吗？
若 $A$ 能来回到 $B$，$B$ 能来回到 $C$，$A$ 与 $C$ 的关系如何？
一条无向边若躺在一个环上，删掉它会把环断成两个连通块吗？

答案与最小理由

1. 不一定；箭头不是自动折返券。2. $A$ 与 $C$ 也互相可达，因此“互相可达”可以把点分组。3. 不会，环的另一侧仍能绕过去；这正是“不是桥”的证据。

互动规则：先把“能到”写成箭头账本

这节有两张不同的图，千万别混在一张纸上：一张是有向图，问“能去又能回来”；另一张是无向图，问“删掉谁后断开”。每张纸都画四栏：我从谁出发、这一步沿了哪条边、我还能回到谁、这条边/点被删后谁失去联系。

遇到 low、缩点、桥这些词时，先把它们盖住。你要先亲自回答：哪些点真的扮演同一种“可达角色”？哪条路只是绕远，哪条路是唯一通道？

从零搭框架：把重复问路压成一张地图

第 0 步：先区分单向能到与互相能到

画有向边：A→B, B→C, C→A, C→D, D→E, E→D, E→F。从每个点出发，先只做最普通的 DFS/BFS，并把下表填成“能/不能”：

出发点	能到 A	能到 C	能到 D	能到 F
A
D
F

停顿 0：A 能到 D，D 能到 A 吗？哪些点既能从 A 到达、又能回到 A？先圈成一团。

展开：先得到最原始的分组

`A,B,C` 可以两两来回；`D,E` 可以两两来回；`F` 只能留在自己的单点团。单向可达不是对称关系，不能直接分组；“互相可达”才可以。

第 1 步：让暴力法自己暴露重复工作

若对每个点都做一次 DFS，就能得到完整的可达表，复杂度约为 $O(V(V+E))$。请在刚才的图上标色：从 A 的 DFS 会反复看 A,B,C 的环；从 B 再出发时，又会把同一个环里的边检查一遍。

停顿 1：把 A,B,C 压成一个大圆，D,E 压成一个大圆，F 保留单点。压完后边还剩怎样的方向？有没有环？

展开：缩点不是丢信息，而是删掉无用区分

得到三个点 `ABC→DE→F`。团内任何点对“能否到团外”的角色相同，许多问题不必再区分它们。若缩点后仍有环，环上团可以沿环互相到达，本应合为同一团，矛盾；所以缩点图一定是 DAG。

第 2 步：先证明“互相可达”能安全分组

请为下面三句各写一条路线拼接理由，而不是只写“显然”：

任意点能回到自己吗？
若 $u$ 能来回到 $v$，那么 $v$ 能来回到 $u$ 吗？
若 $u$ 能来回到 $v$，$v$ 能来回到 $w$，怎样拼出 $u$ 到 $w$ 和 $w$ 到 $u$ 的路线？

展开：等价关系给了我们缩点许可

三条分别是自反、对称、传递。尤其传递性允许把一圈关系扩成一个最大团，而不是得到许多互相重叠的小团。SCC 是“互相可达”的等价类，不是 DFS 恰好走到的一坨点。

第 3 步：如何不做 $n$ 次 DFS 就把团找出来

先接受一个适合手算的框架：第一次 DFS 不急着分组，只记录“一个点的所有后继都处理完”的完成时刻；第二次把所有箭头倒过来，按完成时刻从晚到早出发收集点。

请在下表中模拟从 A 的第一次 DFS。每当一个点没有未访问后继时，把它写进 finish：

返回到的点	此时哪些后继已处理完	`finish` 尾部
F
E
D
C

停顿 3：为什么第二轮要把箭头反过来？若仍在原图按倒序出发，从 A 会不会一路跑到 D、E、F？

展开：反图把“团的入口”封起来

第一次完成序列为 `F,E,D,C,B,A`。在反图中先从 A 出发只能收集 `A,B,C`，不会沿原来 `C→D` 的方向越界；之后收 `D,E`，最后收 F。把两次 DFS 看成一种易懂的脚手架；正式课会把它压缩成 Tarjan 的一次 DFS、栈和 `low` 不变量。

第 4 步：换成无向图，问题完全换了

擦掉箭头，画边：A-B, B-C, C-A, C-D, D-E, E-F, F-D。先不用任何公式，做两个物理实验：

用橡皮擦掉 A-B；A 和 B 还能通过谁相遇？
擦掉 C-D；左右两坨还能相遇吗？
擦掉点 C（连同边）；哪几坨会分开？

停顿 4：给“删边断开”和“删点断开”各起一个临时名字，再看下方正式名字。

展开：桥和割点也是“有没有绕路”

`A-B` 在三角形中可绕 `A-C-B`，不是桥；`C-D` 无替代路线，是桥；删 C 会把左侧和右侧分开，C 是割点。这里不再问“能否回来”，而是问一棵 DFS 子树有没有通往祖先的旁路；它与 SCC 的 `low` 名字相同但含义不同。

问题动机：重复问路太浪费

如果要知道任意两点是否互相可达，最暴力的做法是从每个点都 DFS 一遍。$n$ 个点会得到 $O(n(n+m))$ 的工作量；更糟的是，我们反复发现同一个环里的点本来就是“同一团”。

例如 $A\to B\to C\to A$，再有 $C\to D$，$D\leftrightarrow E$，$E\to F$。在团内从谁出发都能绕回来；真正有价值的是团与团之间的单向关系。

步步式引导

1. “互相可达”为什么正好可以分组

把 $u$ 与 $v$ 放同组，当且仅当 $u$ 能到 $v$ 且 $v$ 能到 $u$。它有三种好性质：自己能到自己、关系可以倒过来、两段来回路可以接起来。因此它是等价关系，所有点被自然切成若干个 SCC。

若缩点图还有一个环，例如团 $P\to Q\to R\to P$，那么三个团里的任何点都能沿这些箭头互相到达，本应是同一团，矛盾。所以缩点后的图是 DAG。这个结论让很多“乱图”变成可以按方向依次处理的图。

2. 从两次走路自然得到 SCC

一种适合入门理解的办法是 Kosaraju：

在原图 DFS，某点的所有能继续走的后代处理完后，记下它的完成顺序；
把所有箭头反向；
按完成顺序倒着出发，在反图中一次 DFS 能收集到的一团就是一个 SCC。

为什么不会串到别团？把一团看成缩点 DAG 的一个点。第一次 DFS 中，沿箭头能到达的团会更早完成；倒序挑出的团不会在反图中走进尚未收集的“错误团”。正式课的 Tarjan 把这两次旅行压缩进一趟 DFS：low 负责告诉我们能回到多早，栈负责暂存尚未封口的一团。

finish = []
for every vertex u not visited:
    dfs_original(u) and append u when it finishes

for u in reverse(finish):
    if u not assigned:
        component = dfs_on_reversed_graph(u)
        output component

3. 无向图的“脆弱处”是另一种问题

现在把箭头擦掉。若删一条边后图被切开，它是桥；若删一个点（以及相连边）后图被切开，它是割点。它们都在问：某棵 DFS 子树能否借一条边绕回祖先？

这里有一个容易混的对照：SCC 的 low 关注“仍在当前栈里的可回到位置”；桥/割点的 low 关注“子树能否绕到祖先”。名字相同，工作许可证不同，别把两张表硬嫁接。

纸上模拟：两张表，两个完全不同的问题

先对有向图完成 Kosaraju 的第二轮。把第一轮的 finish=[F,E,D,C,B,A] 写在纸上，倒过来依次尝试 A,B,C,D,E,F。每次从尚未分配的点出发，在反图中记录本轮收进的点：

尝试起点	是否已分配	反图 DFS 收到的点	新分量
A
B
C
D
F

展开：不要把“倒序”误读成“倒着走路线”

从 A 在反图收 `{A,B,C}`；B、C 已分配，跳过；从 D 收 `{D,E}`；最后从 F 收 `{F}`。倒序的是“选择新起点的完成顺序”，每一轮 DFS 仍沿反图箭头正向走。

再对无向图做一个低链前的人工验证。删除 C-D 后，以 A 为起点能访问到哪些点？删除 A-B 呢？请把结果写进：

删除对象	A 所在连通块	另一侧还有谁	结论
边 `C-D`
边 `A-B`
点 `C`

展开：low 公式要对应一条可见的旁路

删 `C-D` 时 A 侧是 `{A,B,C}`，D 侧是 `{D,E,F}`，它是桥；删 `A-B` 后所有点仍连通，因为有 `A-C-B`；删 C 后 A、B 与 D、E、F 分开，C 是割点。正式算法不是真的逐个删除，它只在 DFS 中记录“子树能绕到多早的祖先”，一次性推导出同样结论。

核心知识：删掉什么，谁就暴露出来

在无向 DFS 树中，若孩子 v 的整棵子树不能沿返祖边回到 u 之前的祖先，即 low[v] > dfn[u]，树边 $(u,v)$ 是桥。若非根 u 存在孩子使 low[v] >= dfn[u]，删除 u 后那棵子树无法接到上方，u 是割点。根要特殊处理：它有至少两个 DFS 孩子时才是割点。

这些条件不是魔法公式：把 low[v] 读成人话——“从 $v$ 子树出发，最早还能绕回 DFS 树的哪位祖先”。

小图上暴力删边/删点当然可以用来验证答案，但每次重做连通性会是 $O((n+m)^2)$ 量级。dfn/low 让一趟 DFS 汇总所有绕路信息，达到 $O(n+m)$。

实现指南

有向 SCC 和无向桥不能混用邻接表语义；先在纸上写清楚每条边是否有方向。
无向图要按边编号排除“父边”，不能按父节点排除；否则平行边会被误判成桥。
SCC 缩点后若要建新图，可去重边，但先保留原边才能正确找分量。
递归 DFS 面对很深的链可能爆栈；正式提交时按题目范围改迭代或调整实现策略。

互动小实验室

运行从互相绕路到缩点.py。选择：

1：观察原图完成顺序、反图 DFS 和缩点结果；
2：观察删桥/割点的低链值，并比较“有环可绕”和“桥无处绕”。

先在纸上预测 $C\to D$ 所在的位置会不会把两个 SCC 合并，再让程序揭晓。程序不是神谕，它只是一个不嫌你反复按回车的黑板。

扩展与联系

缩点 DAG 是许多 DP、最少补边和可达性题的起点；桥缩成边双连通分量后得到桥树；割点和点双连通分量会在后续圆方树中重现。现在只需牢牢记住两句话：有向图先看“能否回来”，无向图先问“有没有绕路”。

总结与自检

缩点图为什么不可能有环？
为什么平行边能救下一条看似孤独的树边？
桥条件的严格大于和割点条件的非严格大于，分别对应什么？

自检答案

缩点环会让环上团互相可达；另一条平行边提供了绕回父亲的路；桥要求完全绕不到父亲，割点只要求绕不到父亲之上。

一周预热安排

第 1 天：画三点有向环与单向链，圈出互相可达组。
第 2 天：手做一次“原图完成、反图收集”。
第 3 天：在无向小图上暴力删一条边、删一个点。
第 4 天：运行互动程序，读出一组 dfn/low 的人话含义。
第 5 天：进入强连通分量与缩点正式课。

00-课前零食-从互相绕路到缩点.md 12 KB Permalink Histórico Raw