当前位置: 代码迷 >> 综合 >> (求某个集合中元素的个数-基础并查集)poj1611 The Suspects
  详细解决方案

(求某个集合中元素的个数-基础并查集)poj1611 The Suspects

热度:82   发布时间:2023-11-02 20:04:03.0

 传送门:poj1611 The Suspects

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=30010;
int par[maxn],n,m;void init(){for(int i=0;i<n;i++)par[i]=i;
}int fi(int x){if(par[x]!=x) return par[x]=fi(par[x]);return par[x];
}void join(int x,int y){int fx=fi(x),fy=fi(y);if(fx!=fy){par[fy]=fx;}
}int main(){while(~scanf("%d%d",&n,&m)){if(n==0&&m==0) break;init();int k,a,b;while(m--){scanf("%d",&k);if(k>0){scanf("%d",&a);k--;while(k--){scanf("%d",&b);join(a,b);}}}int cnt=0;for(int i=0;i<n;i++){if(fi(0)==fi(i)) cnt++;}printf("%d\n",cnt);}return 0;
}