POJ-2524 Ubiquitous Religions【并查集】

本文主要是介绍POJ-2524 Ubiquitous Religions【并查集】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.思路分析

根据题意，统计所有人的宗教信仰，为集合操作，应使用并查集。

2.方法设计及性能衡量

实现并查集即可，计算合并后的集合数量。

3.实现部分

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
int n,m,group=0,par[50010];
void init(){int i;for(i=1;i<=n;i++){par[i]=i;}
}
int find(int x){if(par[x]==x)return x;else return par[x]=find(par[x]);
}
int unio(int x,int y){x=find(x);y=find(y);if(x==y)return 0;else {par[x]=y;return 1;}
}
int main(){while(scanf("%d%d",&n,&m)!=EOF){if(n==0&&m==0)break;group++;int i,a,b,count=n;init();for(i=0;i<m;i++){scanf("%d%d",&a,&b);if(unio(a,b)!=0)count--;}   printf("Case %d: %d\n",group,count);} return 0;
}

这篇关于POJ-2524 Ubiquitous Religions【并查集】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---