蓝桥杯每日一题（并查集）

可疑人员

知识点：并查集 思维

某学校共有 n 个学生，编号 0∼n−1

该学校共有 m 个社团。

每个学生可以加入多个社团，也可以不参加任何社团。

该学校所在的地区爆发了非典型肺炎。

经查实，0 号学生为病毒携带的可疑人员，需要进行隔离观察。

为了防止疫情传播，学校还规定，一旦某社团出现病毒携带的可疑人员，则该社团的全体成员将全部被划分为病毒携带的可疑人员。

请你计算，该学校最终共有多少名学生被判定为病毒携带的可疑人员。

输入格式

输入包含多组测试数据。

每组数据第一行包含两个整数 n,m

接下来 m 行，每行描述一个社团的人员，首先包含一个整数 k，表示该社团的人数，然后包含 k 个整数，表示每个社员的编号。

当输入 n=0,m=0时，表示输入结束。

输出格式

每组数据输出一行结果，表示被判定为病毒携带的可疑人员的学生数量。

数据范围

输入最多包含 10 组数据。

1≤n≤30000

0≤m≤500

1≤k≤n

输入样例：

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在同一集合的节点个数即可
#include<iostream>
using namespace std;
#define IOS cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
int n,m,k;
const int N=3e4+10;
int pre[N];

int find(int x){
    if(pre[x]!=x) pre[x]=find(pre[x]);
    return pre[x];
}
int main(){
    IOS;
    int t,x;
   while(cin>>n>>m&&n!=0||m!=0){
       for(int i=0;i<n;i++) pre[i]=i;
       while(m--){
           cin>>k>>x;    //先输入第一个
           for(int i=2;i<=k;i++){
               cin>>t;
               pre[find(t)]=find(x);//后面所有的合并到第一个节点
           }
       }
       int ans=0,target=find(0);
       for(int i=0;i<n;i++) ans+=(find(i)==target);
       cout<<ans<<endl;
   }
    return 0;
}