学步园

并查集基础

#include<stdio.h>
int set[100000];
int find( int i )
{
return set[ i ] == i ? i : set[ i ] = find( set[ i ] );//路径压缩
}//查找跟结点
void merge( int x,int y )
{
int a = find( x ), b = find( y );
if( a != b )
set[ a ] = b;//合并
 }
int main( )
{
int T,n,m,a,b;
    scanf( "%d",&T );
while( T-- )
    {
           scanf( "%d%d",&n,&m );
for( int i = 1; i <= n; ++i )
set[ i ] = i;
while( m-- ){
                  scanf( "%d%d",&a,&b );
                  merge( a,b );//合并
                  }
int c = 0;
for( int i = 1; i <= n; ++i )
if ( set[ i ] == i )//找有多少张桌子
++c;
           printf( "%d\n",c );
           }
return 0;
}