可供快速查找的数据结构和算法总结之一并查集

最近学习了并查集、线段树、树状数组以及RMQ(Range Minimum Query)这几种关于快速查找
的数据结构和算法，并做了一些ACM的题目巩固了一下。准备写一下总结。
本次总结一下并查集：
并查集对解决不相交集合的合并查找操作非常有效，主要提供了一下几个方法：
make_set(x) 把每一个元素初始化为一个集合
find_set(x) 查找一个元素所在的集合
union_set(x,y) 合并x,y所在的两个集合
空间复杂度为O(N)，建立一个集合的时间复杂度为O(1)，N次合并M查找的时间复杂度为O(M Alpha(N))，
这里Alpha是Ackerman函数的某个反函数，在很大的范围内这个函数的值可以看成是不大于4的，所以并
查集的操作可以看作是线性的。
并查集针对不同的问题有两种不同的实现：
第一种：
make_set(x)的时候parent[x] = x,也就是根的parent指向自己，以此来判断这个元素是否为根元素，
rank值记录树的高度，合并的时候尽量让小的合并到大的集合上，这样可以减少数的高度。
代码如下：

int parent[50001];
int rank[50001];

void make_set(int x){
	parent[x] = x;
	rank[x] = 0;
}

//查找的时候，进行路径压缩parent[x] = find_set(parent[x]),
//把查找路径上的结点都指向跟结点，减小树的高度
int find_set(int x){
	if(x != parent[x]) parent[x] = find_set(parent[x]);
	return parent[x];
}

