poj 2524 Ubiquitous Religions(并查集)

题目链接：poj 2524 Ubiquitous Religions

题目大意：大学生有着自己的信仰，给出n表示有n个大学生，m表示有m次调查，给出a b，表示说a和b的信仰是相同的，现在问说这n个大学生有多少中信仰。

解题思路：并查集求联通分量，每次有两个不同的集合合成一个新的集合，联通分量就减少1.

#include <stdio.h>
#include <string.h>

const int N = 50005;
int n, m, f[N];

int getfar(int x) {
	return x == f[x] ? x : f[x] = getfar(f[x]);
}

int main () {
	int cas = 1;
	while (scanf("%d%d", &n, &m) == 2 && n + m) {
		for (int i = 0; i <= n; i++)
			f[i] = i;

		int a, b;
		for (int i = 0; i < m; i++) {
			scanf("%d%d", &a, &b);
			int p = getfar(a), q = getfar(b);
			if (p != q) {
				n--;
				f[q] = p;
			}
		}
		printf("Case %d: %d\n", cas++, n);
	}
	return 0;
}