并查集 | liangbm3's blog

1. 简介#

并查集（Disjoint Set Union, DSU） 是一种用来高效处理一些不相交集合的合并及查找问题的数据结构，它可以高效地完成两件事：

查找（Find）：确定一个元素属于哪个集合
合并（Union）：将两个不同集合合并成一个大的集合

因为这两个核心操作，它也被称为“Union-Find”数据结构。

2. 实现#

并查集的实现思路可以分为两种：Quick Find 和 Quick Union。这两种方式在如何组织数据以及执行 Find 和 Union 操作上有所不同。

2.1 Quick Find#

Quick Find 的核心思想是用一个数组 id[] 来存储每个元素所属集合的标识符。id[i] 的值就是元素 i 所在集合的 “名字”。

初始化：id[i] = i。每个元素都属于一个以自己为标识的独立集合。
Find (查找)：Find(p, q) 操作就是检查 id[p] 是否等于 id[q]。这是一个 O(1) 的操作，非常快，这也是它“Quick Find”名字的由来。
Union (合并)：Union(p, q) 操作稍微复杂。要将 p 和 q 所在的集合合并，需要遍历整个 id 数组。将所有与 id[p] 相同的元素的集合标识符，全部修改为 id[q] 的值。

C++代码实现如下：

#include <vector>

class QuickFind 
{
public:
    std::vector<int> id;

    // 初始化并查集
    QuickFind(int size) 
    {
        id.resize(size);
        for (int i = 0; i < size; ++i) 
        {
            id[i] = i;
        }
    }

    // 查找p和q是否在同一个集合
    bool Find(int p, int q) 
    {
        return id[p] == id[q];
    }

    // 合并p和q所在的集合
    void Union(int p, int q) 
    {
        int p_id = id[p];
        int q_id = id[q];

        if (p_id == q_id) 
        {
            return;
        }

        // 遍历整个数组，将所有属于p集合的元素，归入q集合
        for (int i = 0; i < id.size(); ++i) 
        {
            if (id[i] == p_id) 
            {
                id[i] = q_id;
            }
        }
    }
};

cpp

优点：Find 操作极快，时间复杂度为 O(1)。
缺点：Union 操作非常慢。每次合并都需要遍历整个数组，时间复杂度为 O(N)。如果进行 N 次合并操作，总时间复杂度会达到 O( $N^2$ )，在处理大规模数据时效率很低。

2.2 Quick Union#

Quick Union 是主流的并查集实现方式，它将数据组织成一个森林（多棵树），每个集合是一棵树。数组 parent[i] 存储的是元素 i 的父节点。

初始化：parent[i] = i。每个元素都是一棵单节点树的根。
Find (查找)：find(p) 操作是从节点 p 开始，沿着父节点指针一路向上，直到找到根节点（即 parent[i] == i 的节点）。这个根节点就是集合的代表。
Union (合并)：union(p, q) 操作是先分别找到 p 和 q 的根节点 rootP 和 rootQ。如果它们不相同，只需将一棵树的根节点设置为另一棵树的子节点即可。例如，parent[rootP] = rootQ。

C++ 代码实现如下：

#include <vector>

class QuickUnion 
{
public:
    std::vector<int> parent;

    // 初始化并查集
    QuickUnion(int size) 
    {
        parent.resize(size);
        for (int i = 0; i < size; ++i) 
        {
            parent[i] = i;
        }
    }

    // 查找p的根节点
    int Find(int p) 
    {
        while (p != parent[p]) 
        {
            p = parent[p];
        }
        return p;
    }

    // 合并p和q所在的集合
    void Union(int p, int q) 
    {
        int rootP = Find(p);
        int rootQ = Find(q);

        if (rootP != rootQ) 
        {
            parent[rootP] = rootQ;
        }
    }
};

cpp

优点：Union 操作非常快。只需要找到两个根节点并修改一次指针，时间复杂度主要取决于 Find 操作。
缺点：Find 操作可能很慢。在最坏的情况下，树可能退化成一条长链，导致 Find 的时间复杂度达到 O(N)。

可以看到虽然 Quick Union 解决了 Union 慢的问题，但引入了 Find 可能慢的新问题。为了解决 Find 的瓶颈，通常会引入路径压缩 (Path Compression) 和 按秩/大小合并 (Union by Rank/Size) 这两大优化。

2.3 路径压缩#

路径压缩是在 Find 操作中进行优化的，核心思想是当我们要查找一个节点 x 的根节点时，我们会从 x 出发，沿着父节点指针一路向上，直到找到根。在这个过程中，我们经过了一条路径。路径压缩的精髓在于：在找到根之后，将这条路径上的所有节点都直接连接到根节点上。下次再查找这条路径上的任何一个节点时，只需一步就能直接访问到根节点。这极大地降低了树的高度。

这通常是用递归来实现的，C++ 代码如下：

// 查找p的根节点，并进行路径压缩
int Find(int p) 
{
    if (parent[p] != p) 
    {
        // 递归向上查找根节点，
        // 并且在回溯时，将p的父节点直接设置为最终的根节点
        parent[p] = Find(parent[p]);
    }
    return parent[p];
}

cpp

2.4 按秩合并/按大小合并#

按秩合并是在 Union 操作中进行的，核心思想是为每个集合（即每棵树的根节点）维护一个叫做“秩” (rank) 的属性。rank 可以理解为树的高度的上界。在合并两个集合时，总是将秩较小的树的根节点，连接到秩较大的树的根节点上。

按大小合并与按秩合并非常相似，但维护的不是 rank，而是每个集合中元素的数量 (size)。在合并时，总是将节点数较少的树，合并到节点数较多的树上。

最终使用两种优化方式的并查集的 C++ 实现如下：

#include <vector>

class UnionFind 
{
public:
    std::vector<int> parent;
    std::vector<int> size;

    // 初始化并查集
    UnionFind(int n) 
    {
        parent.resize(n);
        size.resize(n, 1);
        for (int i = 0; i < n; ++i) 
        {
            parent[i] = i;
        }
    }

    // 查找元素i的根节点，并进行路径压缩
    int find(int i) {
        if (parent[i] == i) 
        {
            return i;
        }
        // 递归查找根，并将路径上所有节点直接指向根
        parent[i] = find(parent[i]);
        return parent[i];
    }

    // 按大小合并元素i和j所在的集合
    void unionElements(int i, int j) 
    {
        int rootI = find(i);
        int rootJ = find(j);

        if (rootI != rootJ) 
        {
            // 按大小合并：将小树合并到大树上
            if (size[rootI] < size[rootJ]) 
            {
                parent[rootI] = rootJ;
                size[rootJ] += size[rootI];
            } 
            else 
            {
                parent[rootJ] = rootI;
                size[rootI] += size[rootJ];
            }
        }
    }
};

cpp