本课时有配套视频讲解，购买后即可观看（永久有效）

割点

一、课上练习

编程练习

割点：L49907

二、知识总结

✨ 核心思想

割点（Articulation Point），也称为割顶或关节点，是无向连通图中的一个特殊顶点：删除该顶点及其关联的所有边后，图的连通分量数增加。割点在网络可靠性分析中至关重要——它代表了网络中的"单点故障"节点。

Tarjan 算法利用 DFS 树的性质，通过维护两个数组 dfn（时间戳）和 low（能回溯到的最小时间戳），在一次 DFS 中高效地找出所有割点。

✨ 算法原理

DFS 树与返祖边

对无向图进行 DFS 时，会生成一棵 DFS 树。树中的边称为树边，非树边都是返祖边（连接后代到祖先的边）。

关键定义

dfn[u]：节点 u 被 DFS 访问的时间戳（顺序编号）。
low[u]：节点 u 及其子树中的节点，通过返祖边能到达的最小 dfn 值。

割点判定条件

对于节点 u，在 DFS 树中：

u 是根节点：如果 u 在 DFS 树中有两个或以上的子树，则 u 是割点。因为删除根节点后，各子树之间无法连通。
u 不是根节点：如果 u 存在某个子节点 v，满足 low[v] >= dfn[u]，则 u 是割点。这意味着 v 的子树中没有返祖边能绕过 u 到达 u 的祖先。

low 值的计算

low[u] = min(dfn[u], min(low[v]) 对所有树边子节点v, min(dfn[w]) 对所有返祖边邻居w)

✨ 代码实现

1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 100005;
5vector<int> adj[MAXN];  // 邻接表
6int dfn[MAXN], low[MAXN]; // 时间戳和最小可达时间戳
7bool is_cut[MAXN];        // 标记是否为割点
8int timer_cnt = 0;        // 全局时间戳计数器
9int n, m;                 // 顶点数和边数
10
11// Tarjan 求割点
12void tarjan(int u, int fa) {
13    dfn[u] = low[u] = ++timer_cnt; // 记录访问时间戳
14    int child_count = 0;           // DFS 树中的子节点数
15
16    for (int v : adj[u]) {
17        if (!dfn[v]) {
18            // v 尚未访问，是树边
19            child_count++;
20            tarjan(v, u);
21            low[u] = min(low[u], low[v]); // 用子节点的 low 更新
22
23            // 判定割点条件
24            if (fa == 0 && child_count >= 2) {
25                // 条件1：u 是根且有两棵以上子树
26                is_cut[u] = true;
27            }
28            if (fa != 0 && low[v] >= dfn[u]) {
29                // 条件2：u 非根且子树无法绕过 u
30                is_cut[u] = true;
31            }
32        } else if (v != fa) {
33            // 返祖边，用 dfn[v] 更新 low[u]
34            low[u] = min(low[u], dfn[v]);
35        }
36    }
37}
38
39int main() {
40    ios::sync_with_stdio(false);
41    cin.tie(nullptr);
42
43    cin >> n >> m;
44    for (int i = 0; i < m; i++) {
45        int u, v;
46        cin >> u >> v;
47        adj[u].push_back(v);
48        adj[v].push_back(u);
49    }
50
51    // 处理可能不连通的图
52    for (int i = 1; i <= n; i++) {
53        if (!dfn[i]) {
54            tarjan(i, 0); // 0 表示无父节点（根）
55        }
56    }
57
58    // 输出所有割点
59    vector<int> cuts;
60    for (int i = 1; i <= n; i++) {
61        if (is_cut[i]) cuts.push_back(i);
62    }
63
64    cout << cuts.size() << "\n";
65    for (int x : cuts) {
66        cout << x << " ";
67    }
68    cout << "\n";
69
70    return 0;
71}

✨ 执行示例

以下图为例（5 个节点，5 条边）：

边：1-2, 1-3, 2-3, 3-4, 4-5
图的形状：1,2,3 构成三角形，3 连接 4，4 连接 5

DFS 从节点 1 开始：

步骤	访问节点	dfn	low	说明
1	1	1	1	起始节点
2	2	2	2	树边 1→2
3	3	3	1	树边 2→3，发现返祖边 3→1，low[3]=1
4	4	4	4	树边 3→4
5	5	5	5	树边 4→5

回溯更新：

low[4] = min(4, low[5]) = 4，因为 low[5]=5 >= dfn[4]=4，所以节点 4 是割点
low[3] = 1，low[3]=1 < dfn[2]=2，所以节点 2 不是割点
回溯到 3：low[4]=4 >= dfn[3]=3，所以节点 3 是割点
节点 1 是根，只有 1 棵子树，不是割点

结果：割点为 {3, 4}

✨ 解题步骤详解

建图：读入边的信息，构建邻接表。
初始化：将 dfn 数组清零（用作访问标记），时间戳从 1 开始。
遍历所有连通分量：对每个未访问的节点调用 tarjan()。
DFS 过程中：
- 给当前节点打上时间戳，初始化 low[u] = dfn[u]。
- 遍历邻居：树边递归后更新 low，返祖边直接更新 low。
- 根据是否为根节点，应用不同的割点判定条件。
收集结果：遍历 is_cut 数组输出所有割点。

✨ 常见错误

根节点判断遗漏：根节点的割点条件与非根节点不同，必须分别处理。仅当根节点有 ≥2 棵子树时才是割点。
重边处理不当：用 v != fa 判断返祖边时，如果存在重边（u 和 v 之间有多条边），可能会出错。更严谨的做法是记录边的编号来区分。
low 更新使用 low[v] 而非 dfn[v]：对于返祖边，应使用 dfn[v] 而不是 low[v] 更新。虽然在求割点时两者结果相同，但在求割边时会产生区别，建议养成好习惯。
时间戳从 0 开始：如果 dfn 数组用 0 表示未访问，时间戳必须从 1 开始，否则无法区分。
忘记处理非连通图：如果图不连通，需要对每个连通分量分别运行 Tarjan 算法。

✨ 算法评价

指标	值
时间复杂度	O(V + E)，每个节点和边各访问一次
空间复杂度	O(V + E)，存储图和辅助数组
适用场景	网络可靠性分析、关键节点识别
优势	线性时间，一次 DFS 解决问题
局限	仅适用于无向图

割点算法是图论中的基础工具，也是学习更高级图论算法（如双连通分量、2-边连通分量）的基石。掌握 dfn/low 的含义和更新规则是理解 Tarjan 系列算法的关键。