我的算法书 - 割点

一句话算法

割点判定看 low[v] >= dfn[u]：如果子树 v 回不到 u 的祖先，那么 u 就是这棵子树通向外界的关口。

问题模型

给定一张无向图。删除某个点以及与它相连的边后，如果图的连通块数量增加，那么这个点叫做割点。

割点反映的是网络中的关键节点：

删除它会让某些点互相不可达；
它常用于无向图连通性分析、网络脆弱点判断、点双连通分量。

核心直觉

DFS 形成一棵搜索树。对一条树边 u -> v：

dfn[u] 是 u 第一次被访问的时间；
low[v] 是 v 的子树通过返祖边能回到的最早祖先。

如果：

low[v] \ge dfn[u]

说明 v 的子树最多只能回到 u，回不到 u 的父亲或更早祖先。删除 u 后，v 的子树就被切开。

根节点需要特殊判断：DFS 根没有父亲，只有当它有两个及以上 DFS 子树时，它才是割点。

算法步骤

对每个未访问的点作为 DFS 根。
进入点 u 时，令 dfn[u] = low[u] = ++timer。
枚举邻点 v：
- 如果 v 未访问，递归 DFS；
- 回溯后用 low[v] 更新 low[u]；
- 若 u 不是根且 low[v] >= dfn[u]，标记 u 为割点。
如果 v 已访问且是祖先，用 dfn[v] 更新 low[u]。
DFS 根如果有超过一个 DFS 子树，标记为割点。

算法证明

核心不变量：low[u] 表示 u 的子树通过树边和最多一条返祖边能到达的最早时间戳。

初始化时，low[u] = dfn[u]，表示至少能到自己。
遇到未访问子节点 v，v 子树能到达的最早祖先也能被 u 使用，所以 low[u] = min(low[u], low[v])。
遇到祖先 v，边 (u,v) 是返祖边，所以 low[u] = min(low[u], dfn[v])。
若 low[v] >= dfn[u]，说明 v 子树不能绕过 u 回到更早祖先。删除 u 后，v 子树与外部断开，因此 u 是割点。
根节点没有“外部祖先”，只有当它有两个及以上 DFS 子树时，删除根才会让这些子树互相断开。

因此判定条件正确。

复杂度分析

设点数为 $n$ ，边数为 $m$ 。

时间复杂度： $O(n+m)$ 。
空间复杂度： $O(n+m)$ ，取决于图存储和递归栈。

代码实现

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

        struct TarjanCut {
    int n, timer; // timer 对应你代码中的 cnt
    int dfn[maxn], low[maxn];
    bool is_cut[maxn]; // 标记是否为割点 (对应 cut[])
    int root; // 当前 DFS 树的根节点

    void set(int _n) {
        n = _n;
        timer = 0;
        memset(dfn, 0, sizeof(dfn));
        memset(low, 0, sizeof(low));
        memset(is_cut, 0, sizeof(is_cut));
    }

    /*
     * u: 当前节点
     * fa: u 的父节点 (防止走回头路)
     */
    void dfs(int u, int fa = -1) {
        dfn[u] = low[u] = ++timer;
        int child = 0; // 记录 root 在 DFS 树中的子节点数量

        for (int i = e.h[u]; ~i; i = e[i].next) {
            int v = e[i].v;

            // 不走父子边
            if (v == fa) continue;

            // v 没有被访问过，是树边
            if (!dfn[v]) { 
                child++;
                dfs(v, u); // 【注意】这里必须传 u，表示 v 的父亲是 u

                // 回溯时用子节点的 low 更新当前节点的 low
                low[u] = std::min(low[u], low[v]);

                // 割点判定情况 2: 非根节点
                // 如果子节点 v 无法回到 u 的祖先 (low[v] >= dfn[u])
                // 说明 u 是连接 v 子树和其他部分的必经点
                if (low[v] >= dfn[u] && u != root) {
                    is_cut[u] = true;
                }

                // 处理返祖边
                // 注意:v可能是u的父亲,但没有关系,最多low[u] == dfn[fa[u]]
                // dfn[v] < dfn[u] 说明v是u的祖先,
                // 在无向图上其实不可能 dfn[v] > dfn[u]
                // 因为: v 是一个已经访问过的点, 如果dfn[v] > dfn[u] 说明u是v的祖先, 那么v在u的子树上,
                // 根据dfs 的性质, 应该先访问u, 再访问v,但此时v已经被访问, 所以不可能出现dfn[v] > dfn[u]的情况
            } else if( dfn[v] < dfn[u] ) {
                // v 已经被访问过，是返祖边 (Back Edge)
                // 用 v 的 dfn 更新 u 的 low
                low[u] = std::min(low[u], dfn[v]);
                // 注意：有些版本写成 min(low[u], low[v]) (对于已访问的 v) 是错误的。
                // 对于返祖边，只能取 dfn[v]，因为 low[v] 可能包含从 v 回到更上层的路径，
                // 而边 (u, v) 并不代表 u 可以通过 v 再跳跃回去（除非有其他边）。
            }
        }

        // 割点判定情况 1: 根节点
        // 如果根节点在 DFS 树中有两个及以上的子节点，则它是割点
        if (u == root && child > 1) {
            is_cut[u] = true;
        }
    }

    void solve() {
        // 遍历所有点，防止图不连通
        for (int i = 1; i <= n; i++) {
            if (!dfn[i]) {
                root = i; // 记录当前连通块的 DFS 根
                dfs(i, 0); 
            }
        }
    }
    
    // 辅助函数：获取所有割点
    std::vector<int> get_cuts() {
        std::vector<int> cuts;
        for (int i = 1; i <= n; i++) {
            if (is_cut[i]) cuts.push_back(i);
        }
        return cuts;
    }
};

测试用例

输入图：

割点是：

2 3

删除 2 后，点 1 与 3,4,5 断开；删除 3 后，点 4、5 与前半部分断开。

应用分类详解

割点用于识别无向图中的关键点。

一、网络脆弱点

典型模式： 删除某个节点后，连通性变差。

识别信号： 题面出现“关键城市”“通信站”“删除点后不连通”。

核心建模： 把对象看作点，连接关系看作无向边，求割点。

应用场景	经典题目	核心思路
割点模板	luogu-P3388	Tarjan 求所有割点
通信网络关键点	网络可靠性题	删除点后连通块增加

二、点双连通分量的入口

典型模式： 求每个点双，或者分析哪些点属于多个点双。

识别信号： 出现“点双连通”“任意两点有两条点不重复路径”。

核心建模： 割点是点双之间的连接处。

经典例题

1. luogu-P3388

割点模板题。重点是根节点特判和 low[v] >= dfn[u]。

2. poj-1144

求通信网络中的割点数量。适合练习非标准输入格式。

3. 点双连通分量模板

割点是理解 v-BCC 的前置知识。继续学习本书点双连通分量章节。