UVa 10583 - Ubiquitous Religions

//UVa 10583 - Ubiquitous Religions

#include <iostream>
#include <vector>
#include <stdio.h>
using namespace std;

vector<int> have[50001];
int color[50001];
int count[50001];

void paint(int c1, int c2) {
	for (int j = 0; j < have[c1].size(); j++) {
		color[have[c1][j]] = c2;
		have[c2].push_back(have[c1][j]);
	}
	have[c1].clear();
	count[c2] += count[c1];
	count[c1] = 0;
}

int main() {
	int n, m, t = 0;
	while ((cin >> n >> m) && (n || m)) {
		t++;
		for (int i = 1; i <= n; i++) {
			color[i] = i;
			count[i] = 1;
			have[i].clear();
			have[i].push_back(i);
		}
		int sol = n;
		for (int j = 0; j < m; j++) {
			int a, b;
			cin >> a >> b;
			if (color[a] != color[b]) {
				if (count[color[a]] < count[color[b]])
					paint(color[a], color[b]);
				else
					paint(color[b], color[a]);
				sol--;
			}
		}
		printf("Case %d: %d\n", t, sol);
	}
	return 0;
}