poj_1611 The Suspects

The Suspects

Time Limit: 1000MS	Memory Limit: 20000K
Total Submissions: 14762	Accepted: 7036

http://poj.org/problem?id=1611

Description

Severe acute respiratory syndrome (SARS), an atypicalpneumonia of unknown aetiology, was recognized as a global threat in mid-March2003. To minimize transmission to others, the best strategy is to separate thesuspects from others.
In the Not-Spreading-Your-Sickness University (NSYSU), there are many studentgroups. Students in the same group intercommunicate with each other frequently,and a student may join several groups. To prevent the possible transmissions ofSARS, the NSYSU collects the member lists of all student groups, and makes thefollowing rule in their standard operation procedure (SOP).
Once a member in a group is a suspect, all members in the group are suspects.
However, they find that it is not easy to identify all the suspects when astudent is recognized as a suspect. Your job is to write a program which findsall the suspects.

Input

The input file contains several cases. Each test casebegins with two integers n and m in a line, where n is the number of students,and m is the number of groups. You may assume that 0 < n <= 30000 and 0<= m <= 500. Every student is numbered by a unique integer between 0 andn−1, andinitially student 0 is recognized as a suspect in all the cases. This line isfollowed by m member lists of the groups, one line per group. Each line beginswith an integer k by itself representing the number of members in the group.Following the number of members, there are k integers representing the studentsin this group. All the integers in a line are separated by at least one space.
A case with n = 0 and m = 0 indicates the end of the input, and need not beprocessed.

Output

For each case, output the number of suspects in one line.

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

Source

Asia Kaohsiung 2003

题目大意：

第一行输入n个学生，m个组，接下来m行中第一个个输入该行的个数k，接下来输入k个数，输出与0在同一个组的同学有几个

解题思路：

这题是一个典型的并查集，只要将与0在同一个组的同学合并在一个组里面，最后在计算其总人数。初始化默认人数为1，合并一个人数加1，本题提交方式是G++.

代码实现：

#include <iostream>
#include<stdio.h>
#include<string.h>
using namespace std;

int stu[30002];
int group[30002];
int n,m;
//x的父亲是stu[x];
int find(int x)
{
    if(x==stu[x])
        return stu[x];
    stu[x]=find(stu[x]);
}

void unionSet(int a,int b)
{
	
    int x=find(a);
    int y=find(b);
    if(x==y)
    {
        return ;
    }
    //合并时，将元素较少的集合合并到元素较多的集合中
    if(group[x]<= group[y])
    {
        stu[x]=y;
        group[y]=group[y]+group[x];
    }
    else
    {
        stu[y]=x;
        group[x]=group[y]+group[x];
    }

}

int main()
{
    int i;
    while(scanf("%d %d", &n, &m)!=EOF && n != 0)
    {
         //为每个学生赋予一个编号0...N
        for(i=0;i<n;i++)
        {
            stu[i]=i;
            group[i]=1;//计数
        }
        while(m--)
        {
            int k,t,s;
            scanf("%d",&k);
            if(k>0)
            {
                //输入第一个数
                scanf("%d",&t);
            }
            for(i=1;i<k;i++)
            {
                scanf("%d",&s);
                unionSet(t,s);
            }
        }
        //查找0所在集合中的总数sum
        int sum=find(0);
        printf("%d\n",group[sum]);
    }

    return 0;
}