割点

代码模板

割点的判定与实现：Tarjan 算法求无向图中删除后使图不连通的节点。

  • 图论
  • Tarjan
  • 割点

一句话算法

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

问题模型

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

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

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

核心直觉

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

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

如果：

low[v]≥dfn[u] low[v] \ge dfn[u]

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

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

算法步骤

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

算法证明

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

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

因此判定条件正确。

复杂度分析

设点数为 nn，边数为 mm。

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

代码实现

C++
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;
    }
};
Python
python 
        
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

        # Tarjan 求无向图割点。依赖模块级链式前向星全局 e（本文件内联了最小实现，完整版见 linklist.py）：
#   e.reset(); e.add2(u, v)   # 无向边双向各加一条
#   t = TarjanCut(); t.set(n); t.solve(); cuts = t.get_cuts()
# 非根割点条件 low[v] >= dfn[u]（取等号：v 回不到 u 的祖先）；根割点当且仅当有 ≥2 棵 DFS 子树。
# 点编号 1..n；dfs 递归深度最坏 n（1e5+），使用前需 sys.setrecursionlimit(1 << 20)。

from collections import defaultdict


class Edge:
    """链式前向星的边：v 终点、next 同起点的下一条边编号。"""

    __slots__ = ("u", "v", "w", "next")

    def __init__(self, u: int, v: int, w: int, next: int) -> None:
        self.u = u
        self.v = v
        self.w = w
        self.next = next


class LinkList:
    """与 linklist.py 的 linkList 等价的最小实现，保证本文件可独立复制使用。"""

    def __init__(self) -> None:
        self.reset()

    def reset(self) -> None:
        self.edge_cnt = 0
        self.e: list[Edge] = []
        self.h: defaultdict[int, int] = defaultdict(lambda: -1)

    def add(self, u: int, v: int, w: int = 0) -> None:
        self.e.append(Edge(u, v, w, self.h[u]))
        self.h[u] = self.edge_cnt
        self.edge_cnt += 1

    def add2(self, u: int, v: int, w: int = 0) -> None:
        self.add(u, v, w)
        self.add(v, u, w)

    def __getitem__(self, i: int) -> Edge:
        return self.e[i]


e = LinkList()


class TarjanCut:
    """dfn/low 为时间戳；root 是当前 DFS 树的根，用来做根割点的子树数特判。"""

    def __init__(self) -> None:
        self.n = 0
        self.timer = 0
        self.dfn: list[int] = []
        self.low: list[int] = []
        self.is_cut: list[bool] = []
        self.root = 0

    def set(self, _n: int) -> None:
        self.n = _n
        self.timer = 0
        self.dfn = [0] * (_n + 1)
        self.low = [0] * (_n + 1)
        self.is_cut = [False] * (_n + 1)
        self.root = 0

    def dfs(self, u: int, fa: int = -1) -> None:
        self.timer += 1
        self.dfn[u] = self.low[u] = self.timer
        child = 0  # 统计 u 在 DFS 树里的子节点数，只有根节点需要

        i = e.h[u]
        while i != -1:
            v = e[i].v
            if v != fa:  # 不走父子边（重边情形需改用边编号判断，这里沿用 C++ 写法）
                if self.dfn[v] == 0:  # 树边
                    child += 1
                    self.dfs(v, u)
                    if self.low[v] < self.low[u]:
                        self.low[u] = self.low[v]
                    # v 回不到 u 的祖先，删除 u 就会把 v 子树切出去。
                    if self.low[v] >= self.dfn[u] and u != self.root:
                        self.is_cut[u] = True
                elif self.dfn[v] < self.dfn[u]:
                    # 返祖边只能取 dfn[v]：边 (u, v) 不代表 u 能借 v 继续往上跳。
                    if self.dfn[v] < self.low[u]:
                        self.low[u] = self.dfn[v]
            i = e[i].next

        # 根节点没有祖先，只有 ≥2 棵子树时才是割点。
        if u == self.root and child > 1:
            self.is_cut[u] = True

    def solve(self) -> None:
        for i in range(1, self.n + 1):
            if self.dfn[i] == 0:
                self.root = i  # 每个连通块单独确定根
                self.dfs(i, 0)  # fa = 0 是 1..n 之外的哨兵，等价于「没有父亲」

    def get_cuts(self) -> list[int]:
        return [i for i in range(1, self.n + 1) if self.is_cut[i]]

测试用例

输入图：

5 4
1 2
2 3
3 4
3 5

割点是：

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 的前置知识。继续学习本书点双连通分量章节。