浅谈并查集

并查集，顾名思义，是一种适用于合并和查找的操作。

举个例子,比如说目前有10个国家，编号从1到10（任何一个公民属于且只能属于一个国家）。那么如何区分这些公民属于那个国家呢？最简单的方法，每个公民都记住自己国家的编号。比如我随便抓住个一个人A，我发现A保存的编号是1，那么A就属于1号国家。如果F保存的是2，那么F就属于2号国家。这样，我们就有了一个最简单的并查集，每个元素（公民）保存该集合的的一个编号（国家编号），这个编号可以是集合中最小元素的编号或者某个自定义的标记等。某种意义上说就是，每个公民都记住自己国家的编号，这种结构很简单，没有层级结构，扁平化。这样我们就得到了一个最简单的并查集。结构如下：

图片说明

这样A保存了自己属于的集合1，B也保存自己属于的集合1。这样存储的好处是查找效率高，比如我要查找F属于哪个集合，F中保存的数字是2，那F就属于2号集合，查找复杂度O（1），效率极高。那么合并操作呢？比如这时候有两个国家要合并，比如1号国家和2号国家要合并（把2号国家公民并入1号国家），这时我应该怎么操作呢，我应该遍历所有的元素，如果发现这个元素属于二号国家，那么修改为1号国家，所以合并的复杂度是O（n），没有查找那么高效了，下面看一下合并和查找的代码：

const int MAX=105;//总人数
int fat[MAX];//记录每个元素属于哪个集合
int find(int x){//查找x属于哪个集合
    return fat[x];
}
void mergy(int a,int b){//将a和b合并
    for(int q=0;q<MAX;q++){
        if(fat[q]==a)
            fat[q]=b;
    }
}

这是最基本的并查集，我们也很容易发现它的缺点——合并效率低，这在数据量不大的情况下还是可以接受的，可如果数据量变大，效率就是很低。那么能不能更好呢，在不显著影响查找性能的基础上，加快合并过程呢？当然有啦。由于第一种并查集合并效率太低，于是乎就有了类似于层级结构的并查集。

下面我们就介绍一种效率更高的并查集。还是用我们国家的例子，此时呢，每个公民保存的不再是自己国家的编号，而是自己上级的编号，什么意思呢，就类似于古代的诸侯，我要找出你属于哪个国家，首先要看你属于哪个部落，再看这个部落属于哪个诸侯，再看这个诸侯属于哪个国家，那么你就属于这个国家。这样查找的最差情况的时间复杂度是O（n），但由于我们合并时是随即合并，这种情况还是很少，几乎可以说没有。那么此时该怎么合并呢，这时候就简单多啦，比如国家1要和国家2合并。那么我们直接将国家2的首领的上级变为国家1的首领就好啦，合并就完成了。结构如下：

图片说明

此时我们1号国家和7号国家要合并，我们只需将1号节点（1号国家的首领指向2号国家首领2号结点即可），这样合并就完成了，下面看一下代码：

const int MAX=105;//总人数
int fat[MAX];//记录每个元素属于哪个集合
int find(int x){//查找x属于哪个集合
    while(x!=fat[x])
        x=fat[x];
    return x;
}
void mergy(int a,int b){//将a，b所在集合合并
    fat[find(a)]=find(b);
}

这就是优化后的并查集了，和第一种相比，整体效率还是提高的。

下面说下优化，我们第二种并查集在合并时，应该将深度小的树合并到深度大的树上，这样整颗树的深度就会最小。因为树的深度越深，查找效率也就越低，当然了，由于我们合并时是随机合并的，所以这种优化用的并不多；用的较多的还是下一种优化---缩短路径。缩短路径和记忆化搜索很像，思想就是如果我们已经访问过一个节点，那么我们在下一次访问时，就直接可以知道该节点属于哪个集合，简单的来说，如果某个人属于部落，那么我们通过回溯知道他属于哪个国家后，直接修改该节点的值为国家，那么下一次就可以直接知道该节点是哪个国家了，示意图如下：

图片说明

比如我们访问了1号国家的4号和6号节点，那么就直接修改4号和6号节点的值为1（去掉红色的边，增加紫色的边），那么在下一次访问时，就大大提高了效率。看一下代码：

const int MAX=105;//总人数
int fat[MAX];//记录每个元素属于哪个集合
int find(int x){//查找x属于哪个集合
    return x==fat[x]?fat[x]:fat[x]=find(fat[x]);
}
void mergy(int a,int b){//将a和b合并
    fat[find(a)]=find(b);
}