zoj1789The Suspects(简单并查集)

题目链接：zoj1789

/*
题目大意：
    n个人，m个小组，每个人可以加入多个小组，找出与0有关系的人
跟0在同一个组人和0有关系，如果一个与和0有关系的人在同一组，那么
这个人和0有关系，如：0,2为一组，2,5为一组，那么2和5都和0有关系

思路：并查集
*/
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           using namespace std; const int N = 3e4 + 10; int father[N]; void set(int n) { for(int i = 0; i < n; i ++) father[i] = i; } int find(int x) { if(x == father[x]) return x; return father[x] = find(father[x]); } void Union(int x, int y) { x = find(x); y = find(y); if(x < y) father[y] = x; else father[x] = y; } int main() { int n,m,t,x,y,i; while(scanf("%d%d",&n,&m),(n+m)) { set(n); while(m--) { scanf("%d%d",&t,&x); for(i = 1; i < t; i ++) { scanf("%d",&y); Union(x, y);//将每一行的第一个元素作为父节点 } } int ans = 1; for(i = 1; i < n; i ++) { //不能直接用father[i] == father[0] 来判断 //因为后输入的值在合并的时候可能会作为之前一些父节点的父节点 if(father[i] == father[0]) ans ++; } printf("%d\n",ans); } return 0; }