POJ——1611 The Suspects

题目大意

这题将的就是有n个人，被分成m组（每个人可能在几个组里面），其中0号人物肯定是患有非典。而与0号同组的人物也可能患有非典。以此类推，与与0号同组的人同组也可能患病。而本题就是要我们找出有哪些人可能患病。第一行为人数N和组数M，下面M行第一个数字为本组人数，之后为本组人的编号。编号一定成0到N-1。

样例输入

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

样例输出

4

1

1

题目分析

这个题目其实就是个简单的并查集，把大的号数向小的号数并，这样能保证可以直接找到0之下有多少个子节点。而本题不能压缩路径（因为可能不在一个树上，这里还有些不明白若是以后明白会回来补充）。

错因分析

最早的时候我是按照我的方法，将pre数组里的所有值初始化为-1，然后记录该树的节点个数并以负数形式表示，合并的时候按照原来的写法若是成环就会树上节点个数就会翻倍。也就是说若是数字很多的时候并不断成同一个环的话，这个节点个数就可能以2的n次方的速度增长，然后超出数组范围，RE。其实特判若是成环则不并在一起应该是可以解决这个问题的（没试过），但是这样对我来说这道题便失去意义了。

代码如下：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define LL long long
using namespace std;
int n,m;

int pre[36000];

int Find(int x)
{
    if(pre[x] == x) return x;
    return  Find(pre[x]);
}

int Union(int R1 , int R2)
{
    int r1 = Find(R1) , r2 = Find(R2);
    if(r1 < r2)
    {
        pre[r2] = r1;
    }
    else if(r1 > r2)
    {
        pre[r1] = r2;
    }
}

void init()
{
    for(int i = 0 ; i < n ; i++)
        pre[i] = i;
}

int main()
{
    while(scanf("%d%d",&n,&m) && n || m)
    {
        init();
        while(m--)
        {
            int t,a,b;
            scanf("%d",&t);
            scanf("%d",&a);
            for(int i = 1 ; i < t ; i++)
            {
                scanf("%d",&b);
                Union(a,b);
            }
        }
        int con = 0;
        for(int i = 0 ; i < n ; i++)
        {
            if(Find(i) == 0) con++;
        }
        printf("%d\n",con);
    }
}