#C240219C. 点双连通分量

标签（Label）

tarjan
模板

网址（Website）

$\qquad$ P8435 【模板】点双连通分量

题解（Solution）

定义：

$\qquad$点双连通：对于一张无向图，若不存在割点，则该图是点联通的；

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

求法：

$\qquad$与求割点与求强连通分量类似，每找到一个割点，将当前存在栈中的元素弹出，直到弹到当前的节点 $x$ 指向的 $y$ 为止（可以想一下为什么只弹到 $y$ ，而不像强连通分量一样弹到 $x$）。

$\qquad$当前的 $x$ 不需要弹出栈，因为它还有可能属于其他的点双连通分量。

$\qquad$注意原题中图并不联通，因此可能出现只有一个点的情况，需要特判。

$\qquad$注意重边和自环。

代码（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<int> ft[N];
stack<int> st;

int n,m,ans;

int low[N],dfn[N],t;
vector<int> dc[N];
int scc[N],cnt;
void tarjan(int x,int fa){
	low[x]=dfn[x]=++t,st.emplace(x);
	int son=0;
	for(auto y:ft[x]){
		if(!dfn[y]){
			son++;
			tarjan(y,x);
			low[x] = min(low[x],low[y]);
			if(dfn[x] <= low[y]){
				++cnt;
				while(st.top() != y){
					dc[cnt].emplace_back(st.top()),st.pop();
				}dc[cnt].emplace_back(st.top()),st.pop();
				dc[cnt].emplace_back(x);
			}
		}else low[x] = min(low[x],dfn[y]);
	}if(fa == 0 && son == 0) dc[++cnt].emplace_back(x);//特判独立点 
}

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);
		ft[y].emplace_back(x);
	}
	
	For(i,1,n) if(!dfn[i]){
		tarjan(i,0);
		while(st.size()) st.pop();
	}
	
	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;
}