题意：有n个学生，编号为0到n-1，m个群，给出每个群的学生，开始学生0被怀疑得了SARS，于是，人传人，被怀疑的学生所属群的所有学生都被怀疑，问共有几个学生被怀疑。
题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=789
——>>简单的并查集题目，将每个群的后一个学生与前一个学生judge，统计结点数输出即可。
带路径压缩递归写法：
#include <iostream>using namespace std;const int maxn = 30000 + 10; //0 < n <= 30000，开30000+10够矣int fa[maxn], height[maxn], cnt[maxn]; //fa[i]为i的父亲，height[i]为以i为根的树的高度，cnt[i]为以i为根的树的叶子的结点数int find(int x) //找根
{return fa[x] == x ? x : (fa[x] = find(fa[x]));
}bool judge(int x, int y) //判断、合并操作
{int new_x = find(x); //找x的根int new_y = find(y); //找y的根if(new_x == new_y) return 0;fa[new_y] = new_x; //将树new_y合并到new_x中cnt[new_x] += cnt[new_y]; //更新树new_x的叶子数return 1;
}int main()
{int n, m, i, j, num, first, temp; //num为一个GROUPR的人数，first为一个GROUP的第一个人while(cin>>n>>m){if(n == 0 && m == 0) return 0;for(i = 0; i < n; i++) //初始化{fa[i] = i; //建立n棵树，自己就是树根cnt[i] = 1; //只有自己，结点数为1}for(i = 0; i < m; i++){cin>>num>>first; //先输入第一个人，后面的人每一个都与前一个judgefor(j = 0; j < num-1; j++){cin>>temp;judge(first, temp);}}cout<<cnt[find(0)]<<endl;}return 0;
}
不那么地压缩写法：
#include <iostream>using namespace std;const int maxn = 30000 + 10; //0 < n <= 30000，开30000+10够矣int fa[maxn], height[maxn], cnt[maxn]; //fa[i]为i的父亲，height[i]为以i为根的树的高度，cnt[i]为以i为根的树的叶子的结点数int find(int x) //找根
{while(x != fa[x]){x = fa[x];}return x;
}bool judge(int x, int y) //判断、合并操作
{int new_x = find(x); //找x的根int new_y = find(y); //找y的根if(new_x == new_y) return 0;else{if(height[new_x] > height[new_y]) //当树new_x的高度 > 树new_y的高度时{fa[new_y] = new_x; //将树new_y合并到new_x中cnt[new_x] += cnt[new_y]; //更新树new_x的叶子数}else if(height[new_x] == height[new_y]) //当树new_x的高度 == 树new_y的高度时{fa[new_y] = new_x; //将树new_y合并到new_x中cnt[new_x] += cnt[new_y]; //更新树new_x的叶子数height[new_x]++; //树new_x的高度加1}else //当树new_x的高度 == 树new_y的高度时{fa[new_x] = new_y; //将树new_x合并到new_y中cnt[new_y] += cnt[new_x]; //更新树new_y的叶子数}return 1;}
}int main()
{int n, m, i, j, num, first, temp; //num为一个GROUPR的人数，first为一个GROUP的第一个人while(cin>>n>>m){if(n == 0 && m == 0) return 0;for(i = 0; i < n; i++) //初始化{fa[i] = i; //建立n棵树，自己就是树根cnt[i] = 1; //只有自己，结点数为1height[i] = 1; //只有自己，为1层}for(i = 0; i < m; i++){cin>>num>>first; //先输入第一个人，后面的人每一个都与前一个judgefor(j = 0; j < num-1; j++){cin>>temp;judge(first, temp);first = temp; //更新前者}}cout<<cnt[find(0)]<<endl;}return 0;
}