0pts求调玄关
查看原帖
0pts求调玄关
611878
sunqihuan楼主2024/12/13 22:14
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5,M=2e6+5;
int n,m,h[N],e[M],ne[M],idx;
int dfn[N],low[N],num,st[N],top;
int dcc,bridge[M],vis[N];
vector<int> ans[N];
void add(int u,int v){
	e[idx]=v;
	ne[idx]=h[u];
	h[u]=idx++;
}
void tarjan(int u,int fa){
	dfn[u]=low[u]=++num;
	st[++top]=u;
	for(int i=h[u];i!=-1;i=ne[i]){
		int v=e[i];
		if(!dfn[v]){
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
			if(dfn[u]<low[v]){
				bridge[i]=bridge[i^1]=1;
			}
		}else if(i!=(fa^1)){
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(dfn[u]==low[u]){
		dcc++;
		int now;
		do{
			now=st[top--];
			ans[dcc].push_back(now);
		}while(now!=u);
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	memset(h,-1,sizeof(h));
	while(m--){
		int u,v;
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
	for(int i=1;i<=n;i++){
		if(dfn[i]==0)tarjan(i,-1);
	}
	cout<<dcc<<endl;
	for(int i=1;i<=dcc;i++){
		cout<<ans[i].size()<<" ";
		for(int j=0;j<ans[i].size();j++)cout<<ans[i][j]<<" ";
		cout<<endl;
	}
	return 0;
}


2024/12/13 22:14
加载中...