lessons/课程/02-强连通与双连通/03-割点点双连通与圆方树入口.md

割点、点双连通分量与圆方树入口

若“一个点为什么能属于多个块”还没有画清，先完成 课前零食：从共享房间到圆方树。它从暴力删点、边栈结账走到圆方图，附有可操作的 Python 验算。

本节目标

学完后，你应能判断割点（articulation point），用边栈提取点双连通分量（vertex-biconnected component, v-BCC），区分点双与边双，并理解为什么点双分量重叠于割点、需要用圆方树表达。

前置知识与课前自测

前置：无向 DFS、上一节的桥与 dfn/low。

1. low[v] >= dfn[u] 与 low[v] > dfn[u] 分别对应什么？
2. DFS 根只有一个儿子时，即使满足前式，为什么不是割点？
3. 两个点双分量能共享几个原图顶点？

自测答案

1. 前者说明子树无法绕过 $u$ 到达更早祖先，对应割点/点双边界；后者说明连 $u$ 也回不到，对应桥。 2. 删除根后唯一子树内部仍连通，没有被分成两块；根需至少两个 DFS 儿子。 3. 至多一个；若共享两个点，两块可经这两点互相形成删任一点仍连通的更大点双分量。

问题动机与步步推导

逐个删点再检查连通性需要 $O(V(V+E))$。在 DFS 树中，非根点 $u$ 是割点，当且仅当存在儿子 $v$ 使

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

此时 $v$ 子树不能绕过 $u$ 到达 $u$ 的祖先，删掉 $u$ 就把它隔开。根没有祖先，判据改成“DFS 树儿子至少两个”。

若还要取出点双分量，只标割点不够。每次走树边或指向祖先的返祖边时，把边编号压栈；当 low[v] >= dfn[u] 时，从栈顶弹到树边 $(u,v)$，这些边及其端点组成一个点双分量。

为什么用边栈而不是点栈？割点属于多个点双分量，不能在第一次弹出后永久删除；边却恰属于一个这样的块。

核心知识

三类概念对照

概念	删除对象	块之间怎样相交	典型缩点结构
强连通分量	有向可达	点不重叠	DAG
边双连通分量	删除一条边仍连通	点不重叠	桥树/森林
点双连通分量	删除一个点后仍保持块内连通	可共享割点	圆方树/块割树

圆方树中，原顶点作为圆点，每个点双分量新建方点，并连接方点与属于该分量的原顶点。原图连通时得到一棵树；路径问题由“必须经过哪些割点”转成树路径问题。

正确性与复杂度

对树边 $u-v$，若 low[v] < dfn[u]，子树能绕过 $u$ 回到更早祖先，不在此处封闭。若 low[v] >= dfn[u]，从该树边之后压入的边无法与更早边共同处于一个更大的点双分量，应在这里恰好弹出。每条边压栈、弹栈至多一次，总时间 $O(V+E)$，空间 $O(V+E)$。

实现指南与常见错误

• 无向边按 edge_id 跳父边；重边不能按父顶点全部跳过。
• 只把 dfn[v] < dfn[u] 的已访问边压栈，避免同一无向边压两次。
• 非连通图要从每个未访问点启动 DFS。
• 单独一个点是否算点双分量依题意而定；以边为对象的题通常只处理含边分量。
• $10^5$ 深链可能触及递归栈限制；本节第二题代码为清晰展示边栈边界采用递归，实际环境若栈较小需改显式栈。

精选例题 1：Network

来源信息与题意

• VJudge：POJ-1144 Network
• 原来源：Central Europe 1996
• 大致难度：割点入门；考点：根特判、按行读取邻接表

每组给一张连通无向电话网络，$N<100$。某交换站失效后，若除它自身外还造成其他站之间不能通信，则该站是关键点。求关键点数量。输入的每行以一个点开头，后接与它直接相连的点；单独一行 0 结束本组，$N=0$ 结束输入。

Hint 1

关键点就是割点。

Hint 2

非根用 `low[child] >= dfn[u]`；根必须有至少两个 DFS 儿子。

Hint 3

输入必须用 `getline` 按行解析，不能只靠固定个数循环。

Observations、Editorial 与证明

从任一点 DFS。对非根 $u$，若某儿子子树无法连接到 $u$ 的祖先，删 $u$ 后该子树与其余图断开；反之每个儿子都能绕到祖先，删 $u$ 后仍可汇合。根只有多个独立儿子时才会造成分裂。标记后计数即可，复杂度 $O(N+M)$。

