块—顶点森林与单点失效查询

路口 3 是割点，不等于“删去 3 后，任意两个路口都不通”。同在一个三角区域里的 4 和 5 仍然连通，从左侧区域的 0 到右侧区域的 8 却不行。要回答这种带端点的问题，需要知道各个块怎样相接。本条目把接合关系变成一片森林，再把“故障会不会挡路”变成“故障顶点是否在唯一树路径上”。

形式陈述

输入是已经完成点双连通边块分解的静态、无自环无向多重图 $G$ 。记原顶点数为 $n$ ，边数为 $m$ ，连通分量数为 $c$ ，边块数为 $b$ 。每个块至少含两个顶点；孤立点不属于边块。

构造关联图 $F$ ：保留全部 $n$ 个原顶点，并为每个块 $B_i$ 新建一个节点 $n+i$ ；当且仅当原顶点 $v$ 属于块 $B_i$ ，连一条无向边 $vB_i$ 。同一块中的平行边不会生成重复的关联边。 $F$ 是森林，它和 $G$ 有同样的 $c$ 个连通分量。

常见的“块—割点树”只保留块节点与割点节点，把非割点原顶点映射到所属块。这里刻意保留所有原顶点：非割点是块节点旁的叶子，孤立点仍是孤立节点。这样查询端点和故障点都保留原编号，不需要按顶点种类切换映射。

索引提供两个接口，每次查询都从原图独立出发，不会累积前一次故障：

$\operatorname{connected\_without}(u,v,x)$ ：删除原顶点 $x$ 及其关联边后，原顶点 $u,v$ 是否都还存在且连通。
$\operatorname{components\_without}(x)$ ： $G-x$ 的连通分量数。

第一个接口先处理三项边界：若 $x=u$ 或 $x=v$ ，返回假；若 $u,v$ 原本不同分量，返回假；若 $x$ 不在它们的分量，返回真。剩下的情形，三者在同一棵关联树中且端点不被删除，于是

\operatorname{connected\_without}(u,v,x) \iff d_F(u,v)\ne d_F(u,x)+d_F(x,v).

这里 $d_F$ 是关联森林中的无权边数，不是原图最短路长度。用最近公共祖先可计算

d_F(a,b)=\operatorname{depth}[a]+\operatorname{depth}[b] -2\operatorname{depth}[\operatorname{LCA}(a,b)].

第二个接口更简单：

\operatorname{components\_without}(x)=c+\deg_F(x)-1.

包括孤立点在内，这个式子都成立。所有接口只接受合法的原顶点编号；空图可建索引，但没有合法的删点查询。

直觉

把一个没有割点的区域画成一个块节点，是说“这个区域内部能承受一次顶点删除”：只要进出端点没有被删，区域内仍有路可走。相反，两个块之间共用的路口无法被块内部的绕路替代。

于是原图中许多不同走法，在关联森林里变成同一条路线。删除 $x$ 能挡住 $u$ 到 $v$ ，恰好是因为这条唯一的路线必须经过原顶点节点 $x$ 。树上两段距离之和等于整段距离，就是“位于路径上”的算术版本；若要绕去一个不在路径上的顶点，再回来，就会多走一段。

全顶点关联森林中，0 到 8 的路径经过割点 3；4 到 5 只经过块 B0，因而删除 3 不会切断这两个端点。另画出边块 B5 和孤立点 11 — 单点失效化为关联树路径阻断

例子与边界

沿用边栈条目的图和块编号：

\begin{aligned} B_0&=\{3,4,5\}, & B_1&=\{7,8\}, & B_2&=\{3,6,7\},\\ B_3&=\{2,3\}, & B_4&=\{0,1,2\}, & B_5&=\{9,10\}. \end{aligned}

这里写的是各块的顶点集。原图有三个连通分量： $0$ 至 $8$ 、 $\{9,10\}$ 、孤立点 $11$ 。关联森林有 $12+6=18$ 个节点、 $18-3=15$ 条边。

$0$ 到 $8$ 的唯一关联路径是

0-B_4-2-B_3-3-B_2-7-B_1-8,

长度为 8。删除 3 时， $d_F(0,3)=4$ 、 $d_F(3,8)=4$ ，相加正好为 8，所以不通。删除 1 时，两段距离是 2 和 8，总和为 10，所以仍通；原图中可以走 $0-2-3-7-8$ 。

然而 $4$ 到 $5$ 的关联路径只是 $4-B_0-5$ 。它长 2，而绕经 3 的两段距离都是 2，总和为 4；因此即使 3 是全图割点，删去它仍不影响 $4,5$ 。原图恰好还有直接边 $(4,5)$ 。

查询 $(u,v,x)$	结果	原因
$(0,8,7)$	假	长度 $8=6+2$ ，路径经过 7
$(0,1,2)$	真	路径 $0-B_4-1$ 不经过 2
$(8,8,7)$	真	同一个幸存顶点到自身连通
$(8,8,8)$	假	端点已被删除，不能用零距离返回真
$(0,10,3)$	假	两端原本不在同一分量
$(9,10,3)$	真	故障发生在另一个分量
$(11,11,3)$	真	孤立点 11 仍然存在

