50pts求调
查看原帖
50pts求调
1552997
yanyunhao2027楼主2025/1/20 20:07
#include<bits/stdc++.h>
using namespace std;
#define int long long
stack<int>s;
int d[1000005],l[1000005],n,root,k,m,h,cnt=-1,maxn,maxx,head[1000005];
bool v2[2000005];
vector<int>er[500005];
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_v_dcc(int u,int fa){
	h++;
	d[u]=l[u]=h;
	s.push(u);
	int o=0;
	if(u==root&&head[u]==0){
		er[++k].push_back(u);
		return;
	}
	for(int i=head[u];i;i=e[i].next){
		int j=e[i].to;
		if(j==fa)continue;
		if(!d[j]){
			o++;
			Tarjan_v_dcc(j,u);
			l[u]=min(l[u],l[j]);
			if(d[u]<=l[j]){
				int t;
				k++;
				if(!v2[u]){
					if(d[u]==1){
						o++;
						if(o>=2)v2[u]=1;
					}else v2[u]=1;	
				}
				do{
					t=s.top();
					s.pop();
					er[k].push_back(t);
				}while(t!=j);
				er[k].push_back(u);
			}
		}else l[u]=min(l[u],d[j]);
	}
	if(fa==0&&o==0)er[++k].push_back(u);
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%lld%lld",&u,&v);
		add(u,v);
		add(v,u);
	}
	for(int i=1;i<=n;i++)
		if(!d[i])root=i,Tarjan_v_dcc(i,0);
	cout<<k<<endl;
	for(int i=1;i<=k;i++){
		cout<<er[i].size();
		for(int j=0;j<er[i].size();j++)
			cout<<' '<<er[i][j];
		cout<<endl;
	}
}
2025/1/20 20:07
加载中...