0分求调
查看原帖
0分求调
1188966
coduck_S12004zbj楼主2025/1/21 09:35
#include<bits/stdc++.h> 
using namespace std;
struct node{
	int nxt,to;
}g[4001000];
int head[501000],cnt=1;
int n,m,dfn[501000],low[501000],sum,id;
vector<int> kuai[501000];
int cut[501000];
int st[501000],top;
void add(int u,int v){
	g[cnt].to=v;
	g[cnt].nxt=head[u];
	head[u]=cnt++;
}
void tarjan(int u,int fa){
	dfn[u]=low[u]=++id;
	st[++top]=u;
	for(int i=head[u];i;i=g[i].nxt){
		int v=g[i].to;
		if(v==fa) continue;
		if(!dfn[v]){
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]){
				int t=0;
				sum++;
				while(t!=v){
					t=st[top--];
					kuai[sum].push_back(t);
				}
				kuai[sum].push_back(u);
			}
		}
		else low[u]=min(low[u],dfn[v]);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		if(u==v) continue;
		add(u,v),add(v,u);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			if(head[i]==0)kuai[++cnt].push_back(i);
			else tarjan(i,0);
		}
		
	} 
	printf("%d\n",sum);
	for(int i=1;i<=sum;i++){
		printf("%d ",kuai[i].size());
		for(int j=0;j<kuai[i].size();j++) printf("%d ",kuai[i][j]);
		printf("\n");
	}
	return 0;
}
2025/1/21 09:35
加载中...