课前零食：从共享房间到圆方树

圆方树不是“再给图换一套很玄的名字”。它处理的是一个很朴素的尴尬：两个结实的小团体可以共用同一个人；把人硬塞进互不重叠的组里，反而把信息弄丢了。今天我们先把这件尴尬画出来，再给“团体”发一张方形身份证。

本节目标

学完后，你能：

从删点实验中认出割点与点双连通分量（vertex-biconnected component）分别在描述什么；
解释为什么点双分量可以共享割点，不能像强连通分量那样直接缩成互不重叠的点；
手工把一张无向图变成圆方树（block-cut tree），并在树上读出必经的割点；
跟踪边栈在何时弹出一个点双块，知道条件 low[child] ≥ dfn[parent] 的人话含义；
用“原点是圆、块是方”的统一视角，为后面的路径统计和树上 DP 搭好框架。

前置知识与课前自测

前置：无向图、DFS 树、桥和割点的直觉。不会写 Tarjan 也没关系；本节会先用暴力删除验证。

删除一个点 C 后图分成两块，C 自己该归到哪一块？
三角形 A-B-C-A 中，删掉 B 后 A 与 C 还连通吗？
两个“删掉任一点仍有路绕开”的大块，能共享两个原图顶点吗？

先别急着看：自测答案

1. 它往往同时是多块的门口，硬选一边会丢掉另一边的归属。2. 仍连通，直接走 A-C。3. 不能。若共享两个点，这两块可经两个公共点拼成更大的点双块；真正的重叠只能是一处割点。

互动规则：把图当作一栋有门的房子

请在纸上画下面的无向图；边都是双向走廊：

三角形一：A-B-C-A
三角形二：C-D-E-C
走廊链：  C-F-G

纸上分四栏：对象（现在有哪些房间、走廊）、状态（删掉谁、DFS 到哪）、动作（本轮能沿哪条走廊）、账本（哪些点属于哪些结实团体）。每次遇到“停顿”，先写答案，再展开或运行程序。

贯穿问题不是“背出圆方树定义”，而是：从 A 去 E、从 A 去 G 时，哪些门卫绝对绕不过？如果后来要问很多次路径，能否只在一棵树上回答？

从零搭框架：先让“一个人属于两组”真的发生

第 0 步：暴力拆房，先不许用 low

依次把 C、F 从图上擦掉，并从 A 出发标记还可到达的点。记录：

被删除的点	A 一侧还看见谁	另一侧有哪些点	这说明什么
C
F

停顿 0：删 C 后，A、B、D、E、F、G 分成哪几堆？C 若是“某个团的成员”，它要属于几团？

展开：第一处不能硬分组的地方

删 C 后有 {A,B}、{D,E}、{F,G} 三堆，所以 C 是割点。它同时是三角形 ABC、三角形 CDE 与走廊 CF 的端点。若把 C 只分给其中一个团，另两个团与 C 的连接信息就被擦掉了；这正是“普通缩点”不够用的原因。

第 1 步：先找真正结实的局部

把三角形 ABC 圈起来。删除其中任一顶点，剩下两点仍有边相连；所以它内部没有一个单点能把其余成员拆开。CDE 也一样。单条走廊 CF 虽然没有绕路，但在以边为单位的点双分解里，它也形成一个含 C、F 的块：它提醒我们这条连接只经由两端。

停顿 1：为什么“删 C 后 A 到 E 断了”不等于“ABC 这个三角形不结实”？请分别写出这两个问题删除后的剩余对象。

展开：块内结实，与块间门口是两层问题

ABC 问的是只看 A、B、C 这个小块时，删一个点后剩余点是否仍连通；删 C 后 A-B 仍有边。A 到 E 的问题却跨了两个块，所有跨越都要经过 C。点双块负责保存局部可绕性，割点负责说明块与块之间的唯一门口。

第 2 步：发明方点，而不是复制原点

试过“给每个点双块涂一种颜色”后，C 会被迫涂三种颜色。不要复制 C；复制的是块这个关系。做法如下：

