0pts 求调玄关
查看原帖
0pts 求调玄关
1552997
yanyunhao2027楼主2025/1/20 19:45

代码如下:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int d1[1000005],size[1000005],l1[1000005],b[1000005],n,m,h1,f,cnt,head[1000005];
bool v1[200005],v[15005];
struct node{
	int r,to,next,w;
}e[4000005];
void add(int u,int v){
	e[++cnt].to=v;
	e[cnt].r=u;
	e[cnt].next=head[u];
	head[u]=cnt;
}
void Tarjan_qiao(int u,int fa){
	h1++;
	d1[u]=l1[u]=h1;
	for(int i=head[u];i;i=e[i].next){
		int j=e[i].to;
		if(j==fa)continue;
		if(!d1[j]){
			Tarjan_qiao(j,u);
			l1[u]=min(l1[u],l1[j]);
			if(l1[j]>d1[u])v1[i]=v1[i^1]=1;
		}else l1[u]=min(l1[u],d1[j]);
	}
}
void dfs(int x){
	v[x]=1;
	b[x]=f;
	size[f]++;
	for(int i=head[x];i;i=e[i].next){
		int j=e[i].to;
		if(v[j]||v1[i])continue;
		dfs(j);
	}
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
	for(int i=1;i<=n;i++)if(!d1[i])Tarjan_qiao(i,0);
	for(int i=1;i<=n;i++)
		if(!v[i])f++,dfs(i);
	cout<<f<<endl;
	for(int i=1;i<=f;i++){
		cout<<size[i];
		for(int j=1;j<=n;j++)
			if(b[j]==i)cout<<' '<<j;
		cout<<endl;
	}
}
2025/1/20 19:45
加载中...