求助
查看原帖
求助
902702
wuming1679a楼主2024/7/1 18:24
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10,M=2e6*2+10;
int n,m;
int dfn[N],low[N],ts=0;
vector<int> bcc[N];
int num=0;
int stk[N];
int nums=0;
int edge[M],next_edge[M],head[M],idx=0;

void add(int u,int v) {
	edge[idx]=v,next_edge[idx]=head[u],head[u]=idx++;
}

void tarjan(int u,int fa) {
	int son=0;
	low[u]=dfn[u]=++ts;

	stk[++nums]=u;

	for(int i=head[u]; i!=-1; i=next_edge[i]) {
		int v=edge[i];
		if(v==fa)continue;
		if(!dfn[v]) {
			son++;
			tarjan(v,u);
			low[u]=min(low[v],low[u]);
			if(low[v]>=dfn[u]) {
				num++;
				while(stk[nums+1]!=v)bcc[num].push_back(stk[nums--]);
			}
			bcc[num].push_back(u);
		} else {
			low[u]=min(low[u],dfn[v]);
		}
	}

	if(fa==-1&&son==0) {
		bcc[num++].push_back(u);
	}
}
int main() {
	scanf("%d%d",&n,&m);
	memset(next_edge,-1,sizeof(next_edge));
	while(m--) {
		int u,v;
		scanf("%d%d",&u,&v);
		if(u!=v)add(u,v),add(v,u);
	}

	for(int root=1; root<=n; root++) {
		if(!dfn[root])tarjan(root,-1);
	}
	printf("%d\n",num);
	for(vector<int> i:bcc) {
		printf("%d ",i.size());
		for(int j:i) {
			printf("%d ",j);
		}
		printf("\n");
	}
	return 0;
}
2024/7/1 18:24
加载中...