关节点问题 题解

知识点：图论 | DFS | Tarjan算法 | 双连通分量相关

此文章的MarkDown、源码以及原图：点击跳转Gitee仓库

📗 题目描述

输入： 两个整数 $n$ 与 $m$，表示 $n$ 个顶点与 $m$ 条无向边。接下来 $m$ 行，每行两个整数 $l$ 与 $r$，表示一条边的两个端点。

输出： 一个整数，表示该无向图中关节点（割点）的个数。

📘 关节点定义

关节点（Articulation Point / Cut Vertex）： 在无向连通图中，删除该顶点及其关联的所有边后，图的连通分量数量增加的顶点。

示例理解：

示例1

图中点集 ${A, B, C, D, E, F, G}$，边集 ${E_1, E_2, \dots, E_9}$ 构成一个连通分量。

  • 删除 $E$ 及其关联边 $E_5, E_6, E_7, E_8$ 后，图分裂为两个连通分量：
    • $U_1 = {A, B, C, D}$，边集 ${E_1, E_2, E_3, E_4}$
    • $U_2 = {F, G}$，边集 ${E_9}$

因此 $E$ 是原图的关节点。

📙 算法核心思想

核心思路：DFS + low 值

通过一次 DFS 遍历构建DFS生成树，利用 dfss（时间戳）和 lown（能回溯到的最早祖先时间戳）来判断关节点。

数据结构 含义
dfss[i] 顶点 $i$ 在 DFS 中被访问的时间戳（步骤数）
lown[i] 顶点 $i$ 的子树通过回边能到达的最早祖先的 dfss 值

判定规则

节点类型 关节点条件
根节点 DFS 树中根节点有 $\geq 2$ 个子树 → 是关节点
非根节点 存在子节点 $j$ 使得 $\text{lown}[j] \geq \text{dfss}[i]$ → $i$ 是关节点

$\text{lown}[j] \geq \text{dfss}[i]$ 的直观含义： 子节点 $j$ 及其子树中没有任何回边能绕过 $i$ 到达 $i$ 的祖先，因此删除 $i$ 后 $j$ 的子树与图的其余部分断开。

一定不是关节点 说明
叶子节点 没有子树，删除不影响连通性
根节点且仅有1棵子树 删除后剩余部分仍连通

📕 DFS遍历演示

还是上面的图，从 $A$ 开始作为根节点，按字典序升序进行 DFS：

第1步：初始化

初始 step = 1，ans = 0

step1

第2步：A → B

进入 $B$，step 递增

step2

第3步：B → D

进入 $D$，继续深入

step3

第4步：遍历完整DFS树

所有节点都被访问后，得到以下DFS树 ：

step4

第5步：回退并更新 low 值

（实边为树边，虚边为回边）从叶子节点开始回退，遇到回边时更新 lown：

step5

回退规则：

  1. 若当前点通过回边直接连到某个已访问祖先，比较 dfss[祖先] 与 lown[当前点]，取较小值更新 lown
  2. 回退过程中，若**子节点的 lown $\geq$ 父节点的 dfss**，说明子节点无法绕过父节点 → 父节点是关节点

📓 代码实现

数据结构

1
2
3
4
5
6
7
8
vector<int> arr[114514];   // 邻接表存图
int vis[114514];            // 是否已访问
int step = 1;               // DFS时间戳（步数）
int lown[114514];           // low值：能回溯到的最早祖先时间戳
int dfss[114514];           // DFS时间戳
int ans;                    // 关节点个数
int isCut[114514];          // 标记是否为关节点
int child, root;            // root=DFS起点，child=root的子树数量

完整代码

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
//
// Created by AKKO on 2026/4/10.
//
#include <bits/stdc++.h>
using namespace std;
vector<int> arr[114514];
int vis[114514];
int step=1;
int lown[114514];
int dfss[114514];
int ans;
int isCut[114514];
int child,root;

void dfs(int s,int father) {
    lown[s]=dfss[s]=step++;   // 初始化当前节点的时间戳和low值
    vis[s]=1;
    for (int j:arr[s]) {
        if (j==father) continue;       // 跳过父节点（无向图会存两条边）
        if (!vis[j]) {
            dfs(j,s);                  // 递归访问未访问的子节点
            lown[s]=min(lown[s],lown[j]);  // 回退时用子节点的low更新自己的low
            if (s!=root&&lown[j]>=dfss[s]) {
                // 非根节点：子节点无法绕过自己 → 自己是关节点
                if (!isCut[s]){isCut[s]=1;ans++;}
            }
            if (s==root) {
                child++;                // 根节点：统计子树数量
            }
        }else {
            // 回边：用已访问邻居的时间戳更新自己的low
            lown[s]=min(lown[s],dfss[j]);
        }
    }
}

int main () {
    int n,m;
    cin>>n>>m;
    for (int i=0;i<m;i++) {
        int l,r;
        cin>>l>>r;
        arr[l].push_back(r);    // 无向图存双向边
        arr[r].push_back(l);
    }
    dfs(0,-1);                  // 从节点0开始DFS，父节点设为-1
    if (child>=2&&!isCut[0]) ans++;   // 根节点特判：子树>=2即为关节点
    cout<<"ANS:"<<ans<<endl;
}

📝 算法要点总结

DFS过程中关键操作

阶段 操作 代码
进入节点 初始化时间戳和 low 值 lown[s]=dfss[s]=step++
遇到未访问子节点 递归后更新 low lown[s]=min(lown[s],lown[j])
遇到已访问节点（回边） 用回边更新 low lown[s]=min(lown[s],dfss[j])
回退时判断关节点 非根节点判定 lown[j]>=dfss[s]

根节点特判

条件 结果
child >= 2（子树数 $\geq 2$） 是关节点
child < 2（只有1棵子树） 不是关节点

复杂度分析

指标 复杂度
时间复杂度 $O(n + m)$（DFS遍历整张图）
空间复杂度 $O(n)$（邻接表 + 数组）

💡 易错提醒：

  • 无向图中每条边存了两次，DFS时必须跳过 father，否则会反复访问父节点
  • lown 的更新来源有两种：子节点的 lown（回退时）和 回边指向节点的 dfss（遇到已访问节点时），注意区分
  • 根节点不能套用 lown[j]>=dfss[s] 判定，必须单独用子树数量判断
  • 本代码默认图从节点0开始编号，且假设图是连通的；若图不连通需对每个连通分量分别DFS