算法笔记——并查集

算法笔记——并查集

并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题（即所谓的并、查）。

关于并查集的讲解有很多大佬的博客都写的很好，这里我主要是参考这篇文章——并查集

定义

并查集实际上是一种树形结构，可以用来查询连通分支的个数，属于同一连通分支的在同一棵树上

主要变量

pre[]:记录结点的前驱结点 rank[]:记录结点的高度 count:记录连通分支的个数

主要函数

init():初始化 join(x,y):合并x,y结点 find(x):查找x结点所在树的根节点

函数定义 1.find()

这里通过find要一直找到根节点，当pre[x]=x时即找到根节点 如果不等就一直往上查找即可，这里在返回时对pre[x]进行修改，可以压缩查找路径，具体原理在文章开头的博客中都有讲到

    int find(int x)
    {
        if (pre[x] == x)
            return x;
        else
            return pre[x] = find(pre[x]);
    }

2.join()

要想连接两个结点，只需要把其中一个结点所在树的根节点接到另一棵树的根节点即可

1. 首先判断两个结点是否属于同一棵树，即判断两个结点的根节点是否相等即可，如果相等，则两个结点已经连通，直接返回。
2. 这里我们希望将高度小的树连接到高度大的树上，这样可以缩小连接后树的高度，所以首先分别对两棵树根节点的高度进行判断，如果高度不相等，则将小的连接到大的上，此时连接后原本的rank不变，如果两棵树高度相等的话，则被连接上的树的高度要加1，这里大家可以自己画图看看，还是比较好理解的。
3. 两棵树相连后，总的连通分量的个数要减1

void join(int x, int y)
    {
        x = find(x);
        y = find(y);

        if (x == y)
            return;
        if (rank[x]