沿块分解与失效查询路线，把边栈分解理路点双连通块与边栈分解Vertex-biconnected blocks · Biconnected edge-block decomposition · 点双连通分量在无自环无向多重图的 DFS 中维护未归属边栈，在线性时间内输出以边为划分、以割点为接合处的全部点双连通块。的输出交给块—顶点森林索引理路块—顶点森林与单点失效查询Block-cut forest failure index · Block-vertex incidence forest · 单点失效连通性索引把点双连通块与原顶点组成关联森林，用树路径判定一次指定顶点失效后的两点连通性，并以原顶点的森林度数计算剩余分量数。。交付物不是一张割点名单，而是一份能解释每次弹栈、每条查询和每个边界结果的账本。

下载完整标准库参考程序，运行 python algorithms-block-cut-failure-check.py。它只把一份JSON写到标准输出，不修改图文件；其中含完整输入、DFS状态、压栈与出块事件、森林邻接表、12条查询、5条分量数查询及自动检查范围。再以 python -O 运行，结果应逐字相同。若需保存结果，由运行者自行重定向输出。

一、固定多重边与孤立点的输入合同 ​

建立12个顶点 $0,\dots ,11$，以下列表的位置就是边编号：

0:(0,1)   1:(1,2)   2:(2,0)   3:(2,3)
4:(3,4)   5:(4,5)   6:(5,3)
7:(3,6)   8:(6,7)   9:(7,3)
10:(7,8)  11:(7,8)  12:(9,10)

端点按列表顺序加入两个方向的邻接表。DFS每次从最小未访问顶点开始。顶点11是孤立点；边10和11是两条独立道路，不能因端点相同只留一条。

交付一份输入检查说明：顶点数为非负整数，端点在范围内，允许空图和平行边，拒绝自环。参考器使用严格整数类型，True不能充当顶点0或1。图构造会复制输入，随后修改调用者的原列表，不得改变已经建好的图。

还要明确删除语义：connected_without(u,v,x)询问一次独立的假设故障，不永久删去x。若x就是端点，答案是假，即使u与v原来相同。多次调用不能被当成不断积累的删除序列。

二、交出边栈，而不只交出low数组 ​

复算发现顺序、父顶点与最终low。应得到 tin[v]=v，以及

low = [0,0,0,3,3,3,3,3,7,9,10,11]
parent = [null,0,1,2,3,4,3,6,7,null,9,null]

将每次 push-tree、push-back 和 emit 连成事件序列。至少逐项解释两段：

• $4\to 3$ 返回之前，边栈底到顶为 [0,1,2,3,4,5,6]；$low[4]=tin[3]=3$，弹出 [6,5,4]，余下 [0,1,2,3]
• $8\to 7$ 返回之前，边栈为 [0,1,2,3,7,8,9,10,11]；父边10被跳过，但平行边11从8返向7，令 $low[8]=7$；弹出 [11,10]

完整出块顺序应为：

所有边编号0至12必须恰好出现一次。孤立点11没有空边块；割点3可以同时出现在三个块中。另交割点 [2,3,7] 与桥 [3,12]，解释为何根0有两个图邻点却只有一个DFS孩子。

最后分别证明三件事：出栈段连通且没有割点；它已经极大；每条边最终且仅最终输出一次。只证明“low能找到割点”尚未证明边栈分解正确。

三、把块转成森林，并核对完整查询 ​

原顶点仍用0至11；块节点 $B_i$ 用整数 $12+i$。每个块与它包含的不同原顶点各连一次，因此全森林有18节点、15条边、3个分量。平行边块 $B_1$ 只连7和8，不因为有两条道路而重复两条关联边。

画出

并补齐叶子1、4、5、6、独立的 $9-B_5-10$ 和孤立点11。参考输出的上述主路径整数形式是 [0,16,2,15,3,14,7,13,8]。

对下表逐行提交：是否先被边界条件决定；若三者在同一树中，提交三个关联距离；再从原图真的删去x并搜索验证。距离列按 $[d(u,v),d(u,x),d(x,v)]$ 排列。

