poj2524：Ubiquitous Religions

传送门

题目大意

一个学校有n(n<=50000)个学生，他们都可能信仰不同的宗教，你不能一个一个去问他们的信仰，但你可以通过询问得知两个学生的信仰是否一致，询问有m(m<=n*(n-1)/2)次。通过询问你可以知道校内学生的信仰总数上限，找到这个上限作为答案。

思路

其实就是一个并查集，题目翻译过来就是说给你一个图与它的一些边，找到所有的联通分量。

代码

#include <set>
#include <vector>
#include <cstdio>
#include <utility>
#include <iostream>

using namespace std;

const int N = 55000;

int cnt;
int n, m;
int dad[N];

void init(int top) {
	for(int i = 1; i <= top; i++) {
		dad[i] = i;
	}
}

int get(int x) {
	return dad[x] == x ? x : get(dad[x]);
}

void merge(int x, int y) {
	x = get(x);
	y = get(y);
	if(x != y) {
		dad[y] = x;
	}
}

int main() {
	while(scanf("%d%d", &n, &m)) {
		int ans = 0;
		if(n == 0 && m == 0) break;

		init(n);
		int a, b;
		for(int i = 1; i <= m; i++) {
			scanf("%d%d", &a, &b);
			merge(a, b);
		}

		for(int i = 1; i <= n; i++) {
			if(i == get(i)) {
				ans++;
			}
		}

		printf("Case %d: %d\n", ++cnt, ans);
	}

	return 0;
}

并查集

并查集的核心思想是记录某个节点的父节点是谁。它可以快速的判断某个节点是父节点是谁或者它属于哪个点集合(联通分量)。通常有三种操作：

初始化

初始状态每个节点的父节点就是自己。

void init(int n) {
	for(int i = 1; i <= n; i++) {
		father[i] = i;
	}
}

查询

递归遍历整个关系树，找到当前节点的父节点。

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

路径压缩

事实上，上述的查询函数在极端情况下的复杂度相当高。假设当前关系树是一条链，此时find函数的复杂度会达到O(n)。复杂度如此高的原因是每次find操作都递归到根节点才结束，而关系树真正的结构可能会无比畸形。

其实查询时我们只关注的是每个节点的父节点是谁，没人关心对于关系树真正的造型是什么样的。所以我们可以在find函数查找的同时，将路径上的每个节点的父节点都重设为根节点，这样就能做到往后每次查询的复杂度都是常数时间。

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

如上图，最终关系树会变成一个海胆的造型。

合并

通过将两个节点的父节点设为同一个来合并两个元素所在的集合，合并前判断当前节点是否已经属于同一个集合。

void merge(int x, int y) {
	x = get(x);
	y = get(y);
	if(x != y) {
		father[y] = x;
	}
}