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

## 本节目标

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

## 前置知识与课前自测

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

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

<details><summary>自测答案</summary>

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

</details>

## 问题动机与步步推导

逐个删点再检查连通性需要 $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](https://vjudge.net/problem/POJ-1144)
- 原来源：Central Europe 1996
- 大致难度：割点入门；考点：根特判、按行读取邻接表

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

<details><summary>Hint 1</summary>关键点就是割点。</details>
<details><summary>Hint 2</summary>非根用 `low[child] >= dfn[u]`；根必须有至少两个 DFS 儿子。</details>
<details><summary>Hint 3</summary>输入必须用 `getline` 按行解析，不能只靠固定个数循环。</details>

### Observations、Editorial 与证明

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

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

```text
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](../../参考实现/02-强连通与双连通/POJ-1144.cpp)

### 复盘与变式

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

## 精选例题 2：Simple Cycles Edges

### 来源信息与题意

- VJudge：[CodeForces-962F Simple Cycles Edges](https://vjudge.net/problem/CodeForces-962F)
- 原题：[Educational Codeforces Round 42](https://codeforces.com/problemset/problem/962/F)
- 难度：2400；考点：点双分量、环结构判定、边编号输出

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

<details><summary>Hint 1</summary>先把边按点双连通分量分组；一条边的所有简单环都局限在它所在的块。</details>
<details><summary>Hint 2</summary>一个含 $V_c$ 个点、$E_c$ 条边的点双块若 $E_c=V_c$，它就是一个简单环。</details>
<details><summary>Hint 3</summary>当 `low[v] >= dfn[u]` 时，从边栈弹出一个完整块并统计不同端点数。</details>

### 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)$。

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

```text
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](../../参考实现/02-强连通与双连通/CodeForces-962F.cpp)

### 复盘与变式

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

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

### 来源信息、题意与范围

- VJudge：[AtCoder-agc071_c Orientable as Desired](https://vjudge.net/problem/AtCoder-agc071_c)
- 原题：[AtCoder Grand Contest 071 C](https://atcoder.jp/contests/agc071/tasks/agc071_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$，对手再尝试找一种方向；题目询问能否让对手对所有方向都失败。

<details><summary>Hint 1：先试 X 全为 0</summary>

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

</details>

<details><summary>Hint 2：固定一个点，只改变 X_v</summary>

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

</details>

<details><summary>Hint 3：哪些组大小能拼出所有数</summary>

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

</details>

### 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)$。

### 实现指南、伪代码与附件

```text
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](../../参考实现/02-强连通与双连通/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 逐级展开，复盘重点是从“恰一个环”转成“点双块的边数等于点数”。