并查集入门

tips:本人不小心发到blog去了，好像是要发贴的，不过blog也懒得删了，就这样吧。

在我们平常生活中，无论是人与人之间还是动物与动物之间，都有直接或间接的关系，比如亲戚关系等，那么如果我给你一堆人的亲戚关系，并且问你这一堆人中的某两个人是否是亲戚关系，这个该如何实现呢？

我们可以假设，没有亲戚关系的两个人属于不同的家族，而家族我们又可以假设为集合，即这两个人属于不同的集合。
相信大家都听过家族树这个东西，就是下图所示的东东：
图片说明

这颗树表示同一家族的人，不同的树表示不同的家族，所以我们可以用树来表示家族（即集合）。
这里就到了引入并查集的时候了。
并查集的步骤是怎样的呢？
首先：我们先假设每个人刚开始都是一个集合（即自己是一个家族）。
然后：每次给出具有亲戚关系的两人时，就把这两个家族合并（即把这两个集合合并），如果这两个人本来就属于同一家族则不需要合并。
最后：每次询问两个人是否具有亲戚关系，我们只需要看他们是否处在同一集合即可。

实现的代码和注释如下（最初代的）：

//并查集的实现需要用到一个数组，我们定义一个全局数组来实现集合的功能。
int fa[10005];
（1）  初始化并查集
void init()//初始化并查集
{
//让每个元素自己成为一个集合，即元素只有自己的集合。
    for(int i=0;i<100005;i++)
        fa[i]=i;
}
（2）  合并结合
void Merge(int x,int y)//并查集合并结合
{
       int xx=Find(x),yy=Find(y);
      fa[xx]=yy;//让x所在的集合和y所在的集合合并。
}
（3）  查找节点所在集合
int Find(int x)//查找节点所在集合
{/*若一个元素的数值和所在集合对应数值相同，
说明这个集合的名字是这个元素的数值，即我们需要找到的集合*/
return fa[x]==x?x:Find(x);//找到根节点，即集合的名字
}

这时一个初代的并查集就完成了。

但是我们发现一个问题，这个初代的并查集效率特别低。
它的效率和树的深度有关，树的深度越大，查找所需要的时间就越长，所以如果要改善该算法，我们可以减小树的深度，那么我们该怎么改进呢？

路径压缩
给出下面两幅图来说明：

很明显，图一的树的深度为5，图二的树的深度为2，并查集询问操作时，图一最坏的情况要找五次才能找到所在集合，图二的最坏的情况只需要找两次即可找到所在集合，当数据量大的时候，在时间的效率上，明显图二对应的情况效率更高。
那么我们如何达到图二这样的效果呢?
就如图中的元素A,B,C,D,E,F,我们知道它们属于同一集合，并不需要知道他们的上一个元素是谁，而是只需要知道自己所在的集合，所以我们让所有的节点都指向根节点（即B,C,D,E,F指向A）。
那么该操作如何实现呢？我们无论是在询问操作还是在合并操作中都需要知道元素所在的集合，所以我们只需要在查找元素所在的集合的函数稍作修改即可，即更新路径（路径压缩）。
举个例子，过程如下：
假设有一集合有A,B,C,3个元素，另一个集合有D，E,两个元素，现在需要将两个集合合并。

合并后变成这样：

是不是和我们最优的图不太一样。
假设下一次调用该集合时，路过元素E，我们即可把元素节点E指向它的根节点。

因为无论询问还是合并操作，都需要知道自己所在的集合，所以我们只需要对查找自己所在的集合的函数稍作修改即可。
修改后的Find函数如下：
```
int Find(int x)//查找节点所在集合
{
    return fa[x]==x?x:(fa[x]=Find(fa[x]));
//fa[x]=Find(fa[x])就是用递归将路径上经过的所有节点指向根节点
}
```
按秩合并
什么是按秩合并呢？假如你现在要合并一棵高度为3的树和高度为2的树，你是要让高度为3的树并入高度为2的树还是高度为2的树并入高度为3的树呢？
下面给出两种并入结果
高度为3的树并入高度为2的树：

高度为2的树并入高度为3的树：

很明显，两种合并的方法，合并后所得的树的深度不同，我们前面知道了并查集的效率和树的深度有关，所以明显将高度为2的树并入高度为3的树后面的效率更好，即将深度小的树并入深度大的树。
那么我们如何实现这个过程呢？
假设我们定义一个数组
```
int Rank[10005];
```
用来表示每个元素对应集合的树的深度，初始时每个元素自己就是一个集合，所以Rank的初始值为1。

剩下的我们只需要修改合并函数即可，修改后的合并函数为：
```
void Merge(int i,int j)//按秩合并
{
    int x,y;
    x=findx(i),y=findx(j);
    if(Rank[x]<=Rank[y])//比较两棵树的深度
        fa[x]=y;
    else
        fa[y]=x;
//如果两棵树的深度相同，那么被并入的那个集合的树的深度加一
    if(Rank[x]==Rank[y]&&x!=y)
            Rank[y]++;
}
```