并查集 - Blume's Skylog

归档38

数据结构与算法11 云原生与运维8 后端开发8 编程语言7 前端开发4

214 字

1 分钟

并查集

2024-08-25

并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。

顾名思义，并查集支持两种操作：

合并（Union）：合并两个元素所属集合（合并对应的树）
查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合

并查集在经过修改后可以支持单个元素的删除、移动；使用动态开点线段树还可以实现可持久化并查集。

1
struct dsu {
2
    std::vector<int> pa;
3

4
    explicit dsu(int size) : pa(size) {
5
        std::iota(pa.begin(), pa.end(), 0);
6
    }
7

8
    int find(int x) {
9
        return pa[x] == x ? x : (pa[x] = find(pa[x]));
10
    }
11

12
    void unite(int x, int y) {
13
        pa[find(x)] = find(y);
14
    }
15
};