【题目来源】
洛谷：P3388 【模板】割点（割顶） - 洛谷
【题目描述】
给出一个 \(n\) 个点，\(m\) 条边的无向图，求图的割点。
【输入】
第一行输入两个正整数 \(n,m\)。
下面 \(m\) 行每行输入两个正整数 \(x,y\) 表示 \(x\) 到 \(y\) 有一条边。
【输出】
第一行输出割点个数。
第二行按照节点编号从小到大输出节点，用空格隔开。
【输入样例】
6 7
1 2
1 3
1 4
2 5
3 5
4 5
5 6
【输出样例】
1
5
【算法标签】
《洛谷 P3388 割点》 #Tarjan# #双连通分量#
【代码详解】
// 引入所有标准库头文件，方便使用各种标准库功能
#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;
}
【运行结果】
6 7
1 2
1 3
1 4
2 5
3 5
4 5
5 6
1
5