并查集

作用：

1. 用来合并集合元素，并确定结合数量，查寻元素属于哪个集合。

2. 在图结构里（图里的点便是元素），确定两点是否处于联通状态，应用举例：

eg： 集合个数 Hdu 畅通工程

最小生成树 Hdu 还是畅通工程

#include <iostream>
#include <cstdio>
/*
	function: 1.合并
       		  2.查找

*/
#define MAXN 1010 
int pre[MAXN];

 int find(int& index)
{
	return pre[index] = pre[index] == index ? pre[index] : find(pre[index]);
}  

void Union(int& a,int& b)
{
	pre[find(a)] = find(b);
}

void init(int& n)
{
	for(int j = 0; j != n; j++)
		pre[j] = j;
}

int main()
{
	/*遍历一遍数组，发现数组里储存的元素是自己，则这个节点为其中一个元素的根
	比如 Hdu_1232_畅通工程，求得就是根得个数减去 1 
	*/ 
}

关于find函数

int find(int& index)
{
	return pre[index] = pre[index] == -1 ? pre[index] : find(pre[index]);
}

否则，便递归寻找下去。

。。。

知道找到了根， 把根的编号 一层层复制回集合中的其余元素，这是一种减支。

eg：

pre 0 1 2 3 4 5 6

1-2-3-4-4-3-3

给 find(a) 传进去一个参数0，从下标0开始找， pre[0]中存储的是1,表示pre[0]的父节点是1，

。。。

找到 pre[4]等于4，然后递归返回

把 4 赋值给 pre[4]

把 pre[4] --> pre[3]

把 pre[3] --> pre[2]

把 pre[2] --> pre[1]

把 pre[1] --> pre[0]

0 1 2 3 4 5 6

4 4 4 4 4 4 4