50分求助
查看原帖
50分求助
740093
SamHe楼主2024/7/23 09:58
#include<bits/stdc++.h>
using namespace std;
int n,m,top,ans,idx,low[1000010],dfn[1000010]; 
int head[500010],nxt[5000010],to[500000];
int s[1000010];
int cnt=1; 
vector<int>edge[1000010];
inline void add(int x,int y){
	to[++cnt]=y;
	nxt[cnt]=head[x];
	head[x]=cnt;
}
inline void Tarjan(int now,int fa){
	int child=0;
	low[now]=dfn[now]=++idx;
	s[++top]=now;
	for(int i=head[now];i;i=nxt[i]){
		int v=to[i];
		if(!dfn[v]){
			child++;
			Tarjan(v,now);
			low[now]=min(low[now],low[v]);
			if(low[v]>=dfn[now]){\
				ans++;
				while(s[top+1]!=v){
					edge[ans].push_back(s[top--]);
					
				}
                edge[ans].push_back(now);
			} 
		}
        else if(v!=fa){
			low[now]=min(low[now],dfn[v]);
		}
	}
	if(fa==0&&child==0){
		edge[++ans].push_back(now);
	}
}
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(dfn[i]){
			continue;
		}
		top=0;
		Tarjan(i,0);
	}
	cout<<ans<<endl;
	for(int i=1;i<=ans;i++){
		cout<<edge[i].size()<<' ' ;
		for(auto v:edge[i]){
			cout<<v<<' ';
		}
		cout<<endl;
	}
}
2024/7/23 09:58
加载中...