并查集 (DSU)

笔记

并查集 (DSU)

2026/2/11

简介

并查集（Disjoint Set Union, DSU）主要用于维护若干个不相交集合，支持以下两类操作：

查询（find）：查询某个元素所属集合（以根节点为代表）．
合并（merge）：合并两个元素所属集合．

并查集把每个集合表示成一棵树，对于每个节点 x 记录其父节点 fa[x] ，特别地，对于根节点 fa[x] = x ．

实现

查询

朴素实现

cpp

1
2
3
4


int find(int x) {
    while (x != fa[x]) x = fa[x];
    return x;
}

路径压缩

把沿途经过的每个节点都连到根节点上．

cpp

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


// 递归写法
int find(int x) {
    if (x == fa[x]) return x;
    return fa[x] = find(fa[x]);
}

// 非递归写法
int find(int x) {
    int root = x;
    while (root != fa[root]) {
        root = fa[root];
    }
    while (x != root) {
        int p = fa[x];
        fa[x] = root;
        x = p;
    }
    return x;
}

不使用按大小/秩合并时，路径压缩递归写法遇到长链树时有爆栈风险．

路径减半

把自己连到祖父节点，然后跳到祖父节点．

cpp

1
2
3
4
5
6


int find(int x) {
    while (x != fa[x]) {
        x = fa[x] = fa[fa[x]];
    }
    return x;
}

路径分裂

把自己连到祖父节点，然后跳到父节点．

cpp

1
2
3
4
5
6
7
8


int find(int x) {
    while (x != fa[x]) {
        int p = fa[x];
        fa[x] = fa[p];
        x = p;
    }
    return x;
}

合并

朴素实现

cpp

1
2
3
4


void merge(int x, int y) {
    x = find(x), y = find(y);
    if (x != y) fa[y] = x;
}

按大小合并

小树挂在大树上．

cpp

1
2
3
4
5
6
7
8


// sz[x] 初始值为 1
void merge(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return;
    if (sz[x] < sz[y]) swap(x, y);
    fa[y] = x;
    sz[x] += sz[y];
}

按秩合并

浅树挂在深树上．

不使用路径压缩/减半/分裂时，秩就是树高；
使用路径压缩/减半/分裂后，秩不再严格等于树高，但仍可以作为合并依据．

cpp

1
2
3
4
5
6
7
8


// rk[x] 初始值为 0
void merge(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return;
    if (rk[x] < rk[y]) swap(x, y);
    fa[y] = x;
    if (rk[x] == rk[y]) rk[x]++;
}

时间复杂度

设有 $n$ 个元素， $m$ 次操作．

实现方式	单次 `find/merge`	总复杂度
无优化	$O(n)$	$O(mn)$
仅按大小/秩合并	$O(\log n)$	$O(m\log n)$
仅路径压缩/减半/分裂	最坏 $O(n)$ ，均摊 $O(\log n)$	$O(m\log n)$
路径压缩/减半/分裂 + 按大小/秩合并	最坏 $O(\log n)$ ，均摊 $O(\alpha(n))$	$O(m\alpha(n))$

其中 $\alpha(n)$ 是反阿克曼函数，增长极其缓慢，在实际应用中可视为常数．

模板

cpp

 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


struct DSU {
    vector<int> fa, sz;
    int sets;  // 连通块个数
    DSU(int n){
        init(n);
    }
    void init(int n) {
        fa.resize(n + 1);
        sz.assign(n + 1, 1);
        sets = n;
        iota(fa.begin(), fa.end(), 0);
    }
    int find(int x) {
        while (x != fa[x]) {
            x = fa[x] = fa[fa[x]];  // 路径减半
        }
        return x;
    }
    bool merge(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return false;
        if (sz[x] < sz[y]) swap(x, y);  // 按规模合并
        fa[y] = x;
        sz[x] += sz[y];
        sets--;  // 若成功合并则连通块个数减一
        return true;
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    int size(int x) {
        return sz[find(x)];
    }
};

模意义下最大子段和