学步园

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=34121#problem/F

// File Name: f.cpp
// Author: bo_jwolf
// Created Time: 2013年10月16日 星期三 16:54:03

#include<vector>
#include<list>
#include<map>
#include<set>
#include<deque>
#include<stack>
#include<bitset>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
#include<sstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<ctime>

using namespace std;
const int maxn = 1000005;
int fa[ maxn ];
struct node{
	int x, y;
}edge[ maxn ];

void Union(){
	for( int i = 0; i < maxn; ++i ){
		fa[ i ] = i;
	}
}

int cmp( const node a, const node b ){
	if( a.x != b.x )
		return a.x < b.x;
	return a.y < b.y;
}

int find( int x ){
	return  fa[ x ] = ( x == fa[ x ] ? x : find( fa[ x ] ) );
}

int main(){
	int n, m, a, b, temp = 1;
	while( scanf( "%d%d", &n, &m ) != EOF ){
		Union();
		if( !n && !m )
			break;
		int k = 0;
		while( m-- ){
			scanf( "%d%d", &a, &b );
			edge[ k ].x = a;
			edge[ k++ ].y = b;
		}
		sort( edge, edge + k , cmp);
		int ans = n;
		for( int i = 0; i < k; ++i ){
			int x = find( edge[ i ].x );
			int y = find( edge[ i ].y );
			if( x != y ){
				fa[ x ] = y;
				ans--;
			}
		}
		printf( "Case %d: %d\n", temp++, ans );
	}			
return 0;
}