挑两条“真”的不同理由，交出原图路径。例如删1后的 $0-2-3-7-8$，以及删3后的直接边 $4-5$。这些是真实道路，不要把块节点 $B_i$ 当成原图里可以经过的新路口。

四、从关联度数计算删点后的分量数 ​

原图有 $c=3$ 个分量。逐个删去以下顶点，既用公式又真正枚举剩下的分量：

删去3时，剩下的五组应为 $\{0,1,2\}$、$\{4,5\}$、$\{6,7,8\}$、$\{9,10\}$、$\{11\}$。删去孤立点11使分量总数减少1；度数为0不能硬按“至少留下一组”计数。

说明公式为什么能用关联森林的度数，而不是原图度数。原图3关联五条道路，却只接合三个块；一块内部的多个邻点在删3后仍然连通，不能一条路算一支。证明每个关联分支含有幸存原顶点，才算完成分量数论证。

五、改变编号，区分表示变化与数学变化 ​

先把边列表完全反序，再把顶点按置换 $p(v)=11-v$ 重命名；旧边e的新编号为 $12-e$。重建DFS和索引。发现时刻、low数值、出块编号与出栈顺序都可能改变。把新边编号映射回旧编号后，块的边集合族应仍是第二节那六组；割点映回后仍为2、3、7，桥映回后仍为3、12。

把第三节每条查询也按p变换，答案必须保持。不要用“新输出的 $B_0$ 必须等于旧 $B_0$”检验，因为出块次序并不是数学身份。这个迁移同时检验父边身份、DFS根的改变与查询端点重命名。

再分别建立空图、只有一个孤立点的图，以及两个顶点间三条平行边的图。预期边块数分别为0、0、1；删去单孤立点后的分量数为0；三条平行边都应属于同一个块且没有桥。空图可以建索引，但不存在合法的删点查询。

六、给错误规则反例，也给正确检查计费 ​

实际试验以下改动，记录第一次与正确输出分歧的状态，或被不变量拒绝的位置：

1. 跳过所有“邻点等于父顶点”的边。只用两个点、两条平行边就足够：第二条返祖边被错误跳过，low不能降到父时刻，父边被误报为桥，并可能留下未交付的边
2. 仅当 $low[v]>tin[u]$ 才封块。三角形所有根孩子返回都取等号，因此一个完整块也没有输出，分量结束时边栈非空；桥判据不能替代块封闭判据
3. 只要x是全图割点就对所有 $(u,v)$ 返回假。本例 $(4,5,3)$ 立即反驳
4. 把两个单点答案取“且”当成双点答案。四边形 $0-1-2-3-0$ 中，0到2单独删1或删3都通，同时删1和3却不通。参考程序实际运行这个双点越界见证

参考器穷举0至5顶点的全部1,100张简单图、1至4顶点且每对顶点有0/1/2条边的760张多重图，再检查150张固定种子随机图。它用枚举顶点子集、检验连通且无割点并保留极大者的慢算法核对块；用真正删点后的搜索核对208,717个三元查询和各顶点的分量数。还运行5,000顶点长链、6种非法输入和输入复制检查。慢检查不使用low来定义正确答案；有限穷举仍不能代替一般证明。

最后交付一张代价账：邻接表和完整边块输出各按 $n+m$ 量级，DFS帧至多n，未交付边栈至多m；块顶点去重用一次分配的时间戳数组，不能每出一块清空n格。森林有 $N=n+b\le 2n-c$ 节点；倍增预处理用 $O(n\log (n+1)+1)$，连同输入及分解的总成本为 $O(m+n\log (n+1)+1)$。合法连通性查询最坏 $O(\log (n+1))$，分量数查询最坏 $O(1)$。参考器展开路径的输出、指数级块oracle、删点搜索及详细JSON各自收费，不能算进核心查询的对数界。图结构改变就重建；本任务没有承诺动态更新或多故障索引。