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

## 本节目标

学完后，你应能判断割点（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 环必须先确认，不能直接沿用简单图结论。

## 扩展与联系

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

## 总结与自检

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

## 课后训练建议

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