POJ 2524 （简单并查集）
描述
当今世界上有如此多不同的宗教，很难将它们全部记录下来。您有兴趣了解您所在大学的学生信仰多少种不同的宗教。
您知道您的大学有 n 名学生 (0 < n <= 50000)。你不可能询问每个学生的宗教信仰。此外，许多学生不愿意表达自己的信仰。避免这些问题的一种方法是询问 m (0 <= m <= n(n-1)/2) 对学生，并询问他们是否信仰相同的宗教（例如，他们可能知道他们是否都参加同一所学校）教会）。从这些数据中，你可能不知道每个人信仰什么，但你可以了解校园里可能代表多少种不同宗教的上限。您可以假设每个学生最多信仰一种宗教。
输入
输入由多个案例组成。每种情况都以指定整数 n 和 m 的行开始。接下来的 m 行每行由两个整数 i 和 j 组成，指定学生 i 和 j 信仰相同的宗教。学生编号为 1 到 n。输入的结尾由 n = m = 0 的行指定。
输出
对于每个测试案例，在单行上打印案例编号（从 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
分析，注意并查集的几个函数的优化，初始化init需要同时把每个树的高度设为1；查询find需要在内部同时更改归集，以便下次查找的复杂度为O(1)；合并union中考虑每个数的高度，以便最小树高度，查询的时候耗时最低
#include <cstdio>
#include <cstring>
#define maxn 50005
int s[maxn];
int height[maxn];
void init_set(){
for(int i = 1;i < maxn;i++){
s[i] = i;
height[i] = 0;
}
}
int find_set(int x){
int r = x;
while(r != s[r]) r = s[r];
int i = x, j;
while(i != r){
j = s[i];
s[i] = r;
i = j;
}
return s[x];
}
void union_set(int x, int y){
x = find_set(x);
y = find_set(y);
if(height[x] == height[y]){
height[x]++;
s[y] = s[x];
}
else if(height[x] < height[y]) s[x] = s[y];
else s[y] = s[x];
}
int main() {
int t, n, m,x, y;
int kase = 0;
while(scanf("%d%d", &n, &m)){
if(n == 0 && m == 0) break;
init_set();
for(int i = 1;i <= m;i++){
scanf("%d%d", &x, &y);
union_set(x, y);
}
int ans = 0;
for(int i = 1;i <= n;i++){
if(s[i] == i) ans++;
}
printf("Case %d: %d\n", ++kase,ans);
}
return 0;
}