当前位置：首页 > news >正文

题解：洛谷 P3388 割点

news 2026/6/17 3:12:50

【题目来源】

洛谷：P3388 【模板】割点（割顶） - 洛谷

【题目描述】

给出一个 \(n\) 个点，\(m\) 条边的无向图，求图的割点。

【输入】

第一行输入两个正整数 \(n,m\)。

下面 \(m\) 行每行输入两个正整数 \(x,y\) 表示 \(x\) 到 \(y\) 有一条边。

【输出】

第一行输出割点个数。

第二行按照节点编号从小到大输出节点，用空格隔开。

【输入样例】

【输出样例】

1
5

【核心思想】

问题分析：给定一个 \(n\) 个点 \(m\) 条边的无向图，求所有的割点（割顶）。割点是指删除该点后，图的连通分量数量会增加的点。这是一个Tarjan算法问题，关键在于通过DFS遍历计算每个节点的 dfn（时间戳）和 low（能回溯到的最早时间戳），判断节点是否为割点。
算法选择：
- Tarjan算法：使用DFS遍历图，在 \(O(n + m)\) 时间内找到所有割点
- 割点判定条件：对于节点 \(x\) 的子节点 \(y\)，若 low[y] >= dfn[x]，说明 \(y\) 无法通过回边到达 \(x\) 的祖先，\(x\) 是割点
- 根节点特判：根节点需要有两个或以上子树才是割点
关键步骤：
- 建图：读取 \(m\) 条无向边，构建邻接表
- 初始化：dfn[] = low[] = 0，时间戳计数器 tim = 0
- Tarjan DFS：
  - 对每个未访问的节点作为根节点调用 tarjan(root)
  - dfn[x] = low[x] = ++tim：初始化时间戳
  - 遍历邻接节点 \(y\)：
    - 若 \(y\) 未访问：递归 tarjan(y)，更新 low[x] = min(low[x], low[y])
    - 若 low[y] >= dfn[x]：\(y\) 无法绕过 \(x\) 到达祖先，\(x\) 可能是割点
    - 子树计数 child++，若 x != root || child > 1 则标记 cut[x] = 1
    - 若 \(y\) 已访问：low[x] = min(low[x], dfn[y])
- 输出结果：统计并输出所有割点
时间/空间复杂度：
- 时间复杂度：\(O(n + m)\)，每个节点和边只被访问一次
- 空间复杂度：\(O(n + m)\)，邻接表和辅助数组
割点与Tarjan算法的核心思想：
- 割点定义：删除该点后，图的连通分量数增加，即该点是某些子树的唯一连接点
- dfn与low数组：dfn 记录DFS访问顺序，low 记录通过回边能到达的最早祖先
- 割点判定原理：若子节点 \(y\) 的 low[y] >= dfn[x]，说明 \(y\) 及其子树无法通过回边到达 \(x\) 的祖先，\(x\) 是 \(y\) 子树与图中其他部分的唯一连接点
- 根节点特判：根节点没有祖先，需要有两个或以上独立子树才是割点
- 适用于无向图连通性分析、网络关键节点识别、图的分割类问题

【算法标签】

普及plus #强连通分量

【代码详解】

// 引入所有标准库头文件，方便使用各种标准库功能
#include <bits/stdc++.h>// 使用标准命名空间，避免每次使用标准库函数时都需要加 std:: 前缀
using namespace std;// 定义常量 N，表示节点的最大数量，通常用于限制数组和向量的大小
const int N = 20005;// 定义全局变量
int n, m, a, b;  // n: 节点数量，m: 边数量，a, b: 用于读取每条边的两个节点// 定义邻接表 e，用于存储图的边，e[i] 存储与节点 i 相连的所有节点
vector<int> e[N];// 定义数组 dfn 和 low，用于 Tarjan 算法中的深度优先搜索编号和最低可达编号
int dfn[N], low[N];// 定义时间戳 tim，用于记录 DFS 的访问顺序
int tim;// 定义数组 cut，用于标记节点是否为割点，cut[i] = 1 表示节点 i 是割点
int cut[N];// 定义变量 root，用于表示当前 Tarjan 算法处理的根节点
int root;// Tarjan 算法的递归函数，用于寻找图中的割点
// 参数 x 表示当前处理的节点
void tarjan(int x)
{// 设置当前节点 x 的深度优先搜索编号和最低可达编号为当前时间戳，并递增时间戳dfn[x] = low[x] = ++tim;// 初始化子节点计数器 son，用于记录当前节点的子节点数量int son = 0;// 遍历当前节点 x 的所有邻接节点 yfor (int y : e[x]){// 如果邻接节点 y 还没有被访问过（即 dfn[y] 为 0）if (!dfn[y]){// 递归调用 Tarjan 算法处理邻接节点 ytarjan(y);// 更新当前节点 x 的最低可达编号为 dfn[x] 和 low[y] 中的较小值low[x] = min(low[x], low[y]);// 判断当前节点 x 是否为割点// 条件：如果 low[y] >= dfn[x]，表示 y 无法通过回边到达 x 的祖先，因此 x 可能是割点if (low[y] >= dfn[x]){son++;  // 增加子节点计数// 判断是否满足割点的条件// 条件1：如果当前节点 x 不是根节点（x != root），或者// 条件2：如果当前节点 x 是根节点且有多个子节点（son > 1）if (x != root || son > 1)cut[x] = 1;  // 标记节点 x 为割点}}// 如果邻接节点 y 已经被访问过，则更新当前节点 x 的最低可达编号为 dfn[x] 和 dfn[y] 中的较小值elselow[x] = min(low[x], dfn[y]);}
}// 主函数，程序的入口点
int main()
{// 从标准输入读取节点数量 n 和边数量 mcin >> n >> m;// 循环读取每条边，构建无向图while (m--){// 读取边的两个节点 a 和 bcin >> a >> b;// 在邻接表 e 中，将节点 a 和节点 b 互相连接，表示无向边e[a].push_back(b);e[b].push_back(a);}// 遍历所有节点，对每个未被访问的节点调用 Tarjan 算法for (root = 1; root <= n; root++)if (!dfn[root])tarjan(root);// 初始化答案变量 ans，用于计数割点的数量int ans = 0;// 遍历所有节点，统计被标记为割点的节点数量for (int i = 1; i <= n; i++)if (cut[i])ans++;// 输出割点的总数量cout << ans << endl;// 输出所有被标记为割点的节点编号for (int i = 1; i <= n; i++)if (cut[i])cout << i << " ";// 输出换行符，以美化输出格式cout << endl;// 程序正常结束，返回 0return 0;
}

【运行结果】