核心伪代码与参考实现附件

DFS(u, parent_edge):
    dfn[u] = low[u] = next_time()
    for each edge u-v except parent_edge:
        if v unvisited:
            DFS(v); low[u] = min(low[u], low[v])
            if u is non-root and low[v] >= dfn[u]: mark u as cut
        else: low[u] = min(low[u], dfn[v])
    root is cut iff it has at least two DFS children

完整 GNU C++17 参考实现见附件：POJ-1144.cpp

复盘与变式

若要输出“删除该点后增加多少个连通块”，非根应统计满足判据的儿子数并结合原图连通块；不能只用一个布尔标记。

精选例题 2：Simple Cycles Edges

来源信息与题意

• VJudge：CodeForces-962F Simple Cycles Edges
• 原题：Educational Codeforces Round 42
• 难度：2400；考点：点双分量、环结构判定、边编号输出

给定可不连通的简单无向图，$1\le n\le10^5$，$0\le m\le\min(n(n-1)/2,10^5)$。求恰好属于一个简单环的边，按编号递增输出。

Hint 1

先把边按点双连通分量分组；一条边的所有简单环都局限在它所在的块。

Hint 2

一个含 $V_c$ 个点、$E_c$ 条边的点双块若 $E_c=V_c$，它就是一个简单环。

Hint 3

当 `low[v] >= dfn[u]` 时，从边栈弹出一个完整块并统计不同端点数。

Observations

1. 桥属于零个环，单独形成的二点一边块不满足 $E_c=V_c$。
2. 一个简单环有相同数量的点和边，每条边只在这个环中。
3. 点双块若比简单环多边，则存在额外耳路径；块中每条边都能参与不止一种简单环，不能入选。

Editorial 与正确性

Tarjan DFS 时维护边栈，每遇到点双边界就弹出一块。用时间戳数组统计该块不同端点数；若边数等于点数，把块中全部边加入答案。

每条简单环完全包含在一个点双分量中。若块满足 $E_c=V_c$，点双连通迫使每点度数至少 2，而度数总和为 $2E_c=2V_c$，所以每点度数恰为 2，整块就是一个简单环。若 $E_c>V_c$，点双块含额外耳结构，使其中边不可能只属于唯一简单环。故筛选充要。复杂度 $O(n+m)$。

核心伪代码与参考实现附件

during undirected Tarjan, push tree/back edge IDs on a stack
when low[child] >= dfn[parent]:
    pop through the parent-child edge to obtain one vertex-biconnected block
    vertices = distinct endpoints of popped edges
    if number_of_edges == number_of_vertices:
        add every block edge to answer
sort and output answer edge IDs

完整 GNU C++17 参考实现见附件：CodeForces-962F.cpp

复盘与变式

识别信号是“边属于多少个简单环”，它比单纯判桥更细，需要看边所在点双块的整体结构。若图允许重边，两个点两条平行边是否按题目定义构成长度 2 环必须先确认，不能直接沿用简单图结论。

高阶扩展：Orientable as Desired——点双块控制局部自由度

来源信息、题意与范围

• VJudge：AtCoder-agc071_c Orientable as Desired
• 原题：AtCoder Grand Contest 071 C
• 官方难度口径：1100 分；考点：二分图、边栈点双分解、完备子集和判定

对每个简单连通无向图 $G$，问是否存在 $0\le X_v\le\deg(v)$，使得无论怎样给边定向，都至少有一个顶点 $v$ 同时不满足 $\operatorname{in}(v)=X_v$ 与 $\operatorname{out}(v)=X_v$。测试总 $\sum N,\sum M\le2\times10^5$。

量词顺序必须写清：我们先选整组 $X$，对手再尝试找一种方向；题目询问能否让对手对所有方向都失败。

Hint 1：先试 X 全为 0

若图含奇环，不可能把每个点都变成“入度为 0 或出度为 0”：那等价于用源点/汇点二染奇环。因此非二分图立即存在一组坏死所有定向的 $X$。

Hint 2：固定一个点，只改变 X_v

令其余 $X_u=0$。同一个点双块中与 $v$ 相接的边，在源/汇交替定向里必须整组选择同一侧；不同点双块才可独立翻转。

