Tarjan

P3388 【模板】割点（割顶）

1、注意在遍历时要储存根节点编号，判断时需要特判根节点

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;   
int n,m,r;
int dn,dfn[N],low[N],cnt,buc[N];
vector<int> e[N];
void dfs(int id){
	//标记时间戳 
	dfn[id] = low[id] = ++dn;
	int son = 0;
	//遍历该点相邻点 
	for(int it : e[id]){
		//如果没有被遍历 
		if(!dfn[it]){
			//其子节点加一 
			son++;
			//遍历当前节点 
			dfs(it);
			//进行更新 
			low[id] = min(low[id],low[it]);
			//若id的子节点不能够通过其他路径走到比id时间戳更小的点 并且 id不为根节点 
			//id就为割点 
			if(low[it] >= dfn[id] && id != r){
				//割点数量加一 
				cnt += !buc[id];
				//将id标记为割点 
				buc[id] = 1;
			}			
		}else{
			//更新id_low为其邻点的最小时间戳 
			//得到通过id点能够到达的最小值 
			low[id] = min(low[id],dfn[it]);
		}
	}
	//如果id是根节点，但其有两个以上的子树，那么id为割点 
	if(son >= 2 && id == r){
		//更新，标记 
		cnt += !buc[id];
		buc[id] = 1;
	}
}
int main(){
	cin>>n>>m;
	//邻接表存储连点 
	for(int i = 1; i <= m; ++i){
		int u,v;
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	//遍历dfs 
	for(int i = 1; i <= n; ++i){
		//没有被遍历 
		if(!dfn[i]){
			//初始化顶点 
			r = i;
			dfs(i);
		}
	}
	cout<<cnt<<endl;
	for(int i = 1; i <= n; ++i){
		if(buc[i]){
			cout<<i<<" ";
		}
	}
	return 0;
} 

洛谷 P1656 炸铁路

读图，邻接表存图，tarjan求割边(桥)，排序，输出

注意父亲节点的判断，如果两点之间有重边的情况需要注意

如果在第一次之外还回到了父亲结点（说明可能有重边），则按像计算儿子结点的方法一样用父亲结点的值更新当前结点的值。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 10010;
int n, m, x, y, idx, dfn[MAXN], low[MAXN], ans,a;
//dfn储存固定时间戳， low储存其出点能够到达的最小时间戳
vector<int> G[MAXN];//使用邻接表存图 
struct Edge{int from, to;} edge[MAXN];//题目要求，a < b 
bool cmp(const Edge a, const Edge b){if(a.from != b.from)return a.from < b.from; return a.to < b.to;}//题目要求排序 
inline void add_edge(int x, int y){edge[ans].from = min(x, y); edge[ans].to = max(x, y); ans++;}//在答案中加入一条边 
void dfs(int cur, int fa){//cur当前节点， fa 为其父亲节点 
	int child;
	dfn[cur] = ++idx;// 计算当前节点的时间戳 
	low[cur] = dfn[cur];//初始化 当前可以访问到的最早时间戳肯定是自己的时间戳 
	bool vis = false;//防止在有重边时会出错
	for(int i = 0; i < G[cur].size(); ++i){//遍历它的所有出点 
		child = G[cur][i];//取出出点 
		//如果这个节点被访问过 
		if(dfn[child]){
			if(child == fa && !vis) vis = true;//如果是父亲节点 且是第一次访问不做任何操作 
			else low[cur] = min(low[cur], dfn[child]);//如果访问到了不是父亲节点的节点 更新low值 
			//如果在第一次之外还回到了父亲结点，则按像计算儿子结点的方法一样用父亲结点的值更新当前结点的值。
		}
		//如果这个节点之前没有被访问过 
		if(!dfn[child]){
			dfs(child, cur);//进行dfs 
			if(dfn[cur] < low[child]) add_edge(cur, child);//如果满足条件(当前节点向下走无法回到之上的节点)，
			//说明当边是割边 将其加入答案之中 
			low[cur] = min(low[cur], low[child]);
			//更新当前节点的low值 
		}
	}
}
int main(){
	cin >> n >> m;
	for(int i = 0; i < m; ++i) cin >> x >> y,G[x].push_back(y),G[y].push_back(x);
	for(int i = 1; i <= n; ++i) if(!dfn[i]) dfs(i, i);//图可能不连通， 初始时将自己的父亲节点初始化为自己，不会出错 
	sort(edge, edge + ans, cmp);//将答案进行排序 
	for(int i = 0; i < ans; ++i) cout << edge[i].from <<" "<< edge[i].to << endl;//输出 
	return 0;
}