GDUT寒假训练场3-The Suspects

题目描述

2019冠状病毒病(英语:Coronavirus disease 2019,缩写:COVID-19 ),是一种由严重急性呼吸系统综合症冠状病毒2型(缩写:SARS-CoV-2)引发的传染病。此病在全球各国大规模爆发并急速扩散,成为人类历史上致死人数最多的流行病之一。 很显然,目前最好的办法就是将所有可能的患者都隔离起来。 现在某高校正在排查可能的患者,这个高校中有多个社团,每个社团经常进行内部交流,一名学生可能会加入多个社团。学校认为一旦某个社团里出现一名可疑患者,这整个社团的学生都被视为是可能的患者。 现在请你帮忙找到这所学校的所有可能的患者。

输入格式

输入文件包含多组数据。

对于每组测试数据:

第一行为两个整数n和m, 其中n是学生的数量, m是社团的数量。0 < n <= 30000,0 <= m <= 500。

接下来m行,每一行有一个整数k,代表社团中学生的数量。之后,有k个整数代表这个社团里每个学生的编号(在0到n-1之间)。

n = m = 0表示输入结束,不需要处理。

输出格式

对于每组测试数据, 输出可能的患者数目。

输入样例

100 4
2 1 2
6 11 13 50 12 14
2 0 1
2 99 2
200 2
1 5
6 5 6 7 8 9 10
1 0
0 0

输出样例

4
1
1

参考思路

题目的意思是说0号学生是感染患者,只要有0号出现的社团都会被感染,然后被0号感染的学生加入其他社团又会感染别人,生化危机

那么我们用并查集将他们联系起来就可以了,最后遍历并查集数组,只要是和0号同属于一个集合的就加上,太惨了

参考代码 

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<sstream>
#include<string>
#include<map>
using namespace std;
typedef long long ll;
#define fo(i,l,r) for (int i = l; i <= r; ++i)
#define F 30005
int n, m, pa[F], f[105];
int find(int x)//查
{
    if (pa[x] != x)
        pa[x] = find(pa[x]);
    return pa[x];
}
void un(int x, int y)//并
{
    x = find(x);
    y = find(y);
    if (x != y)
        pa[y] = x;
}
int main()
{
    int fi, next, zu;
    int sum = 0;//答案个数
    while (1)
    {
        sum = 0;
        scanf("%d%d", &n, &m);
        fo(i, 0, n - 1)pa[i] = i;//初始化并查集数组
        if (n == 0 && m == 0)break;
        fo(i, 1, m)
        {
            scanf("%d", &zu);//社团人数
            scanf("%d", &fi);//这样子连容易理解一点
            fo(i, 1, zu - 1)
            {
                scanf("%d", &next);
                un(fi, next);
            }
        }
        fo(i, 0, n - 1)
        {
            if (find(i) == find(0))//查找
                sum++;
        }
        cout << sum << endl;
    }
    return 0;
}

如果有更好的方法或者有错误的地方,欢迎斧正。

感谢您的阅读!(*^▽^*)

上一篇:ELK搭建实时日志分析平台之一ElasticSearch搭建


下一篇:【洛谷P5305】旧词