kuangbin 并查集 - POJ - 1611 The Suspects （并查集模板题）

传送门 Click here ~~

题意：

小明被确诊了非典病毒，小明必须被隔离治疗，并且与他直接或间接接触者都要隔离观察。同一个社团内如果有人感染病毒或可能感染病毒，那么这个社团内所有人都被认为是可能已经感染了病毒，由于时间紧迫，需要尽快找到所有可能携带病毒的同学并隔离，以防止更大范围的病毒扩散，院长请你帮忙编写程序计算需要隔离多少人。

题解：模板题。
Click here ~~~ 可以看一下这个并查集模板解释，应该是能看懂的。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<algorithm>#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long
// #define int ll
#define INF 0x3f3f3f3f
using namespace std;
int read()
{
    int w = 1, s = 0;char ch = getchar();while (ch < '0' || ch>'9') {
     if (ch == '-') w = -1; ch = getchar(); }while (ch >= '0' && ch <= '9') {
     s = s * 10 + ch - '0';    ch = getchar(); }return s * w;
//最大公约数
}
int gcd(int x,int y) {
    if(x<y) swap(x,y);//很多人会遗忘，大数在前小数在后//递归终止条件千万不要漏了，辗转相除法return x % y ? gcd(y, x % y) : y;
}
int lcm(int x,int y)//计算x和y的最小公倍数
{
    return x * y / gcd(x, y);//使用公式
}
//------------------------ 以上是我常用模板与刷题几乎无关 ------------------------//
const int N = 30010;
int p[N];  //存储每个同学的结点int find(int x)//返回x的祖宗节点+路径压缩
{
    if (p[x] != x)//如果当前节点x不是根节点的话，就会往上走一层。p[x] = find(p[x]);//就返回父节点的祖宗节点return p[x];
}
int main()
{
    int n, m;while (~scanf("%d%d", &n, &m) && (n+m) ){
    //编号for (int i = 0; i < n; ++i)p[i] = i;for (int i = 0; i < m; ++i) {
    //tot是人数，num1是第一个同学，num2是第二个同学int tot, num1, num2;scanf("%d%d", &tot, &num1);for (int j = 1; j < tot; ++j) {
    scanf("%d", &num2);if (find(num1) != find(num2)) {
    //num2的祖宗节点的父亲 == num1的祖宗节点p[find(num2)] = find(num1);//find()返回祖宗节点+路径压缩}}}int sum = 1;for (int i = 1; i < n; ++i) {
    //回溯到根节点判断if (find(p[i]) == find(p[0])) sum++;}printf("%d\n", sum);}return 0;
}