poj 1611 TheSuspects 并查集连通图

87 阅读 0 评论 58 点赞

我是靠谱客的博主激昂朋友，这篇文章主要介绍poj 1611 TheSuspects 并查集连通图，现在分享给大家，希望可以做个参考。

题意：
有一个学校，有N个学生，编号为0-N-1，现在0号学生感染了非典，凡是和0在一个社团的人就会感染，并且这些人如果还参加了别的社团，他所在的社团照样全部感染，求感染的人数。

Input：
输入文件包含几个事例。每个测试用例以一行中的两个整数n和m开始，其中n是学生数，m是组数。你可以假设0<n<=30000和0<=m<=500。每个学生都由一个介于0和n−1之间的唯一整数进行编号，在所有情况下，最初的学生0都被视为嫌疑犯。这一行后面是M组成员列表，每组一行。每行以一个整数k开头，该整数本身表示组中的成员数。在成员数之后，有k个整数表示这个组中的学生。一行中的所有整数都由至少一个空格分隔。
n=0，m=0的情况表示输入结束，不需要处理。

Output:
对于每种情况，输出一行中的嫌疑人数量

思路：
并查集的变种，实质是求0所在的强连通图的结点数目。
数据的输入只是告诉你哪些学生是同一个社团的。这个社团有num个孩子，第一个孩子不处理，从第二个孩子起，和上个孩子合并，这样就完成了他们的合并。ps：及时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
64
65
66
67
68
69
70
#include<iostream>
#include<string>
#include<cmath>
#include<ctype.h>
#include<memory.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<iomanip>
#include<set>
#include<list>
#include<vector>
#include<stack>
#include<queue>
#define ll long long int
using namespace std;
const int maxn = 30010;
int n, m;

int par[maxn];
int ans[maxn];

int find(int x)
{
	if (par[x] == x)
		return x;
	return par[x] = find(par[x]);
}
void initial()
{
	for (int i = 0; i <= n; i++)
	{
		par[i] = i;
		ans[i] = 1;
	}
}

int main()
{
	while (cin >> n >> m)
	{
		if (n == 0 && m == 0)
			break;
		initial();

		for (int i = 0; i < m; i++)
		{
			int num;
			cin >> num;
			int a, b, fa, fb;
			if (num != 0)
				cin >> a;
			fa = find(a);
			for (int j = 0; j < num - 1; j++)
			{
				cin >> b;
				fb = find(b);
				if (fa != fb)
				{
					par[fb] = fa;//b 归到a的类里
					ans[fa] += ans[fb];//a类里的数目新加上b里的数目
				}
			}

		}
		cout << ans[find(0)] << endl;
	}
	return 0;
}