并查集¶

并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。它支持两种操作：

查询（find）：查询某个元素属于哪一个集合。
合并（union）：将两个集合合并为一个集合。

基本实现¶

并查集的基本思想就是以集合中的一个元素代表整个集合。

我们可以用一个树形的结构来表示一个集合，树上每一个结点都表示集合中的一个元素，树的根结点又可以用来代表整个集合。

使用一个数组 fa[] 来保存每一个结点的父结点。

int fa[MAX_N];

初始化¶

一开始，每一个元素都在不同的集合中，所以每一个结点的父结点都是它自己。

// 初始化
void init(int n)
{
    for (int i = 1; i <= n; ++i)
        fa[i] = i;
}

查询¶

查询时，只需要一层一层向上查询父结点，直到找到根结点。根结点的标志就是它的父结点依然是它本身。

递归¶

// find 操作
int find(int x)
{
    return (x == fa[x]) ? x : find(fa[x]);
}

非递归版本¶

// find 操作
int find(int x)
{
    while (x != fa[x])
        x = fa[x];
    return x;
}

如果要判断两个元素是否在同一个集合，只需要比较它们两个的根结点是否相同。

合并¶

合并时，只需要将其中一个集合的根结点的父结点设置为另一个集合的根结点。

// union 操作
void unionSet(int i, int j)
{
    fa[find(i)] = find(j);
}

路径压缩¶

很容易看出，上面合并和查找的时间复杂度都为 \(O(h)\)，\(h\) 为树的深度。

然而在某些情况下，一些集合的树可能形成一条长长的链，导致每一次查询的时间复杂度极高。考虑到我们只关心一个结点的根结点是谁，我们可以在每次 find 操作时，把路径上每一个结点的父结点直接设置为根结点，以此来减小树的深度。

递归¶

// 路径压缩 find
int find(int x)
{
    return (x == fa[x]) ? x : (fa[x] = find(fa[x]));
}

非递归版本¶

// 路径压缩 find
int find(int x)
{
    int root = x;

    // 找到根结点
    while (root != fa[root])
        root = fa[root];

    // 将路径上每一个结点的父结点设置为根结点
    while (x != root)
    {
        int temp = fa[x];
        fa[x] = root;
        x = temp;
    }

    // 返回根结点
    return root;
}

启发式合并（按秩合并）¶

在合并集合 \(A\) 和 \(B\) 时，无论将 \(A\) 合并进 \(B\) 还是将 \(B\) 合并进 \(A\)，结果都是正确的。然而不同的合并方式可能会对接下来查询的时间复杂度产生影响。如果将深度小的树合并到深度较大的树中，那么下一次查询时显然有更优的时间复杂度。

再使用一个数组 rank[] 来保存每一个结点的子树的深度（即以它为根结点的树的深度）。

int rank[MAX_N];

// 按秩合并 初始化
void init(int n)
{
    for (int i = 1; i <= n; ++i)
    {
        fa[i] = i;
        rank[i] = 1; // 一开始深度都是 1
    }
}

// 按秩合并 union 操作
void unionSet(int i, int j)
{
    // 找到两个根结点
    int x = find(i);
    int y = find(j);

    // 将深度小的树合并到深度大的树
    if (rank[x] <= rank[y])
        fa[x] = y;
    else
        fa[y] = x;

    // 如果两棵树的深度相同且根节点不同，则新树的深度 + 1
    if (rank[x] == rank[y] && x != y)
        rank[y]++;
}

需要注意的是，如果路径压缩和按秩合并一起使用，很可能会使 rank[] 的准确性降低。此时 rank[] 保存的是树深度的一个上界。

例题¶

相关文章
判断图中是否有环