学步园

题目：求并查集集合的个数。

分析：并查集。

#include <stdio.h>
#include <stdlib.h>

//union_set_begin
int sets[ 50001 ];
int rank[ 50001 ];

void union_set( int n )
{
	for ( int i = 0 ; i <= n ; ++ i ) {
		rank[i] = 0;
		sets[i] = i;
	}
}

int Find( int a )
{
	if ( a != sets[a] )
		sets[a] = Find( sets[a] );
	return sets[a];
}

int Union( int a, int b )
{
	if ( rank[a] > rank[b] )
		sets[b] = a;
	else {
		sets[a] = b;
		if ( rank[a] == rank[b] )
			rank[b] ++;
	}
}
//union_set_end

int main()
{
	int T = 1,N,M,x,y,a,b; 
	while ( scanf("%d%d",&N,&M) && N+M ) {
		union_set( N );
		for ( int i = 1 ; i <= M ; ++ i ) {
			scanf("%d%d",&x,&y);
			a = Find( x );
			b = Find( y );
			if ( a != b )
				Union( a, b ); 
		}
		int count = 0;
		for ( int i = 1 ; i <= N ; ++ i )
			if ( sets[i] == i )
				++ count;
		printf("Case %d: %d\n",T ++,count);
	}
	return 0;
}