并查集之The Suspects（二）

71 阅读 0 评论 47 点赞

我是靠谱客的博主老实蜻蜓，这篇文章主要介绍并查集之The Suspects（二），现在分享给大家，希望可以做个参考。

题目链接：The Suspects

题意：病毒来了，n个学生，m个团体，每个学生有个自己的编号，一个学生可以有多个团体，一个人感染了，他团体里的人都被认为是怀疑对象，默认第0号同学为感染体，询问有多少人被感染了。

思路：用sum数组记录，在初始化设置为1，在联合时进行转移合并。
注意：poj不支持万能头…

复制代码

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long int

const int maxn = 30010;
int s[maxn];
int sum[maxn];
int n, m;

void Init(int n)
{
	for (int i = 0; i < n; i++)
	{
		s[i] = i;
		sum[i] = 1;
	}
}

int find(int x)
{
	if (s[x] != x)
		s[x] = find(s[x]);
	return s[x];
}

void Union(int a, int b)
{
	int aa = find(a);
	int bb = find(b);
	if (aa != bb)
	{
		s[bb] = aa;
		sum[aa] += sum[bb];
	}
}


int main()
{
	while(~scanf("%d %d",&n, &m))
	{
		if (n == 0 && m == 0) break;
		Init(n);
		while(m--)
		{
			int t, now, last;
			scanf("%d",&t);
			scanf("%d",&now);
			t -= 1;
			while(t--)
			{
				scanf("%d",&last);
				Union(now, last);
			}
		}
		printf("%dn",sum[find(0)]);
	}
	return 0;
}