Disjoint Set Union 数据结构详解

1. 简介

Disjoint Set Union（DSU），也称为 Union-Find，是一种用于处理一组不相交集合的数据结构。它的核心操作包括：

合并两个集合（Union）
查询某个元素所属的集合（Find）
判断两个元素是否属于同一集合（Check）

在初始状态下，我们有一个包含 n 个元素的全集 U = {a₁, a₂, ..., aₙ}，每个元素自成一个集合。随着操作的进行，集合会被合并。DSU 的目标是在高效支持这些操作的同时，保持良好的时间复杂度。

2. DSU 的基本操作

DSU 支持以下三种核心操作：

**MAKE-SET(a)**：创建一个只包含元素 a 的集合。
**FIND-SET(a)**：返回 a 所在集合的代表（通常是树根）。
**UNION(a, b)**：将包含 a 和 b 的两个集合合并。

这两个操作可以回答两类常见问题：

Check Query：判断 a 和 b 是否属于同一个集合。
Union Query：合并 a 和 b 所在的集合。

具体实现中，Check Query 通过两次 FIND-SET 比较结果实现；Union Query 则直接调用 UNION。

3. DSU 的树表示法

DSU 最高效的实现方式是使用树森林（Forest of Trees）结构：

每个集合用一棵树表示；
每棵树的根节点是集合的代表；
每个节点保存父节点指针，根节点的父节点指向自己。

示例：初始状态

假设我们有集合 U = {a, b, c, d, e, f}，初始时每个元素都是独立的集合，形成 6 棵单节点树：

a   b   c   d   e   f
|   |   |   |   |   |
a   b   c   d   e   f

示例：执行 UNION 操作

执行 UNION(b, e) 和 UNION(c, d) 后，结构变为：

b     c     a     f
|     |
e     d

继续执行 UNION(a, f) 和 UNION(a, b) 后，最终结构为：

a
├── f
└── b
    └── e
c
└── d

此时：

FIND-SET(e) 返回 a
FIND-SET(b) 返回 a
FIND-SET(d) 返回 c

4. 基础实现（Naive Version）

4.1 MAKE-SET 实现

class Node {
    Node parent;
    int value;

    Node(int value) {
        this.value = value;
        this.parent = this;
    }
}

Node makeSet(int value) {
    return new Node(value);
}

4.2 FIND-SET 实现

Node findSet(Node node) {
    while (node != node.parent) {
        node = node.parent;
    }
    return node;
}

4.3 UNION 实现

void union(Node a, Node b) {
    Node rootA = findSet(a);
    Node rootB = findSet(b);

    if (rootA != rootB) {
        rootB.parent = rootA;
    }
}

⚠️ 注意：基础实现的 FIND 和 UNION 时间复杂度为 O(n)，效率较低。

5. 时间复杂度分析（Naive）

操作	时间复杂度
MAKE-SET	O(1)
FIND-SET	O(n)
UNION	O(n)

基础实现中，树可能退化为链表，导致 FIND-SET 操作效率低下。

6. 优化策略

6.1 路径压缩（Path Compression）

在 FIND-SET 过程中，将访问路径上的所有节点直接指向根节点，从而压缩树的高度。

Node findSet(Node node) {
    if (node != node.parent) {
        node.parent = findSet(node.parent);  // 递归压缩路径
    }
    return node;
}

✅ 效果：显著降低树的高度，后续 FIND 操作更快。

6.2 按秩合并（Union by Rank）

在合并两个集合时，总是将秩（树的大小或高度）较小的树合并到较大的树上，防止树过高。

class Node {
    Node parent;
    int value;
    int rank;  // 表示树的大小或高度

    Node(int value) {
        this.value = value;
        this.parent = this;
        this.rank = 1;
    }
}

Node union(Node a, Node b) {
    Node rootA = findSet(a);
    Node rootB = findSet(b);

    if (rootA == rootB) return rootA;

    // 按秩合并
    if (rootA.rank >= rootB.rank) {
        rootB.parent = rootA;
        rootA.rank += rootB.rank;
        return rootA;
    } else {
        rootA.parent = rootB;
        rootB.rank += rootA.rank;
        return rootB;
    }
}

✅ 效果：控制树的高度增长，提升 FIND 效率。

7. 优化后的复杂度分析

结合路径压缩和按秩合并后，DSU 的操作时间复杂度变为 **均摊 O(α(n))**，其中 α(n) 是阿克曼函数的反函数，增长极其缓慢。

操作	时间复杂度（均摊）
MAKE-SET	O(1)
FIND-SET	O(α(n))
UNION	O(α(n))

✅ 实际应用中，α(n) 可以视为常数，因此 DSU 是一种高效的并查集实现方式。

8. DSU 在图问题中的应用

8.1 图的连通分量（Connected Components）

使用 DSU 可以高效找出图中所有连通分量：

for (int v : G.V) {
    MAKE_SET(v);
}

for (Edge e : G.E) {
    if (FIND_SET(e.v1) != FIND_SET(e.v2)) {
        UNION(e.v1, e.v2);
    }
}

✅ 优势：支持动态添加边时维护连通性，优于 DFS/BFS。

8.2 Kruskal 算法中的 DSU 应用

Kruskal 算法用于求最小生成树（MST），其核心步骤是：

按权重排序所有边；
遍历每条边，若两个顶点不在同一集合，则加入 MST 并合并集合。

sort(G.E, by weight);

for (int v : G.V) {
    MAKE_SET(v);
}

List<Edge> MST = new ArrayList<>();

for (Edge e : G.E) {
    if (FIND_SET(e.v1) != FIND_SET(e.v2)) {
        MST.add(e);
        UNION(e.v1, e.v2);
    }
}

✅ 优势：DSU 的高效 FIND 和 UNION 操作显著提升了 Kruskal 算法的性能。

9. 总结

DSU 是一种高效的集合管理数据结构，特别适用于需要频繁合并和查询集合的问题场景。通过路径压缩和按秩合并两种优化策略，DSU 的操作时间复杂度接近常数级别，是图算法中不可或缺的工具。

✅ 关键点总结：

DSU 支持三种基本操作：MAKE-SET、FIND-SET、UNION；
使用树森林结构表示集合；
路径压缩 + 按秩合并是提升性能的核心；
广泛应用于图的连通分量、Kruskal 算法等场景；
时间复杂度接近 O(1)，适合大规模数据处理。

Persistence

REST

Security