void union_set(int x,int y){
	int r1 = find_set(x);
	int r2 = find_set(y);
	if(r1 == r2) return;//如果两个元素在相同的集合中，直接retun;

	if(rank[r1] < rank[r2]//把rank值较小的集合合并到达的集合中
		parent[r2] = r1;
	else{
		if(rank[r1] == rank[r2])//两个rank值相等的树合并后rank要增加一
			rank[r2] += 1;
		parent[r1] = r2;
	}
}

第二种：
make_set的时候把parent[x] = -1，根节点parent记录了该集合元素个数
的相反数,所以这种方法很适合想知道某个元素所在的集合的个数的情况。

int parent[30001];

void make_set(int x){
	parent[x] = -1;
}

int find_set(int x){
	int p = x;
	while(parent[p] > 0) p = parent[p];//找到跟结点
	while(x != p){//查找并压缩路径，让查找路径上的每一个x的parent[x] = p,p为根节点
		int temp = parent[x];
		parent[x] = p;
		x = temp;
	}
	return x;
}

void union_set(int x,int y){
	int r1 = find_set(x);
	int r2 = find_set(y);

	if(r1 == r2) return;
	if(parent[r1] < parent[r2]){//集合小的合并到集合大的上，并更新集合元素个数的计数
		parent[r1] += parent[r2];
		parent[r2] = r1;
	}else{
		parent[r2] += parent[r1];
		parent[r1] = r2;
	}
}

以下是这两种并查集的两道ACM应用，可以巩固一下学习的知识：
poj2524 http://acm.pku.edu.cn/JudgeOnline/problem?id=2524
这道题目的主要意思是：n个大学生，指出m对宗教信仰相同的学生，然后让你估算这n个学生中最多
有多少种宗教信仰。
这道题很简单，把宗教数初始化为学生数n,对给出的每对大学生i,j，如果他们在不同的集合，那么
就合并，然后宗教的数量减一
以下是AC的代码：

#include<iostream>
using namespace std;

int parent[50001];
int rank[50001];

void make_set(int x){
	parent[x] = x;
	rank[x] = 0;
}

int find_set(int x){
	if(x != parent[x]) parent[x] = find_set(parent[x]);
	return parent[x];
}

void union_set(int x,int y){
	int r1 = find_set(x);
	int r2 = find_set(y);
	if(r1 == r2) return;

	if(rank[r1] < rank[r2])
		parent[r2] = r1;
	else{
		if(rank[r1] == rank[r2])
			rank[r2] += 1;
		parent[r1] = r2;
	}
}

int main(){
	int m,n;
	int ncases = 0;
	int i = 0;
	while(cin >> n >> m, n){
		int a,b;
		++ncases;
		for(i = 0; i < n; i++){
			make_set(i);	
		}

		for(i = 0; i < m; i++){
			cin >> a >> b;
			int x = find_set(a);
			int y = find_set(b);
			if(x != y){//不同的集合，合并并减一
				n--;
				union_set(x,y);
			}
		}
		cout << "Case " << ncases << ": " << n << endl;
	}
	return 0;
}

poj 1611 The Suspects http://acm.pku.edu.cn/JudgeOnline/problem?id=1611
这道题的意思是有一种传染病SARS，学生有很多的groups,如果groups的一个学生是疑似患者Suspect，
则整个组的其他人都是Suspects,但一个人可能属于不同的组，初始0是suspect,问学生中有多少个
Suspects.
这个题目很简单，把同一组的人进行合并，然后查找一个0元素所在集合元素的个数，由于要统计一个
集合元素的个数，所以使用第二种构造并查集的方法。
AC的代码：

#include<iostream>
using namespace std;

int parent[30001];

void make_set(int x){
	parent[x] = -1;
}

int find_set(int x){
	int p = x;
	while(parent[p] > 0) p = parent[p];
	while(x != p){
		int temp = parent[x];
		parent[x] = p;
		x = temp;
	}
	return x;
}

void union_set(int x,int y){
	int r1 = find_set(x);
	int r2 = find_set(y);

	if(r1 == r2) return;
	if(parent[r1] < parent[r2]){
		parent[r1] += parent[r2];
		parent[r2] = r1;
	}else{
		parent[r2] += parent[r1];
		parent[r1] = r2;
	}
}

int main(){
	int n,m,i = 0;
	while(cin >> n >> m, n){
		for(i = 0; i < n; i++){
			make_set(i);
		}

		for(i = 0; i < m; i++){
			int k;
			cin >> k;
			int first_s,s;
			cin >> first_s;
			for(int j = 1; j < k; j++){
				cin >> s;
				union_set(first_s,s);
			}
		}
		cout << -parent[find_set(0)] << endl;
	}
	return 0;
}

其他来自fandy_wang总结中提供的一些相关题目：
POJ 1182 食物链
并查集的拓展注意: 只有一组数据;
要充分利用题意所给条件:有三类动物A,B,C，这三类动物的食物链
构成了有趣的环形。A吃B， B吃C，C吃A。也就是说:只有三个group
POJ 2492 A Bug's Life 并查集的拓展
法一:深度优先遍历
每次遍历记录下该点是男还是女，只有:男-〉女，女-〉男满足，否则，找到同性恋，结束程序。
法二:二分图匹配
法三:并查集的拓展:和1182很像，只不过这里就有两组，而1182是三组,1611无限制
POJ 1861 Network == zju_1542    并查集+自定义排序+贪心求"最小生成树"
答案不唯一，不过在ZOJ上用QSORT()和SORT()都能过，在POJ上只有SORT()才能过...
POJ 1703 Find them, Catch them 并查集的拓展
这个和POJ 2492 A Bug's Life很像，就是把代码稍微修改了一下就AC了！
注意：And of course, at least one of them belongs to Gang Dragon, and the same for Gang Snake. 就是说只有两个组。
POJ 2236 Wireless Network        并查集的应用
需要注意的地方：1、并查集；2、N的范围，可以等于1001；3、从N+1行开始，第一个输入的可以是字符串。
POJ 1988 Cube Stacking            并查集很好的应用
1、与 银河英雄传说==NOI2002 Galaxy一样；2、增加了一个数组behind[x],记录战舰x在列中的相对位置；3、详细解题报告见银河英雄传说。
JOJ 1905 Freckles   == POJ 2560 最小生成树
法一：Prim算法；法二：并查集实现Kruskar算法求最小生成树
JOJ 1966 Super Market III == PKU 1456 Supermarket 带限制的作业排序问题（贪心+并查集）
提高题目：
POJ 2912 Rochambeau
POJ 1733 Parity game   
POJ 1308 Is It A Tree?