再看分量数。原顶点 $2,3,7,11,9$ 在关联森林里的度数分别为 $2,3,2,0,1$ ，删去它们后的分量数分别是 $4,5,4,2,3$ 。孤立点被删时，原来的一整个分量消失；因此结果减少 1，而不是保持不变。

不能把两次单点查询合成一次双点查询。四边形 $0-1-2-3-0$ 是一个块。单独删除 1 或单独删除 3， $0,2$ 都还连通；同时删去 1 和 3，却会断开。块能承受一次顶点删除，并不承诺承受两次。把两个单点答案取“且”会在这个最小例子上出错。

推论与应用

关联图为什么是森林？两个不同块不能共享两个顶点：否则删去任意一个顶点后，至少还保留一个共同顶点，两个块的并仍连通，于是它们的并没有割点，违背极大性。进一步，若块与接合顶点交替组成一个环，删去环上任一接合顶点，还可以沿环的另一侧连接相邻块；删去其他顶点，则由所在块没有割点保证接通。环上块的并同样没有割点，也违背极大性。因此关联图无环。

原图一条边 $(a,b)$ 总在某个块 $B$ 内，可以替换为关联图里的两步 $a-B-b$ ；反过来，关联图中两步 $a-B-b$ 可以换成块内部的一条路径。沿途拼接这些片段，说明 $G$ 与 $F$ 的连通关系完全相同。孤立点也被原样保留，所以二者有相同的 $c$ 个分量。

为什么删点可以只看树路径？两个方向都要证明。

如果 $G-x$ 中有一条 $u$ 到 $v$ 的路，把每条边换成“原顶点—块—原顶点”的两步，就得到一条不经过原顶点节点 $x$ 的关联游走。删去游走中的往返段，剩下的唯一树路径也不经过 $x$ 。
如果关联树的 $u$ 到 $v$ 路径不经过 $x$ ，看其中每一段 $a-B-b$ 。两个原顶点端点都不是 $x$ ；若 $x$ 在块内，由块没有割点知 $B-x$ 仍把 $a,b$ 接通；若不在块内，更不受影响。选取这些块内路径并拼接，必要时消去回路，就得到 $G-x$ 中的路径。二顶点块也没有例外：若它的端点被删，该关联路径早已不满足避开 $x$ 的前提。

距离判据因此是精确等价，不只是割点的充分条件。它还说明：原顶点 $x$ 是割点，当且仅当 $\deg_F(x)>1$ 。

分量数公式如何覆盖孤立点？删除 $x$ 后，关联树原来所在的一个分量变成 $\deg_F(x)$ 支；每支至少含一个幸存原顶点，因为邻接块至少还有另一个端点。上一段的路径等价说明这些支恰好对应原图剩下的分量。其他 $c-1$ 个分量不变，故总数是 $c-1+\deg_F(x)$ 。若 $x$ 孤立，度数为 0，原来的那个分量直接消失。

空间会随原图的稠密程度膨胀吗？设 $N=n+b$ 。森林有 $N-c$ 条边，每个块节点的度数至少为 2，所以

2b\le N-c=n+b-c, \qquad b\le n-c,\qquad N\le2n-c.

因此关联森林只有 $O(n)$ 个节点和边，即使原图有很多平行边或稠密区域也一样。不过输入及完整的边块输出仍占 $O(m)$ ，不能把它们从端到端空间账里抹去。

边块分解与森林构造用 $O(n+m+1)$ 时间。对每棵树用显式栈求父节点、深度、分量号，再建立二进制倍增祖先表，需要 $O(n\log(n+1)+1)$ 时间与空间。连同输入和边块列表，端到端时间与空间上界均为 $O(m+n\log(n+1)+1)$ 。对合法查询（因此 $n\ge1$ ），三次 LCA 给出最坏 $O(\log(n+1))$ 的连通性查询；分量数查询只读一个度数，最坏 $O(1)$ 。这些是静态数组上的确定性界。

终端任务会把森林路径、删点后的真实搜索和分量数放在一起核对。参考实现另有展开整条森林路径的诊断接口，那要按输出路径长度计时；它不包含在对数查询承诺中，也没有直接输出原图绕行路线。原图增删边或顶点后，应重建当前索引，本接口没有动态维护或多点失效的保证。

参考资料

OGDF，BCTree 官方文档，尤其是 Detailed Description、BComp/CComp 与原图节点映射接口。说明传统块—割点树及非连通图的森林构造。本文保留所有原顶点的表示，是在传统表示上接回非割点叶子、保留孤立点；单点失效判据与分量数公式在正文单独证明。
John E. Hopcroft、Robert E. Tarjan，Efficient Algorithms for Graph Manipulation，STAN-CS-71-207，1971，印刷页 3–4。原报告扫描件。关联森林的输入来自报告所述的线性边块分解；该报告并不直接提供本文的 LCA 查询接口。

形式陈述 ​

反向链接

形式陈述