并查集

最近做了一道最小生成树的题，用Kruskal算法，用到了并查集，这里介绍一下

先看一下官方定义：

并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间（1～3秒）内计算出试题需要的结果，只能用并查集来描述。

并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。

并查集用来解决一些类似计算机网络，群的类型的题，

---

在任何一个带节点的图中，我们都可以把他优化为一个树状结构，数据结构课中老师都讲过，不记得也没关系，这里举个例子

左边是一个图状结构，右边是一个树状结构，如果比作电脑之见联网的话，无论这哪一种结构都可以互相传送文件，

我们可以这样理解，老大是老二和老三的爸爸，老二和老三又是老四的爸爸，老大可以说是它们的总爸爸，哈哈哈，然后变为树状结构，

下面开始正式切入正题，

1、初始化

假如我们用f[]数组来存树状结构，那么i的爸爸就是f[i]，所以刚才的树状结构中，f[2] ,f[3], f[4]都等于f[1]，而总爸爸可以说自己是自己的爸爸，我们也可以根据这个来判断他到底是不是总爸爸，所以初始化的作用就是每个人都是一个树状结构，每个人都是自己的爸爸，每个人都是总爸爸，最后解题的时候才根据题意让谁认谁当爸爸

for(int i=1;i<=n;i++) f[i]=i;

2、查找

查找的作用就是找到一个人的最终爸爸，解题当中如果需要判断两个人是不是在一个群中，我们就需要判断这两个人的总爸爸是不是同一个人

int find(int x)//查找x的爸爸 
{
	if(x==f[x]) return x;//如果x的爸爸是自己，他就是总爸爸 
	else return f[x]=find(f[x]);
	//x认最后的总爸爸当爸爸，相当于优化一下 
}

3、合并

当题目中要求让一个人假如另一个认的群中，如果只修改这个人的爸爸，也就是一个人认另一个人当爸爸，这时会破坏原来的数据结构，所以我们就需要把他们的总爸爸找出来，然后让一个总爸爸认另一个总爸爸当爸爸

void merg(int a,int b)//合并函数 
{
	int fa=find(a),fb=find(b); 
	if(fa!=fb) f[fa]=fb;
	//a的总爸爸（fa）认b的总爸爸（fb）当爸爸 
}

4、优化

好啦，上面就算是入门了，但是，敲黑板。。如果题目中时间卡的很紧的话，我们就需要优化一下啦，其实上面   “ x认最后的总爸爸当爸爸”  这一步， 已经优化了不少了，但是我们还可以在优化一下，

"按秩合并"。实际上就是在合并两棵树时，将高度较小的树合并到高度较大的树上。这里我们使用“秩”(rank)代替高度，秩表示高度的上界，通常情况我们令只有一个节点的树的秩为0，严格来说，rank + 1才是高度的上界；两棵秩分别为r1、r2的树合并，如果秩不相等，我们将秩小的树合并到秩大的树上，这样就能保证新树秩不大于原来的任意一棵树。如果r1与r2相等，两棵树任意合并，并令新树的秩为r1 ++

总的来说就是谁的树深一些谁当爸爸，并且两个人的深度相同时，当爸爸的人深度加一，这个自己画两棵树模拟一下就理解啦

void merg(int a,int b)//合并函数 
{
	int fa=find(a),fb=find(b); 
	if(fa!=fb) 
	{
		if(rank[fa]<rank[fb]) f[fa]=fb;
		//如果fb树深一些 ，fa 认fb当爸爸 
		else
		{
			f[fb]=fa;
			if(rank[fa]=rank[fb])
			rank[fa]++;
			//只有两棵树的深度相等才加一 
		}
	}
}