#C240219D. 边双连通分量

标签（Label）

tarjan
模板

网址（Website）

$\qquad$ P8436 【模板】边双连通分量

题解（Solution）

定义：

$\qquad$边双连通：一张没有割边的无向图。

$\qquad$边双连通分量：一张无向图中，满足边双连通的子图，且使这个图尽量大，称其为边双连通分量。

求法1（ tarjan+dfs 法）：

$\qquad$先通过 $tarjan$ 跑出割边，然后直接 $dfs$ 求出去除割边后的连通块。

求法2（ tarjan跑“强连通分量” 法）

$\qquad$找出无向图的强连通分量，注意不能让当前点从同一条无向边来回。由于存在重边，因此不能通过记录当前的 $father$ 来判断是否走的同一条无向边，可以通过记录上一次走过的边的编号来判断。（直接用 $vector$ 存储 $pair<int,int> $ ，$first$ 用来存当指向的点，$second$ 用来存边的编号）

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#include<stack>
#include<set>
#define For(i,l,r) for(int i=l;i<=r;i++) 
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
inline int input(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 501234;

vector<P> ft[N];
stack<int> st;

int n,m,ans;

int dfn[N],low[N],t;
int scc[N],cnt;
vector<int> dc[N];
void tarjan(int x,int last){//last上一条边的编号 
	dfn[x]=low[x]=++t,st.emplace(x);
	for(auto p:ft[x]){
		int y=p.first,id=p.second;
		//!!!特别注意：只是不能走上一条边，并不是不能走上一个点!!! 
		if(!dfn[y]) tarjan(y,id) , low[x] = min(low[x],low[y]);
		else if(!scc[y] && id!=last) low[x] = min(low[x],dfn[y]);
	}if(low[x] == dfn[x]){
		scc[x]=++cnt;
		dc[cnt].emplace_back(x);
		while(st.top() != x){
			scc[st.top()] = cnt;
			dc[cnt].emplace_back(st.top());
			st.pop();
		}st.pop();
	}
} 

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;int Tim = clock();
	For(i,1,m){
		int x=input(),y=input();
		ft[x].emplace_back(y,i);
		ft[y].emplace_back(x,i);
	}//记录边的编号  
	
	For(i,1,n) if(!dfn[i]) tarjan(i,0);
	
	cout<<cnt<<'\n';
	For(i,1,cnt){
		cout<<dc[i].size()<<' ';
		for(auto x:dc[i]) cout<<x<<' ';
		cout<<'\n';
	}
	return cerr<<"TIME:"<<(clock()-Tim)/1024.,0;
}