太难的搞不过，只能来写简单的了
POJ2524
无所不在的宗教
世界上宗教何其多。假设你对自己学校的学生总共有多少种宗教信仰很感兴趣。学校有n个学生，但是你不能直接问学生的信仰，不然他会感到很不舒服的。有另外一个方法是问m对同学，是否信仰同一宗教。根据这些数据，相信聪明的你是能够计算学校最多有多少种宗教信仰的。
【输入格式】
可以输入多个测试用例(Case)，每一个用例的第一行包含整数n和m，n表示学生编号(1-n)，在接下来的m行中，每一行包含两个整数，对应信仰同一宗教的两名学生的编号，输入结束行为n
= m=0。
【输出格式】
输出每一个测试用例中包含的学生信仰的最大宗教数量。
样例输入
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
样例输出
Case 1: 1
Case 2: 7
代码
#include <iostream>
using namespace std; const int MAXN=;
int pa[MAXN];
int rank[MAXN]; void make_set(int x){
pa[x] = x;
rank[x] = ;
} int find_set(int x){
if(x != pa[x]){
pa[x] = find_set(pa[x]);
}
return pa[x];
} void union_set(int x,int y){
x = find_set(x);
y = find_set(y); if(rank[x] > rank[y]){
pa[y] = x;
}
else{
pa[x] = y;
if(rank[x] == rank[y]){
rank[y]++;
}
}
} int main(void){
int n,m,kase=,count;
while(scanf("%d%d",&n,&m) == && n!= && m!=){
int i;
for(i=;i<=n;i++){
make_set(i);
}
for(i=;i<m;i++){
int a,b;
scanf("%d%d",&a,&b);
union_set(a,b);
}
count = ;
for(i=;i<=n;i++){
if(i == pa[i]){
count++;
}
}
printf("Case %d: %d\n",++kase,count);
}
return ;
}