原图每个顶点保留一枚圆点；
每个点双块新建一枚方点；
方点与属于该块的全部圆点连边。

请为 ABC、CDE、CF、FG 分别画方点 Q1、Q2、Q3、Q4，再连到对应圆点。

停顿 2：在你新画出的图中，圆点 C 的度数是多少？从圆点 A 到圆点 G 的唯一路径经过哪些方点和圆点？

展开：把重叠改写成树边

C 连 Q1、Q2、Q3，度数为 3。A 到 G 的路径是 A-Q1-C-Q3-F-Q4-G；其中 C、F 是原图中绕不过的割点。原图的“块重叠”被方点吸收后，连接关系变成树状，不再需要在一张有环图里猜所有绕路。

第 3 步：为什么结果真会是一棵树

先只看连通原图。每加入一个新点双块，它若和已经出现的块共享两个原点，就会与旧块合并成更大的点双块，矛盾；因此它只会通过一个割点接到已有部分。每个新方点像给树挂上一颗新叶子，圆方图不会出现环。

这一步很重要：圆方树不是“把原图画得好看”，而是用一棵树保存原图的块—割点骨架。原图的一条边落在某个方点内部；跨块路径则只能在圆方树中穿过相应圆点。

问题动机：暴力删点会重复做太多次

刚才逐个擦点很直观，但若有 n 个点、m 条边，每删一个点都重做一次 DFS，会接近 O(n(n+m))。我们需要在一次 DFS 中记住：某个孩子子树有没有一条边能绕回父亲之前的祖先。

步步式引导：把尚未封口的走廊放进边栈

1. 边栈里放的不是“访问顺序”，而是暂未归属的边

从 A DFS。每走一条树边，或看见一条通往祖先的返祖边，就把边编号压进栈。为什么不是压顶点？因为 C 需要出现在多个块里；一条边却恰好属于一个点双块，最后可以放心交出去。

令 dfn[u] 是 u 首次被看到的时间，low[u] 是从 u 的 DFS 子树出发，经零条或多条树边、至多一条返祖边，能碰到的最早祖先时间。

当树边 u-v 满足：

$$ low[v]\ge dfn[u], $$

v 子树再也不能绕到 u 的上方。栈顶直到边 u-v 为止的走廊恰好封成一个点双块；把它们弹出，新建一个方点。

2. 先翻译不等式，再看伪代码

low[v] < dfn[u]：子树能从侧门绕到 u 的祖先，暂时不能封口；
low[v] = dfn[u]：能绕回 u 本人，却到不了上方；在 u 这里封口；
low[v] > dfn[u]：连 u 也绕不回，这条树边还是桥；它仍对应一个只有这条边的块。

停顿 3：在图中从 C 走到 F，再走到 G。G 返回 F 时为什么必然封出 FG？F 返回 C 时为什么又会封出 CF？

展开：没有旁路的走廊会逐段结账

G 没有返祖边，low[G]=dfn[G]，大于 dfn[F]，所以弹出 FG。随后 F 的 low 仍是 dfn[F]，大于 dfn[C]，再弹出 CF。桥不是“圆方树做不了的边”；它恰好是一个极小的方块，只连接它的两个端点。

DFS(u, parent_edge):
    dfn[u] = low[u] = next_time()
    for edge e=(u,v):
        if e is parent_edge: continue
        if v is unvisited:
            push e onto edge_stack
            DFS(v, e)
            low[u] = min(low[u], low[v])
            if low[v] >= dfn[u]:
                pop edges through e as one block
                create one square node for their endpoints
        else if dfn[v] < dfn[u]:
            push e onto edge_stack
            low[u] = min(low[u], dfn[v])

适用条件：这里是静态无向图。重边必须按边编号跳过父边，不能把“连到父亲”全跳过；否则另一条平行边提供的绕路会消失。

核心知识：圆点与方点各自承诺什么

节点	表示	它连向谁	读路径时意味着什么
圆点	原图一个顶点	包含它的方点	可能是割点，也可能只是块内成员
方点	一个点双连通块	该块的原顶点	在块内部可以绕开单个成员

