Massive Algorithms: POJ 1611 -- The Suspects

Description

Severe acute respiratory syndrome (SARS), an atypical pneumonia of unknown aetiology, was recognized as a global threat in mid-March 2003. To minimize transmission to others, the best strategy is to separate the suspects from others.
In the Not-Spreading-Your-Sickness University (NSYSU), there are many student groups. Students in the same group intercommunicate with each other frequently, and a student may join several groups. To prevent the possible transmissions of SARS, the NSYSU collects the member lists of all student groups, and makes the following 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 a student is recognized as a suspect. Your job is to write a program which finds all the suspects.

Input

The input file contains several cases. Each test case begins 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 and n−1, and initially student 0 is recognized as a suspect in all the cases. This line is followed by m member lists of the groups, one line per group. Each line begins with an integer k by itself representing the number of members in the group. Following the number of members, there are k integers representing the students in 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 be processed.

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

http://blog.sina.com.cn/s/blog_a0e9b50d0101az2c.html

首先输入n和m，代表n个学生和m个分组。学生按 0 ~ n-1 标号。接下来输入m行，表示每组的学生成员，每行第一个数为该组内的总人数k，后面k个数代表这个组内的k个学生。学生0感染了SARS，与它在一组的同学都会被感染，并且这些感染的同学也会去感染与其在一组的其他人。对于每组测试数据，输出被感染的学生数量

const unsigned int MAX=30010;//最大人数
int StuNum;//学生数量
int GrpNum;//分组数量
int father[MAX];//保存祖先
int people[MAX];//集合内人数
void Init()//初始化
{
   for(int i=0;i<StuNum;++i)
   {
       father[i]=-1;//每个人的祖先都是自己
       people[i]=+1;//每个组内有一个人（自己）
   }
}
int Find(int t)//找t的祖先
{
   if(father[t]==-1) return t;//如果本身就是根节点直接返回
   int temp=t;//保存原节点
   while(father[t]!=-1) t=father[t];//直到找到祖先
   father[temp]=t;//更新路径
   return t;//返回祖先
}
void Conbine(int a,int b)//将a，b合并为同一集合
{
   int fatherA=Find(a);//找到a的祖先
   int fatherB=Find(b);//找到b的祖先
   if(fatherA==fatherB) return;//若在一个集合直接返回
   father[fatherB]=fatherA;//把节点b的根连接到a的根上
   people[fatherA]+=people[fatherB];//累加节点a内人数
}
int main()
{
   //freopen("in.txt","r",stdin);
   while(scanf("%d%d",&StuNum,&GrpNum),StuNum+GrpNum)
   {
       Init();//初始化
       for(int i=0;i<GrpNum;++i)//输入每组信息
       {
           int num;//该组内人数
           int first;//第一个人以第一个人为根
           scanf("%d%d",&num,&first);
           for(int j=1;j<num;++j)
           {
               int other;
               scanf("%d",&other);//输入其他人
               Conbine(first,other);//合并为同一集合
           }
       }
       int r=Find(0);//找到0节点的根
       printf("%d\n",people[r]);//输出0的根节点的集合内人数
   }
   return 0;
}
Read full article from 1611 -- The Suspects

POJ 1611 -- The Suspects

Labels

Popular Posts