POJ-1611 The Suspects

1、题意##

为了防止SARA传播，NSYSU收集所有学生组的成员列表，一旦群组中的成员是可疑人员，群组中的所有成员都是可疑人员。当学生被认定为患病嫌疑时，识别所有有嫌疑的学生并不容易。你的工作是写一个程序，找到所有的有嫌疑的学生。
也就是用并查集将每一组的同学连起来，一旦组内有一个人有嫌疑，直接排除ta所在的那组。

2、输入数据分析

100 4  //第一组样例，总数n = 100人， m = 4个小组
2 1 2  //第一个数据k代表小组总不能人数，后面数据是小组组员的号数
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 0 //n, m为0，结束输入

3、输出数据分析

4  //第1、3、4小组为感染者组，共4人
1
1

4、代码样例

#include <stdio.h>

int pre[50005]; //父节点数组
int lw[50005];
int i, j;

void ini(int n)  //预处理
{
    for(i = 0; i < n; i++)
    {
        pre[i]=i;
        lw[i]=1;//可用memset(lw, 0, sizeof(lw))放在for循环之前;
    }
}

int Find(int x) //查找根节点
{
    if(x!=pre[x])
        pre[x] = Find(pre[x]);
    return pre[x];
}

void uoin(int x,int y)//合并
{
    int xx = Find(x);
    int yy = Find(y);
    if(xx != yy)
    {
        pre[xx] = yy;
        lw[yy] += lw[xx];
    }
}

int main()
{
    int n, m, t, x, y, res;
    while(scanf("%d%d", &n, &m) != EOF)
    {
        if(n==0 && m==0) break;//n,m都为0，直接结束程序
        ini(n);
        for(i = 0; i < m; i++)
        {
            scanf("%d", &t);
            scanf("%d", &x);//输入小组第一号成员
            for(j = 1; j < t; j++)
            {
                scanf("%d", &y);//输入小组剩余成员
                uoin(x, y);//每输入一个和上一个连在一起
                x = y;
            }
        }
        res = Find(0);//看有没有0节点，如果有查找谁与0号连在一起
        printf("%d\n", lw[res]);//取个巧输出
    }
    return 0;
}

PS. 这题不能用#include<bits/stdc++.h>会挖