POJ 1232 Ubiquitous Religions(基础并查集)

并查集的基础题目,最简单套个模板就可以通过

#include<iostream>
#include<cstdio>
#include<cstring>
#include<functional>
#include<algorithm>
int n,m,a,b,cnt;
int fa[50000];
void init()
{
	cnt=0;
	for(int i=1;i<=n;i++)
		fa[i]=i;
}
int getfa(int x)
{
	if(x==fa[x])
		return x;
	else
		return fa[x]=getfa(fa[x]);
}
void merge(int u,int v)
{
	int t1,t2;
	t1=getfa(u);
	t2=getfa(v);
	if(t1!=t2)
		fa[t1]=t2;
}
int main()
{
	int i;
	int test=1;
	while(scanf("%d%d",&n,&m),n&&m)
	{
		init();
		for(i=1;i<=m;i++)
		{
			scanf("%d%d",&a,&b);
			merge(a,b);
		}
		for(i=1;i<=n;i++)
			if(fa[i]==i)
				cnt++;
		printf("Case %d: %d\n",test++,cnt);
	}
	return 0;
}


全部评论

相关推荐

牛客976315581号:这是hr“不合适”的便捷语句
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务