并查集

一：背景

并查集（Union-Find Set），也叫Disjoint Set，由Bernard A. Galler和Michael J. Fischer在1964年提出，它主要是用来解决动态连通性问题。

什么是动态连通性问题？

如上图，若两点之间存在一条路线可以相互连接，那么这两个点就是连通的。现在如果我们一边新加入更多的点和路径，一边又要立即得到随机某两点是否连通，那么这该如何实现呢？

二：算法分析与实现

并查集的思想非常简单，把那些彼此连通的点连起来形成一棵树，如下图，

那么我们要判断某两点是否连通，只需判断它们的根是否相同即可。代码如下，

#include <iostream>

using namespace std;

#define N 10

int pre[N];

void Init()
{
    for (int i = 0; i < N; i++)
        pre[i] = i;
}

int Find(int i)
{
    if (pre[i] == i)
        return i;

    int i_parent = pre[i];
    int i_root = Find(i_parent);

    return i_root;
}

void Union(int i, int j)
{
    int i_root = Find(i);
    int j_root = Find(j);

    if (i_root == j_root)
        return;

    pre[i_root] = j_root;
}


int main()
{
    Init();

    Union(2, 9);
    Union(4, 9);
    Union(3, 4);
    Union(5, 6);

    // 判断 3 和 5 是否连通
    if (Find(3) == Find(5))
        cout << "3 和 5 连通.\n";
    else
        cout << "3 和 5 不连通.\n";

    return 0;
}

三：算法优化

从上面的代码可以看出，算法的复杂度主要在 Find 函数中，而 Find 的快慢主要由树的高度决定，那么我们的问题就转化为 如何降低树的高度 ，常用的方法有两个： Path Compression 和 Union By Rank 。

（1）Path Compression（路径压缩）

因为我们只想要快速地找到根结点，对沿途经过的那些结点并不关心，因此可以在 Find 查找过程中，将沿途经过的每一个结点的父亲直接设置为根结点，如下图，

int Find(int i)
{
    if (pre[i] == i)
        return i;

    int i_parent = pre[i];
    int i_root = Find(i_parent);

    pre[i] = i_root; // 路径压缩

    return i_root;
}

从上图可以看到，压缩后，树的高度变低了。

但我们要清楚，路径压缩其实是牺牲了路径完整性来求得更高效的运行速度，对于某些需要输出路径的应用场景，路径压缩这种优化就无法使用了。

（2）Union By Rank（按秩合并）

Rank 翻译为"秩"，在这里，我们可以简单地理解成"树的高度"，见下图，

void Union(int i, int j)
{
    int i_root = Find(i);
    int j_root = Find(j);

    if (i_root == j_root)
        return;

    if (rank[i_root] > rank[j_root])
        swap(i_root, j_root);

    pre[i_root] = j_root;

    if (rank[i_root] == rank[j_root]) // 两个秩相同的树合并，则整体的秩就会增加 1
        rank[j_root]++;
}

（3）更多的优化方法

上面讲的只是平时常用的两种，在维基上还有更多的优化方法，包括Path Having、Path Splitting等等，需要了解的朋友可以到 这里 。

四：优化后的代码

下面的代码同时使用了路径压缩和按秩合并优化。

#include <iostream>
#include <algorithm>

using namespace std;

#define N 10

int pre[N];
int rank[N];

void Init()
{
    for (int i = 0; i < N; i++)
    {
        pre[i] = i;
        rank[i] = 0;
    }
}

int Find(int i)
{
    if (pre[i] == i)
        return i;

    int i_parent = pre[i];
    int i_root = Find(i_parent);

    pre[i] = i_root; // 路径压缩

    return i_root;
}

void Union(int i, int j)
{
    int i_root = Find(i);
    int j_root = Find(j);

    if (i_root == j_root)
        return;

    if (rank[i_root] > rank[j_root])
        swap(i_root, j_root);

    pre[i_root] = j_root;

    if (rank[i_root] == rank[j_root]) // 两个高度相同的树合并则整体的高度就会增加
        rank[j_root]++;
}

int main()
{
    Init();

    Union(2, 9);
    Union(4, 9);
    Union(3, 4);
    Union(5, 6);

    // 判断 3 和 5 是否连通
    if (Find(3) == Find(5))
        cout << "3 和 5 连通.\n";
    else
        cout << "3 和 5 不连通.\n";

    return 0;
}

五：算法复杂度

当不采用任何优化的情况下，并查集每次操作的最差时间复杂度为$O(n)$，即树退化为链表的时候。

当仅采用路径压缩优化时，每次操作的最差时间复杂度为$O(1+log_{2+f/n}n)$，这个值比$O(log_2n)$小，其中$f$为查找次数。

当仅使用按秩合并优化时，每次操作的最差时间复杂度为$Θ(log_2n) $。

当同时使用路径压缩和按秩合并优化时，摊还分析后，每次操作的最差时间复杂度为$O(log^∗n)​$，其中$log^∗n​$是 Iterated Logarithm 函数，实际使用中，它的值不超过5，如下图，这也就是说每次操作的实际复杂度，只有$O(1)​$。