样例不过求条
查看原帖
样例不过求条
398152
MinimumSpanningTree最小生成树楼主2024/7/15 20:10
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=5e5+100,M=2e6+100;
int n,m,u,v,k,t[N],dfn[N],low[N],num,block[N],cnt,lsz;
vector<vector<int> > ans;
bool flag[M*2];
struct node
{
	int id,last;
}a[M*2];
void add(int a1,int a2)
{
	a[++k].id=a2;
	a[k].last=t[a1];
	t[a1]=k;
}
void tarjan(int x,int edge)
{
	dfn[x]=low[x]=++num;
	for(int i=t[x];i;i=a[i].last)
	{
		if(!dfn[a[i].id])
		{
			tarjan(a[i].id,i);
			low[x]=min(low[x],low[a[i].id]);
			if(low[a[i].id]>dfn[x]) flag[i]=flag[i^1]=true;
		}
		else if(i!=(edge^1)) low[x]=min(low[x],dfn[a[i].id]);
	}
}
void dfs(int x,int c)
{
	block[x]=c;
	ans[c].push_back(x);
	for(int i=t[x];i;i=a[i].last)
	{
		if(block[a[i].id]||flag[i]) continue;
		dfs(a[i].id,c); 
	} 
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		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]) tarjan(i,0);
	}	
	ans.push_back(vector<int>());
	for(int i=1;i<=n;i++)
	{
		if(!block[i])
		{
			ans.push_back(vector<int>());
			dfs(i,++cnt);
		}
	}
	printf("%d\n",cnt);
	for(int i=1;i<=cnt;i++)
	{
		lsz=ans[i].size();
		for(int j=0;j<lsz;j++) printf("%d ",ans[i][j]);
		printf("\n");
	}
	return 0;
}
2024/7/15 20:10
加载中...