DSU (并查集) 模板详解

1. 简介

并查集（Disjoint Set Union，简称 DSU）是一种用于处理不相交集合的合并与查询问题的数据结构。它支持以下两种操作：

1. 合并（Union）：将两个不同的集合合并为一个集合
2. 查询（Find）：查询某个元素属于哪个集合

并查集的主要特点是：

• 支持快速进行集合的合并和查询操作
• 时间复杂度接近 O(1)
• 空间复杂度 O(n)

2. 实现原理

2.1 基本结构

并查集使用树形结构来表示集合，每个集合都是一棵树。树中的每个节点都有一个父节点，根节点的父节点是自己。

2.2 核心操作

1. 初始化：每个元素初始时都是一个独立的集合，父节点指向自己
2. 查找：沿着父节点不断向上查找，直到找到根节点
3. 合并：将两个集合的根节点相连，使其中一个成为另一个的父节点
4. 路径压缩：在查找过程中，将路径上的所有节点直接连接到根节点，优化后续查询

3. 模板代码

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

struct DSU {
    std::vector<int> f, siz;
    
    DSU() {}
    DSU(int n) {
        init(n);
    }
    
    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);  // 初始化父节点数组
        siz.assign(n, 1);                   // 初始化集合大小数组
    }
    
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];  // 路径压缩
        }
        return x;
    }
    
    bool same(int x, int y) {   
        return find(x) == find(y);
    }
    
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;  // 已经在同一集合中
        }
        siz[x] += siz[y]; // 更新集合大小
        f[y] = x;         // 合并集合
        return true;
    }
    
    int size(int x) {
        return siz[find(x)];  // 返回所在集合的大小
    }
};

4. 函数说明

4.1 构造函数和初始化

1
2
3

DSU() {}
DSU(int n)
void init(int n)

• 支持默认构造和指定大小构造
• init 函数初始化 n 个元素的并查集
• 初始时每个元素构成一个单独的集合

4.2 查找函数

1

int find(int x)

• 查找元素 x 所属的集合（返回该集合的根节点）
• 使用路径压缩优化，将查找路径上的所有节点直接连接到根节点

4.3 判断同集合

1

bool same(int x, int y)

• 判断两个元素是否属于同一个集合
• 通过比较它们的根节点是否相同来判断

4.4 合并集合

1

bool merge(int x, int y)

• 将包含元素 x 和 y 的两个集合合并
• 如果两个元素已经在同一集合中，返回 false
• 合并时会更新集合的大小信息

4.5 获取集合大小

1

int size(int x)

• 返回包含元素 x 的集合的大小

5. 时间复杂度分析

• 初始化：O(n)
• 查找：均摊 O(α(n))，其中 α(n) 是阿克曼函数的反函数，实际上可以认为接近 O(1)
• 合并：O(α(n))
• 判断同集合：O(α(n))
• 获取集合大小：O(α(n))

6. 应用场景

1. 处理无向图的连通性问题
2. 最小生成树算法（Kruskal 算法）
3. 判断图中是否存在环
4. 维护动态连通性
5. 集合的合并与查询操作

7. 注意事项

1. 初始化时需要确保节点编号在 [0, n-1] 范围内
2. 合并操作前最好先判断是否在同一集合
3. 路径压缩对于提高查询效率非常重要
4. 需要维护集合大小时，合并操作要更新 siz 数组

8. 总结

并查集是一种简单而强大的数据结构，它在处理一些动态连通性问题时非常高效。通过路径压缩等优化，可以使其操作的时间复杂度接近常数级别。掌握并查集的实现和应用对于解决图论相关问题非常有帮助。