感染者 - The Suspects

这个题目用并查集来解答,很容易过的

Posted by isheng on July 18, 2016

感染者-仙术之并查集之术

原题题目

B - The Suspects

Time Limit:1000MS Memory Limit:20000KB 64bit IO Format:%I64d & %I64u

Description

严重急性呼吸系统综合症( SARS), 一种原因不明的非典型性肺炎,从2003年3月中旬开始被认为是全球威胁。为了减少传播给别人的机会, 最好的策略是隔离可能的患者。

在Not-Spreading-Your-Sickness大学( NSYSU), 有许多学生团体。同一组的学生经常彼此相通,一个学生可以同时加入几个小组。为了防止非典的传播,NSYSU收集了所有学生团体的成员名单。他们的标准操作程序(SOP)如下:

一旦一组中有一个可能的患者, 组内的所有成员就都是可能的患者。

然而,他们发现当一个学生被确认为可能的患者后不容易识别所有可能的患者。你的工作是编写一个程序, 发现所有可能的患者。

Input

输入文件包含多组数据。

对于每组测试数据:

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

每个学生编号是一个0到n-1之间的整数,一开始只有0号学生被视为可能的患者。

紧随其后的是团体的成员列表,每组一行。

每一行有一个整数k,代表成员数量。之后,有k个整数代表这个群体的学生。一行中的所有整数由至少一个空格隔开。

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

Output

对于每组测试数据, 输出一行可能的患者。

Sample Input

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

4

1

1

我的思路

刚开始,看到这个题目还没有什么头绪,后来看到公告上说要用并查集,所以赶紧果断的看了并查集的概念以及如何使用并查集,感觉很好,用了并查集,执行效率还不错,而且能够很好的解决这个问题,很开心,到时候我要把写并查集的那个文章贴粗来,留在我的博客,哈哈!

调试信息

本次调试结果并未记录,大概问题就是在使用并查集的时候,有些数据没有更新导致该数据的头指针还是原来的,没有缩短路径。

改进

有空就去看看其他人的解法。

AC代码

#include <cstdio>
#define w2tb_max 30010

int w2tb_pre[w2tb_max];

void w2tbFind(int x,int& y){
    int r = x;
    if(w2tb_pre[r] == -1) {
        r = -1;
        y = -1;
        return;
    }
    while(w2tb_pre[r]!=r)
        r = w2tb_pre[r];
    int i = x,j;
    while(i!=r){
        j = w2tb_pre[i];
        w2tb_pre[i] = r;
        i = j;
    }
    y = r;
}

int main(){
    int m,n,x,y,one;
    while(scanf("%d %d",&n,&m)!=EOF) {
        for (int k = 0; k <n; ++k) {
            w2tb_pre[k] = -1;
        }
        if(m == 0 && n == 0) break;
        while (m--){
            scanf("%d",&x);
            for (int i = 0; i < x; ++i) {
                scanf("%d",&y);
                if(i == 0) {
                    if(w2tb_pre[y] < 0)
                        w2tb_pre[y] = y,one = y;
                    else one = w2tb_pre[y];
                }
                else {
                    int xx;
                    w2tbFind(y,xx);
                    if(xx > -1){
                        w2tb_pre[one] = xx;
                        one = xx;
                    }
                    w2tb_pre[y] = one;
                }
                int xx;
                w2tbFind(w2tb_pre[y],xx);
            }
        }
        one = 0;
        y = 0;
        w2tbFind(y,m);
        int san;
        if(m == -1) printf("1\n");
        else {
            for (int j = 0; j < n; ++j) {
                w2tbFind(j,san);
                if (w2tb_pre[j] == m) one++;
            }
            printf("%d\n", one);
        }
    }
    return  0;
}

Coding是一件有趣的事!