PKU 1611 The Suspects

1611 -- The Suspects

[問題]
いくつかのグループとそこに所属する生徒のメンバーの情報が与えられる。0番の生徒が強力な風邪菌(意訳)を持っていて、同じグループに所属している生徒に感染してしまう。感染は推移的であり、例えば aグループ と bグループ両方に所属している生徒が感染した場合、両方のグループの生徒全員に感染、以下これらの繰り返しとなる。
感染した生徒の人数を求めよ。

[解法]
適当に実装しても間に合うかもしれないが、今回はUF木を使った。

const int MAX_N = 30000;
int par[MAX_N];
int rank[MAX_N];
void init(int n){
  rep(i,n) par[i] = i;
  memset(rank,0,sizeof(rank));
}
int find(int x){
  if(par[x] == x) return x;
  else return par[x] = find(par[x]);  
}
void unite(int a,int b){
  a = find(a);
  b = find(b);
  if(a == b) return;
  if(rank[a] < rank[b]){
    par[a] = b;
  }else{
    par[b] = a;
    if(rank[a] == rank[b]) rank[a]++;
  }
}
bool same(int a,int b){
  return find(a) == find(b);
}
int N,M;
int main(){
  while(cin>>N>>M,(N|M)){
    init(N);
    rep(i,M){
      int k; cin>>k;
      int first; cin>>first;
      rep(j,k - 1){
	int tmp; cin>>tmp;
	unite(first,tmp);
      }
    }
    int ans = 0;
    for(int i = 0; i < N;i++)
      if(same(0,i))ans++;
    
    cout<<ans<<endl;
  }
}