The Suspects （并查集问题模板）

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

题目大概翻译

在一所大学里有n个学生（这些学生的编号为0 ∼n−1）。这些学生由于兴趣爱好等原因组成了m个群体。

由于非典（SARS）流行，该大学的学生会需要排除可能的非典患者。

由于非典传染性强，学生会的成员假定：如果一个群体中有一个人是非典患者，那么这个群体中的所有人都是非典患者。

现在已知编号为0的学生为非典患者。请你找出这些学生中非典患者的人数。

输入输出格式

输入格式：

输入数据由多组数据组成。

每组数据包括m+1行：

第1行有两个由空格隔开的非负整数n和m，其意义如题目所述。

第2∼m+1行表示每个群体的人员信息，每行的第一个数字k表示该群体的人数，其后有k个用空格隔开的非负整数，表示这个群体的各个成员的编号。

当n=m=0时，表示输入结束，不需要处理之后的数据。

输出格式：

对于每组输入数据，输出一个整数，表示这组数据中非典患者的数量。每组数据的输出以换行符结尾。

。

题目分析；大概就是看和0的一个组的人数，是不是就可以想到树根问题，我们把树根一样的并在一起（并查集），然后遍历和0对比看是不是有相同树根。

又是一道模板题，听懂了记得给个赞鼓励一下，码字不易，用爱发电。

上ac代码。

有事你就q我；QQ2917366383

学习算法

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int p[40000];
int find(int x)//树根 
{
  if(p[x]!=x)return find(p[x]); return p[x];
}
int main()
{
  int n,m;
  while(cin>>n>>m)
  {   int ans=1;//开始就有一个学生有疫病
    memset(p,0,sizeof(p));//初始化 
    if(!n&!m)break;
    for(int i=0;i<n;i++)p[i]=i;//自己是自己的父亲节点 
    for(int i=1;i<=m;i++)
    {
      int num,x,y;  
        cin>>num>>x;//先读入群体里人的个数和第一个人的编号，这样方便之后合并 
      for(int i=2;i<=num;i++)
      {
        cin>>y; 
        p[find(y)]=find(x);//额，这步解释一下就是和第一个成员 x绑成为一个组； 
      }   
    }
    for(int i=1;i<n;i++)//遍历每个人 
      if(find(0)==find(i)) ans++;
          cout<<ans<<endl;
   } 
}