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

63 阅读 0 评论 42 点赞

我是靠谱客的博主甜美西牛，最近开发中收集的这篇文章主要介绍kuangbin 并查集 - POJ - 1611 The Suspects （并查集模板题），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

[kuangbin带你飞] 题单最短路问题 + 并查集问题模板题及简单题
https://blog.csdn.net/m0_46272108/article/details/108923142

题目传送门 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("%dn", sum);
    }
    return 0;
}