藍橋杯每日一題（并查集）

可疑人員

知識點：并查集 思維

某學校共有 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;
}