并查集

并查集（Disjoint Set Union, DSU）是一种数据结构，用于处理不相交集合（disjoint sets）的合并（union）和查询（find）操作。并查集特别适用于动态连通性问题，例如判断两个元素是否在同一个集合中或合并两个集合。广泛应用在图论算法中，比如 Kruskal 最小生成树算法。

并查集的概念

并查集主要支持两个操作：

  1. 查找（Find）：确定元素所属的集合。通常返回集合的“代表元素”。
  2. 合并（Union）：将两个集合合并成一个集合。

并查集使用树结构来表示集合，每个集合中的元素都指向一个根节点，根节点代表该集合。为优化效率，通常使用以下两种技术：

  • 路径压缩（Path Compression）：在查找操作中，将树的高度降低，使得查找的时间复杂度接近常数。
  • 按秩合并（Union by Rank）：在合并操作中，将较小的树合并到较大的树上，避免树变得过于深。

并查集的性质

  1. 时间复杂度：使用路径压缩和按秩合并的并查集可以将单次操作的平均时间复杂度优化到几乎为常数，接近 $O(\alpha(n))$ ，其中 $(\alpha)$ 是阿克曼函数的逆，非常接近常数。
  2. 空间复杂度：并查集使用 (O(n)) 的空间，其中 (n) 为元素个数。

并查集的 C++ 实现

以下是并查集的标准实现代码，包含路径压缩和按秩合并优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <vector>
using namespace std;

class DisjointSet {
private:
    vector<int> parent;  // 存储每个节点的父节点
    vector<int> rank;    // 存储树的高度（秩）

public:
    // 初始化并查集
    DisjointSet(int n) {
        parent.resize(n);
        rank.resize(n, 0);  // 初始秩为 0
        for (int i = 0; i < n; i++) {
            parent[i] = i;  // 每个节点的父节点初始化为自己
        }
    }

    // 查找操作，带路径压缩
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // 递归查找并路径压缩
        }
        return parent[x];
    }

    // 合并操作，按秩合并
    void unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            // 将秩低的树合并到秩高的树上
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }

    // 检查两个元素是否在同一个集合中
    bool isConnected(int x, int y) {
        return find(x) == find(y);
    }
};

int main() {
    DisjointSet ds(10);  // 创建包含10个元素的并查集

    // 合并一些集合
    ds.unionSets(1, 2);
    ds.unionSets(2, 3);
    ds.unionSets(4, 5);
    ds.unionSets(6, 7);

    // 查询集合连接情况
    cout << "Is 1 connected to 3? " << (ds.isConnected(1, 3) ? "Yes" : "No") << endl;
    cout << "Is 1 connected to 4? " << (ds.isConnected(1, 4) ? "Yes" : "No") << endl;

    // 合并更多集合
    ds.unionSets(3, 4);
    cout << "Is 1 connected to 5 after union? " << (ds.isConnected(1, 5) ? "Yes" : "No") << endl;

    return 0;
}

代码解释

  1. 初始化：

    • parent 数组存储每个节点的父节点，初始时每个节点的父节点是自己，表示每个元素独立的集合。
    • rank 数组存储每个集合的秩，初始为 0。

  2. 查找操作 find：

    • 通过递归查找，找到元素所属集合的根节点，并进行路径压缩，将路径上的所有节点直接连接到根节点。
    • 路径压缩可以减少后续查找操作的时间复杂度。

  3. 合并操作 unionSets：

    • 先找到两个元素所属集合的根节点，通过秩大小决定合并方向。
    • 将低秩的集合合并到高秩集合上，以保持树的高度较低；如果秩相同，将任意一个根连接到另一个根，同时增加连接根的秩。

  4. 连接检查 isConnected：

    • 检查两个元素是否属于同一集合，如果根节点相同则属于同一集合。

输出示例

假设输入是如上代码中的操作，输出将如下：

1
2
3
Is 1 connected to 3? Yes
Is 1 connected to 4? No
Is 1 connected to 5 after union? Yes

通过路径压缩和按秩合并优化后的并查集，能够高效地支持合并和查找操作。