C - The Suspects

133 阅读 0 评论 88 点赞

我是靠谱客的博主等待花卷，这篇文章主要介绍C - The Suspects，现在分享给大家，希望可以做个参考。

原题

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

输入文件包含多组数据。

对于每组测试数据：

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

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

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

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

样例

Sample Input

复制代码

1
2
3
4
5
6
7
8
9
10
100 4
2 1 2
5 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

Sample Output

复制代码

思路

并查集套一下就解决了，把每个社团的人连接到一起，最后看有多少个人和0号学生没有关联即可。

代码

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<iostream>
#define ll long long
using namespace std;
int fa[30008];
int ss[30008];
int cnt[30008];
int n,m;
int k;

int find(int x)
{
	return x==fa[x]? x : fa[x]=find(fa[x]);
}

void merge(int x,int y)
{
	x=find(x);
	y=find(y);
	if(x!=y)
	{
		fa[x]=y;
		cnt[y]+=cnt[x];
	}
	return;
	
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//cin >> n >> m;
	while(scanf("%d %d",&n,&m) != EOF)
	{
		if(n==0 && m==0)
			break;
		if(m==0)
		{
			cout<<"1"<<endl;
		//	cin >> n >> m;
			continue;
		}
		for(int i=0;i<n;i++)
		{
			cnt[i]=1;
			fa[i]=i;
		}
		while(m--)
		{
			cin >> k;
			if(k==0)
				continue;
			for(int i=1;i<=k;i++)
				cin >>ss[i];
			for(int i=2;i<=k;i++)
				merge(ss[i],ss[1]);
		}
		cout<<cnt[find(0)]<<endl;
	//	cin >> n >>m;
	}

    return 0;
}