Codeforces 278C Learning Languages(并查集) 求连通块

为什么最后还要getfather 一遍 比如 x 是 y 的父亲

然后你 Union(x,z) 然后 z 变成了 x 父亲 然后 y 的祖先就是错的了

题解 求一个无向图中有几个连通块 sum

特判 一下 如果 每一个人的语言都为 0 则答案为 sum

其他 答案则为 sum - 1

 

 

1 #include 
     
       2 using namespace std ;  3  4 const int N = 111 ;  5 int n,m,k,x,sum ;  6 int fa[N*2] ;  7 bool flag ;  8  9 inline int find(int x) 10 {11     if(fa[x]==x) return x ; 12     return fa[ x ] = find(fa[ x ]) ; 13 }14 15 inline void Union(int x,int y) 16 {17     x = find(x) ;  y = find(y) ; 18     if(x!=y) fa[ x ] = y ; 19 }20 21 int main() 22 {23     scanf("%d%d",&n,&m) ; 24     for(int i=1;i<=n+m;i++) fa[ i ] = i ;25     flag = 0 ;  26     for(int i=1;i<=n;i++) 27     {28         scanf("%d",&k) ; 29         if(k) flag = 1 ;  30         for(int j=1;j<=k;j++)31             scanf("%d",&x) ,Union( i,x+n ) ; 32     }33     if(!flag) 34     {35         printf("%d\n",n) ; 36         return 0 ; 37     }38     for(int i=1;i<=n;i++) fa[ i ] = find(fa[ i ]) ;       39     sort(fa+1,fa+n+1) ; 40     fa[ 0 ] = -100 ; 41     for(int i=1;i<=n;i++) if(fa[ i ]!=fa[ i-1 ]) sum++ ; 42     43     printf("%d\n",sum-1) ; 44     45     return 0 ; 46 }