Hint 3：哪些组大小能拼出所有数

把 $v$ 在各点双块中的关联边数排序为 $c_1\le\cdots\le c_k$。从可达区间 $[0,S]$ 出发，下一组不留下空洞当且仅当 $c_i\le S+1$。

Observations

1. 枚举 $X$ 有 $\prod_v(\deg(v)+1)$ 种，枚举方向有 $2^M$ 种；先用 $X=0$ 试探，量词博弈立刻暴露二分性。
2. 桥不是“特殊失败边”，而是只含一条关联边的点双块，给固定顶点贡献组大小 $1$；这使树上总能逐点选择方向。
3. 点双块的作用不是判环本身，而是刻画“在顶点 $v$ 看来哪些关联边无法独立翻转”。分解后，局部可实现入度集合恰是组大小的子集和。

Editorial 与正确性证明

官方结论的反面更容易判定：不存在题目所求 $X$，当且仅当：

1. $G$ 是二分图；
2. 对每个顶点 $v$，其各点双块内关联边数 $c_1,ldots,c_k$ 能用子集和表示 $0$ 到 $\deg(v)$ 的每个整数。

必要性：若图有奇环，取 $X=0$ 即可让所有定向失败。若固定 $v$ 的组大小无法拼出某个 $x$，取 $X_v=x$、其余为 0；其余点要满足 0，就必须成为源或汇。在一个点双块里，沿偶环传播后，$v$ 的同组边只能整组入或整组出，于是 $x$ 不可实现。

充分性：先看树。根到叶处理，每个点只有父边方向已定，其余子边可补出任意要求的入度或出度。一般图的块割树仍是一棵树；把一个点双块视为树上的“粗边”。原图二分保证块内可按两侧统一源汇定向，而条件 2 保证在割点处能选若干整组凑出所需数量，于是对任意 $X$ 都能逐块构造一种满足方向，题目所求的反例 $X$ 不存在。

排序后，组大小能覆盖所有 $[0,\sum c_i]$ 的充要条件是：初始 $S=0$，每次有 $c_i\le S+1$，再令 $S\leftarrow S+c_i$。若 $c_i>S+1$，数 $S+1$ 无法表示；反之新区间 $[0,S]$ 与 $[c_i,c_i+S]$ 无缝相接。点双分解 $O(N+M)$，所有组排序总计 $O(M\log M)$。

实现指南、伪代码与附件

bipartite = two_color(G)
blocks = vertex_biconnected_edge_blocks(G)  // Tarjan edge stack
for each block:
    count how many popped edges touch each incident vertex v
    append that count to groups[v]
complete = True
for each vertex v:
    sort(groups[v]); covered = 0
    for c in groups[v]:
        if c > covered + 1: complete = False
        covered += c
answer = not (bipartite and complete)

点双块中的 $c$ 是关联边数而非块的顶点数。连通简单图仍应按边编号维护父边；附件用迭代 DFS，避免链图深度 $2\times10^5$ 爆栈。完整 GNU C++17 实现：AtCoder-agc071_c.cpp

复盘与变式

识别信号是“方向选择在环中传播、但在割点处分组独立”。若要求实际输出那组 $X$，在发现奇环时可取全 0；在覆盖断点 $S+1$ 时令该点取 $S+1$、其余取 0。若图允许重边，二边环也属于点双结构，父边必须按边号跳过。

扩展与联系

• 圆方树把一个割点在多个点双块中的“重叠”变成树上的多条边，适合必经点计数与路径查询。
• 边双看“边是否能绕”，点双看“顶点是否能绕”；两者的 low 判据只差等号，却对应不同删除模型。
• 若要处理动态加边后的双连通性，静态 Tarjan 不再直接适用，通常需要离线、并查集或更强的动态结构。

总结与自检

1. 非根割点、根割点的判据分别是什么？
2. 为什么点双分量用边栈提取？
3. 点双分量为什么不能像边双那样直接把原点互不重叠地缩掉？
4. Simple Cycles Edges 中 $E_c=V_c$ 为什么推出块是一个环？

课后训练建议

先对拍割点：随机删点比较剩余连通块数。再手画“两个环共一个点”和“两个环共一条边”的图，分别列出点双块。第二题卡住时按 Hint 逐级展开，复盘重点是从“恰一个环”转成“点双块的边数等于点数”。