简述

在计算机科学中，并查集是一种树型的数据结构，其保持着用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。有一个联合-查找算法（union-find algorithm）定义了两个操作用于此数据结构：

Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
Union：将两个子集合并成同一个集合。

因为它支持这两种操作，一个不相交集也常被称为联合-查找数据结构（union-find data structure）或合并-查找集合（merge-find set）。其他的重要方法，MakeSet，用于建立单元素集合。有了这些方法，许多经典的划分问题可以被解决。

为了更加精确的定义这些方法，需要定义如何表示集合。一种常用的策略是为每个集合选定一个固定的元素，称为代表，以表示整个集合。接着。Find(x)返回x所属集合的代表，而Union使用两个集合的代表作为参数。

（以上内容复制自维基百科）

集合的查找

集合的查找的作用就是寻找一个元素的父亲。我们首先设置了一个father[x]数组，他记录了表示x的“父亲”的编号，数组元素的值全都设置为father[x] = x，即节点的父亲就是它本身。

那么接下来我们就可以通过迭代的方式来不断的递推，直到找到了x = father[x]的时候，那么我们就能说x就是这个集合最原始的父亲了。

C++代码如下：

int findset(int x)
{
    while (x != father[x])
    {
        x = father[x];
    }
    return x;
}

但是一旦元素一多起来，或退化成一条链，每次findset(x)都将会使用O(n)的复杂度，这显然不是我们想要的。

对此，我们必须要进行路径压缩，即我们找到最久远的祖先时“顺便”把它的子孙直接连接到它上面。这就是路径压缩了。

C++代码如下：

//非递归式
int findset(int x)
{
    int k, j, r;
    r = x;
    while (r != father[r])
    {
        r = father[r];
    }
    k = x;
    while (k != r)
    {
        j = father[k];
        father[k] = r;
        k = j;
    }
    return r;
}

//递归式
int findset(int x)
{
    return father[x] == x ? x : father[x] = findset(father[x]);
}

集合的合并

操作很简单：还是使用father[x]数组。那么，合并两个不相交集合的方法就是，找到其中一个集合最父亲的父亲（也就是最久远的祖先），将另外一个集合的最久远的祖先的父亲指向它。简单的说就是将两个集合的父亲指向同一个父亲。

C++代码如下：

void unionset(int a, int b)
{
    a = findset(a);
    b = findset(b);
    if (a != b) father[a] = b;
}

其中findset(x)表示的是寻找x的父亲节点。

集合的按秩合并

集合的合并的时候有一个问题，就是两个集合的父亲到底谁指向谁，其实都没问题。问题就是谁更优。

显然，合并之后高度比较小的集合更加的优化，查找操作更加的节省时间。因此我们就可以将高度比较小的集合合并到高度比较大的集合上面，这样就能保证高度最小了。

要维持这样的合并方式，我们需要引入一个rk[x]数组，记录的就是x的最子节点开始，到x的高度。通过rk[x]的值进行合并就可以将低深度的集合合并到高深度的集合了，但是需要将其初始化：memset(rk, 0, sizeof(rk))。

C++代码如下：

void unionset(int a, int b)
{
    a = findset(a);
    b = findset(b);
    if (a == b) return;
    if (rk[a] > rk[b]) father[b] = a;
    else
    {
        if (rk[a] == rk[b]) rk[b]++;
        father[a] = b;
    }
}

参考资料

[1] 并查集详解 By nedushy123

[2] 并查集 - 维基百科