专栏文章

题解：P3388 【模板】割点（割顶）

cchangxiang2012
P3388题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip9p9vn
此快照首次捕获于
2025/12/03 08:27
3 个月前
此快照最后确认于
2025/12/03 08:27
3 个月前
查看原文

割点（割顶）问题的 Tarjan 算法解析

割点（Cut Vertex），也称为割顶，是无向连通图中的一个重要概念。如果删除某个顶点后，图的连通分量数目增加，则称该顶点为割点。在通信网络中，割点可能代表关键节点，其故障会导致网络分裂。

题目分析

本题要求找出给定无向图中的所有割点，并按编号从小到大输出。输入为图的顶点数和边数，以及每条边的连接信息；输出为割点的数量和具体编号。
关键约束条件：
  • 顶点数 nn 最大为 20,00020,000。
  • 边数 mm 最大为 100,000100,000。
  • 图可能不连通，需要处理所有连通分量。

Tarjan算法原理

Tarjan 算法是一种高效的图论算法，通过深度优先搜索（DFS）来寻找图的割点、桥和强连通分量。其核心思想是利用时间戳（dfndfn）和回溯值（lowlow）来判断顶点间的连通关系。
  • 时间戳 dfn[u]dfn[u]：顶点 uu 在 DFS 遍历中第一次被访问的顺序号。
  • 回溯值 low[u]low[u]：顶点 uu 及其子树中的节点通过非父子边（回边）所能追溯到的最早时间戳。

AC代码

下面是解决该问题的 Tarjan 算法实现：
CPP
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <cctype>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <map>
#include <ctime>
#include <cstdlib>
#include <iomanip>
#include <bitset>
#define N 100010 
using namespace std;
struct add{int v,next;}e[2 * N];
int head[N],dfn[N],low[N],n,m,cnt = 1,num = 0,root;
bool cut[N];
inline void ins(int x,int y){
	e[++cnt].v = y;
	e[cnt].next = head[x];
	head[x] = cnt;
}
inline void tarjan(int x){
	dfn[x] = low[x] = ++num;
	int flag = 0;
	for(int i = head[x];i;i = e[i].next){
		int y = e[i].v;
		if(!dfn[y]){
			tarjan(y);
			low[x] = min(low[x],low[y]);
			if(low[y] >= dfn[x]){
				++flag;
				if(x != root || flag > 1){
					cut [x] = 1;
				}
			}
		}else low[x] = min(low[x],dfn[y]);
	} 
}
int main(){
	ios::sync_with_stdio(false);//关闭cin流同步,不能使用scanf printf;
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i = 1;i <= m;i++){
		int x,y;
		cin>>x>>y;
		ins(x,y);
		ins(y,x);
	}
	for(int i = 1;i <= n;i++){
		if(!dfn[i]){
			root = i,tarjan(i);
		}
	}
	int tot = 0;
	for(int i = 1;i <= n;i++){
		if(cut[i]){
			++tot;
		}
	}
	cout<<tot<<endl;
	for(int i = 1;i <= n;i++){
		if(cut[i]){
			cout<<i<<" ";
		}
	}
	return 0;
}
/*

*/

算法关键点解析

  1. 邻接表存储图结构：使用数组模拟链表，高效存储稀疏图。每个顶点的所有邻接边构成一个链表。
  2. Tarjan 算法核心逻辑：
    • 对每个顶点进行 DFS 遍历，记录时间戳 dfndfn 和回溯值 lowlow。
    • 对于根节点，若其子树数量大于 11，则为割点
    • 对于非根节点，若存在子树 vv 满足 low[v]≥dfn[u]low[v] \ge dfn[u]，则 uu 为割点。
  3. 处理非连通图：遍历所有顶点，对每个未访问的顶点作为根节点进行 Tarjan 算法。
  4. 时间复杂度分析：算法对每个顶点和每条边仅遍历一次，时间复杂度为 O(n+m)O(n + m)，适用于大规模图。

示例测试

以题目中的样例输入为例：
CPP
6 7
1 2
1 3
1 4
2 5
3 5
4 5
5 6
运行算法后，顶点 55 被标记为割点，因为删除顶点55后，图将分为两个连通分量： 1,2,3,4{1,2,3,4} 和 6{6}。输出结果为：
CPP
1
5
感谢@whoseJam的讲解

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...