2524.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include "stdio.h"
#include "memory.h"
int s[50001];
int temp[50001];
int father( int a )
{
	int k=0;
	
	while( s[a]>=0 )
	{
		temp[k++] = a;
		a = s[a];
	}
	while( k-- )
	{
		s[ temp[k] ] = a;
	}
	return a;
}
int main()
{
	int n, m, a, b, ans, cas=1;
	while( scanf( "%d %d", &n, &m ) == 2 )
	{
		if( n==0 && m==0 )break;
		ans = n;
		memset( s, -1, (n+1)*sizeof(int) );
		while( m-- )
		{
			scanf( "%d %d", &a, &b );
			a = father(a);
			b = father(b);
			if( a != b )
			{
				if( s[a] < s[b] )
				{
					s[a] += s[b];
					s[b] = a;
				}
				else
				{
					s[b] += s[a];
					s[a] = b;
				}
				ans--;
			}
		}
		printf( "Case %d: %d\n", cas++, ans );
	}
	return 0;
}