POJ2524 Ubiquitous Religions

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>

using namespace std;
const int maxn = 50001;

int f[maxn+10];
int gn, gm;

int getFather(int x) {
	if(x == f[x]) return x;
	else return f[x] = getFather(f[x]);
}

int main()
{
	int Case = 0;
	int x, y, t1, t2;
	while(scanf("%d%d", &gn, &gm) == 2 && (gn || gm)) {
		for(int i = 1; i <= maxn; i++) f[i] = i;
		for(int j = 0; j < gm; j++) {
			scanf("%d%d", &x, &y);
			t1 = getFather(x);
			t2 = getFather(y);
			if(t1 != t2) f[t1] = t2;
		}
		int cnt = 0;
		for(int i = 1; i <= gn; i++) {
			if(f[i] == i) cnt++;
		}
		printf("Case %d: %d\n", ++Case, cnt);
	}
}

POJ2524 Ubiquitous Religions,布布扣,bubuko.com

POJ2524 Ubiquitous Religions

原文：http://blog.csdn.net/achiberx/article/details/21509635