The Suspects POJ - 1611 （并查集）

106 阅读 0 评论 70 点赞

我是靠谱客的博主明亮唇彩，这篇文章主要介绍The Suspects POJ - 1611 （并查集），现在分享给大家，希望可以做个参考。

题目链接
并查集算法详解

题目描述

复制代码

1
2
3
4
5
6
7
    严重急性呼吸系统综合症(SARS)是一种病因不明的非典型肺炎，在
办法是把嫌疑人和其他人分开。在不扩散的你的疾病大学(NSYSU)中，有
许多学生团体。同一组中的学生经常相互交流，一个学生可以加入几个小
其标准操作程序(SOP)中制定了以下规则：一旦某一组成员成为嫌疑人，该
小组中的所有成员都是嫌疑人，但是，当学生被认定为嫌疑人时，很难
识别出所有的嫌疑人。你的工作是写一个程序找出所有嫌疑人。

输入

复制代码

1
2
3
4
5
6
多组输入。每个测试用例从一行中的两个整数n和m开始，其中n是学生的数
到n−1之间的唯一整数编号，在所有情况下，最初都将学生0识别为嫌疑这
一行后面跟着组的m个成员列表，每组一行。每一行的开头都是一个整数k
表示组中的成员数。在成员数之后，有k个整数代表这个组中的学生。一
行的理。

输出

复制代码

1
2
每个案件，输出一行嫌疑犯的数量。

Sample Input

复制代码

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

Sample output

复制代码

解题思路

复制代码

1
2
3
4
5
给了n个学生，然后是m行数据，每行数据的第一个数字表示有几个人。
学生0感染了非典，然后他的兴趣小组里的所有人也会感染非典，他所
在小组里面的其他成员如果参加了其他的社团，那么也会感染非典，
m就是小组的组数,问最后有多少个感染了的。

AC代码

复制代码

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
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;

int father[30500];
int ans[30500];//记录以 i 为根结点的人数
int find(int a)//查找根结点
{
    if (a!=father[a])
        father[a]=find(father[a]);
    return father[a];
}
void Unit(int x,int y)//合并
{
    x=find(x);
    y=find(y);
    if (x==y)return ;
    else
    {
        father[x]=y;
        ans[y]+=ans[x];
    }
}
int main()
{
    int n = 0, m = 0;
    while(scanf("%d%d", &n, &m)!=EOF)
    {
        if (m==0&&n==0)break;
        for (int i=0; i<n; i++)
        {
            father[i]=i;
            ans[i]=1;
        }
        int s,first,nxt;
        for (int i=0; i<m; i++)
        {
            scanf("%d%d", &s, &first);
            for (int j=0; j<s-1; j++)
            {
                scanf("%d", &nxt);
                Unit(first,nxt);
            }
        }
        printf("%dn", ans[find(0)]);
    }
    return 0;
}