并查集之The Suspects（二）

题目链接：The Suspects

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

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

#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;
}

最后

以上就是老实蜻蜓为你收集整理的并查集之The Suspects（二）的全部内容，希望文章能够帮你解决并查集之The Suspects（二）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。