原图连通时，圆方树是一棵树；原图不连通时得到森林。两原点间在原图跨越的点双块顺序，就是圆方树上两圆点之间的路径。若题目询问“从 u 到 v 必经多少个割点”，常可在这条树路径上统计度数大于 1 的圆点（但要按题目是否计端点调整）。

正确性的账本有两层：边栈弹出的边在边界出现前不能和更早边组成同一块；边界出现时它们又通过 DFS 路径和返祖边连成最大块。每条边压、弹各一次，Tarjan 与建树总计 O(n+m)，树有至多 n 加上块数个节点。

实现指南

给每个原点预留圆方树编号 1..n；新方点从 n+1 起编号，弹出一块才分配。
弹栈时收集边的两个端点；对每个不同端点 v，加圆方树边 square-v。
用时间戳数组去重“本块出现的端点”，不要为每块清空 O(n) 的集合。
根是否是割点的判定需要 DFS 儿子数；但边栈的点双块弹出仍按 low[child] ≥ dfn[parent] 执行。
孤立点没有边栈块；题目若要把它放进圆方树，可只保留孤立圆点。不要无依据地造一个方点。

纸上模拟：让边栈真的开一次账

按邻接顺序 A→B→C→D→E→F→G DFS。先在纸上补全表；返祖边 E-C 和 C-A 是最关键的两笔。

返回的孩子边	low[孩子]	与父亲 dfn 比较	弹出的边	新方点
D-E
C-D
F-G
C-F
A-B

展开：一份可核对的边栈流水线

E 经返祖边回到 C，所以 low[E]=dfn[C]；D 返回 C 时 low[D]=dfn[C]，弹出 C-D、D-E、E-C，得到 CDE。G 返回 F 时弹 FG；F 返回 C 时弹 CF。C 还能经 C-A 回到 dfn[A]，所以 B 返回 A 时才弹 A-B、B-C、C-A，得到 ABC。每一批弹出的边只交给一个方点。

接着在你画出的圆方树上圈出 A 到 E、D 到 G 两条路径。问自己：若原图某条块内边替换成另一条块内边，圆方树路径会变吗？不会；圆方树刻意忘掉了块内部细节，只保留“从哪个门进、从哪个门出”的结构。

互动小实验室

运行从共享房间到圆方树.py。它会先请你预测删 C 的结果，再打印边栈的压入、弹出和生成的方点。可输入：

show：查看原图、点双块和圆方树邻接表；
delete C：用朴素 DFS 验证删点后的连通块；
path A G：查看圆方树上两圆点的路径；
trace：重新逐步打印 Tarjan 的账本。

先预测 Q1 到 Q4 中哪一个方点会连接 C，再运行；程序只是验算员，不会替你补纸上的箭头。

扩展与联系

圆方树也叫块割树；“圆/方”只是方便画图的称呼，不代表图论中另一个神秘对象。
边双连通分量彼此不共享原点，缩成桥树即可；点双块共享割点，才需要额外方点。
块内若要继续处理最短路、计数或 DP，圆方树不足以代替原图；它只保存块与块之间的骨架。
动态加删边会改变点双块边界，静态 Tarjan 与静态圆方树不能直接维护。

总结与自检

为什么方点代表点双块、圆点仍代表原图顶点？
两个点双块为什么至多共享一个原点？
low[child] ≥ dfn[parent] 的一句人话是什么？
为什么边栈比顶点栈适合提取点双块？

自检答案

方点把可重叠的“成员关系”外置；共享两个点会使两块合并；孩子子树无法绕到父亲上方；割点可以反复属于不同块，边却恰好只交给一个块。

一周预热安排

第 1 天：在两三角形共一点的图上暴力删点，写下连通块。
第 2 天：手建 Q1、Q2、Q3、Q4，沿圆方树回答必经门口。
第 3 天：只模拟一次边栈的压入和第一次弹块。
第 4 天：运行互动程序，比较暴力删点和 low 的结账时刻。
第 5 天：进入割点、点双连通分量与圆方树入口正式课。

00-课前零食-从共享房间到圆方树.md 12 KB Пермалинк Историја Датотека