Ubiquitous Religions Time Limit:5000MS Memory Limit:65536KB 64bit IO Format:%lld & %llu Description 当今世界有很多不同的宗教,很难通晓他们。你有兴趣找出在你的大学里有多少种不同的宗教信仰。 你知道在你的大学里有n个学生(0 < n <= 50000) 。你无法询问每个学生的宗教信仰。此外,许多学生不想说出他们的信仰。避免这些问题的一个方法是问m(0 <= m <= n(n - 1)/ 2)对学生, 问他们是否信仰相同的宗教( 例如他们可能知道他们两个是否去了相同的教堂) 。在这个数据中,你可能不知道每个人信仰的宗教，但你可以知道校园里最多可能有多少个不同的宗教。假定每个学生最多信仰一个宗教。 Input 有多组数据。对于每组数据： 第一行：两个整数n和m。 以下m行：每行包含两个整数i和j，表示学生i和j信仰相同的宗教。学生编号从1到n。 输入的最后一行中,n = m = 0。 Output 对于每组测试数据，输出一行，输出数据序号( 从1开始) 和大学里不同宗教的最大数量。（参见样例） Sample Input 10 9 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 10 4 2 3 4 5 4 8 5 8 0 0 Sample Output Case 1: 1 Case 2: 7
这题目没什么好说的和之前的题目基本一样，注意下维护的是未知信仰种类的人就行。
AC代码：
#include"iostream"
#include"cstdio"
#include"algorithm"
#include"cmath"
#include"cstring"
using namespace std;
int pe[100000];
int num;
int find(int x) {
return pe[x]==x?x:(pe[x]=find(pe[x]));
}
int main() {
int n,m,a,b,time=1;
while(~scanf("%d%d",&n,&m)) {
if(!n&&!m)break;
for(int i=0; i<n; i++) {
pe[i]=i;
num=n;
}
for(int i=0; i<m; i++) {
scanf("%d%d",&a,&b);
int root1=find(pe[a]);
int root2=find(pe[b]);
if(root1!=root2) {
pe[root2]=root1;
num--; //记录还有多少个人信仰种类不知道
}
}
printf("Case %d: %d\n",time++,num);
}
return 0;
}
ACM: Ubiquitous Religions-并查集-解题报告
原文：http://www.cnblogs.com/HDMaxfun/p/5700716.html