POJ1611 （简单并查集）
描述
严重急性呼吸系统综合症 (SARS) 是一种病因不明的非典型肺炎，于 2003 年 3 月中旬被确认为全球性威胁。为了尽量减少传染给他人，最好的策略是将嫌疑人与其他人分开。
在不传播你的疾病大学（NSYSU），有很多学生团体。同一小组中的学生相互交流频繁，一个学生可能会加入多个小组。为了防止SARS可能的传播，新中山大学收集了所有学生团体的成员名单，并在他们的标准操作程序（SOP）中制定了以下规则。
一旦团体中的一个成员成为嫌疑人，则该团体中的所有成员都成为嫌疑人。
然而，他们发现，当一名学生被认定为嫌疑人时，要识别所有嫌疑人并不容易。你的工作是编写一个程序来找到所有嫌疑人。
输入
输入文件包含多个案例。每个测试用例以一行中的两个整数 n 和 m 开头，其中 n 是学生数量，m 是组数。您可以假设 0 < n <= 30000 且 0 <= m <= 500。每个学生都由 0 到 n−1 之间的唯一整数编号，并且最初学生 0 在所有情况下都被识别为嫌疑人。这一行后面是组的 m 个成员列表，每组一行。每行以一个整数 k 开头，k 本身代表组中的成员数量。在成员数量之后，有 k 个整数代表该组中的学生。一行中的所有整数至少由一个空格分隔。
n = 0且m = 0的情况表示输入结束，不需要处理。
输出
对于每种情况，在一行中输出嫌疑人的数量。
输入样本
100 4
2 1 2
5 10 13 11 12 14
2 0 1
2 99 2
200 2
1 5
5 1 2 3 4 5
1 0
0 0
样本输出
4
1
1
直接并查集，注意最后判读与嫌疑人在一个集合的方法是判断根节点，虽然优化了查询，但是不能保证每个节点都被更改；
#include <cstdio>
#include <cstring>
#define maxn 50005
int s[maxn];
int height[maxn];
void init_set(){
for(int i = 0;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();
int k;
for(int i = 0;i < m;i++){
scanf("%d", &k);
scanf("%d", &x);
for(int j = 1;j < k;j++){
scanf("%d", &y);
union_set(x,y);
}
}
int ans = 0;
for(int i = 0;i < n;i++){
if(find_set(i) == find_set(0)) ans++;
}
printf("%d\n",ans);
}
return 0;
}