50分求助
查看原帖
50分求助
869988
DLYdly2010楼主2023/1/15 22:06
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10,M=2e6+10;
vector<int>a[N],ans[N];
int n,m,cnt,tot,top,st[N],dfn[N],low[N];
void Tarjan(int u,int fa)
{
	dfn[u]=low[u]=++tot,st[++top]=u;
	for(int i=0;i<a[u].size();i++)
	{
		int v=a[u][i];
		if(v==fa)continue;
		if(dfn[v]==0)
		{
			Tarjan(v,u);
			low[u]=min(low[u],low[v]);
		}
		else low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u])
	{
		cnt++;
		for(;st[top]!=u;top--)
		{
			ans[cnt].push_back(st[top]);
		}
		ans[cnt].push_back(u);
		top--;
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1,u,v;i<=m;i++)
	{
		scanf("%d%d",&u,&v);
		a[u].push_back(v);
		a[v].push_back(u);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])Tarjan(i,0);
	printf("%d\n",cnt);
	for(int i=1;i<=cnt;i++)
	{
		printf("%d ",ans[i].size());
		for(int j=0;j<ans[i].size();j++)
		{
			printf("%d ",ans[i][j]);
		}
		printf("\n");
	}
	return 0;
}
2023/1/15 22:06
加载中...