我的算法书 - 并查集

一句话算法

并查集把同一类元素挂到同一个代表元下面，用 find 找代表，用 unite 合并集合。

问题模型

并查集适合动态维护等价关系。

常见操作是：

合并两个元素所在集合；
查询两个元素是否在同一个集合。

例如给定 $n$ 个点和若干条无向边，边不断加入，在线询问两个点是否连通。

核心直觉

每个集合选一个代表元，也就是根节点。

元素 x -> 父亲 -> 父亲 -> 根

find(x) 沿着父亲指针找到根。两个元素根相同，就在同一个集合。

为了让树不变高，有两个常用优化：

路径压缩：find 之后，把路径上的点直接挂到根上；
按大小合并：小集合挂到大集合下面。

状态设计

维护两个数组：

fa[x]：x 的父亲；
sz[x]：当 x 是根时，表示集合大小。

初始化时：

fa[x]=x,\quad sz[x]=1

表示每个元素单独成集。

算法步骤

查询代表元 `find(x)`

如果 fa[x] == x，说明 x 是根，返回 x。
否则递归查找 fa[x] 的根。
回溯时把 x 直接挂到根上。

合并集合 `unite(x, y)`

分别找到 x 和 y 的根。
如果根相同，不需要合并。
否则把小集合的根挂到大集合的根下面。
更新集合大小。

算法证明

核心不变量：同一个集合中的所有元素最终指向同一个根；不同集合的根不同。

初始化正确

每个元素的父亲是自己，所以每个元素单独成集，根互不相同。
find 正确

find 沿父亲指针走到根。路径压缩只把路径上的点改为直接指向根，没有改变它们所在集合。
unite 正确

合并两个集合时，只把一个根挂到另一个根下面。这样两个集合的所有元素会通过父亲指针到达同一个根。
查询正确

两个元素在同一集合，当且仅当它们的根相同。

因此并查集能正确维护动态连通性。

复杂度分析

使用路径压缩和按大小合并后，单次操作的均摊复杂度为：

O(\alpha(n))

其中 $\alpha(n)$ 是反阿克曼函数，在竞赛数据范围内可以近似看成常数。

空间复杂度为 $O(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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

        #include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> fa, sz;

    DSU(int n = 0) {
        init(n);
    }

    void init(int n) {
        fa.resize(n + 1);
        sz.assign(n + 1, 1);
        iota(fa.begin(), fa.end(), 0);
    }

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

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    bool unite(int x, int y) {
        int fx = find(x);
        int fy = find(y);
        if (fx == fy) return false;

        if (sz[fx] < sz[fy]) swap(fx, fy);
        fa[fy] = fx;
        sz[fx] += sz[fy];
        return true;
    }
};

int main() {
    int n, m;
    cin >> n >> m;

    DSU dsu(n);
    while (m--) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) {
            dsu.unite(x, y);
        } else if (op == 2) {
            cout << (dsu.same(x, y) ? "Y" : "N") << "\n";
        }
    }

    return 0;
}

种类并查集：

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
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

        #include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> fa, sz;

    DSU(int n = 0) {
        init(n);
    }

    void init(int n) {
        fa.resize(n + 1);
        sz.assign(n + 1, 1);
        iota(fa.begin(), fa.end(), 0);
    }

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

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    void unite(int x, int y) {
        int fx = find(x);
        int fy = find(y);
        if (fx == fy) return;

        if (sz[fx] < sz[fy]) swap(fx, fy);
        fa[fy] = fx;
        sz[fx] += sz[fy];
    }
};

int main() {
    int n, m;
    cin >> n >> m;

    DSU dsu(2 * n);
    auto enemy = [n](int x) {
        return x + n;
    };

    bool ok = true;
    while (m--) {
        int x, y;
        cin >> x >> y;

        // x 与 y 必须在不同类别中。
        if (dsu.same(x, y)) {
            ok = false;
        }
        dsu.unite(x, enemy(y));
        dsu.unite(enemy(x), y);
    }

    cout << (ok ? "YES" : "NO") << "\n";
    return 0;
}

测试用例

普通并查集输入：

输出：

N
Y
N

种类并查集输入：

输出：

NO

解释：三条“不同类”关系形成奇环，无法二分。

应用分类详解

并查集的本质是维护具有传递性的关系。只要题目中关系满足“如果 $a$ 和 $b$ 同类， $b$ 和 $c$ 同类，那么 $a$ 和 $c$ 同类”，就可以考虑并查集。

一、动态连通性

典型模式： 无向边不断加入，询问两个点是否连通。

识别信号： 出现“合并集合”“查询是否在同一集合”“朋友关系传递”。

核心建模： 每个连通块是一个集合，加入边就是合并两个集合。

应用场景	经典题目	核心思路
并查集模板	luogu-P3367	合并集合，查询同属
亲戚关系	luogu-P1551	亲戚关系具有传递性

二、最小生成树

典型模式： 按边权从小到大选边，判断加入边是否成环。

识别信号： 出现“无向连通图”“最小生成树”“Kruskal”。

核心建模： 如果一条边两端已经在同一集合，加入它会成环；否则合并两个连通块。

应用场景	经典题目	核心思路
Kruskal	luogu-P3366	并查集维护当前森林连通块
最小生成树	图论 MST 专题	选边时快速判环

三、二元对立关系

典型模式： 每条关系表示两个元素必须属于不同类别。

识别信号： 出现“敌人”“性别不同”“不能同组”“判断是否二分图”。

核心建模： 为每个元素建立一个反集 x+n。若 x 与 y 不同类，则合并 x 和 enemy(y)，合并 enemy(x) 和 y。

应用场景	经典题目	核心思路
种类并查集	本文专题页	用反集维护二元对立
关押罪犯	luogu-P1525	敌对关系按权值处理

四、离线区间与网格连通

典型模式： 删除操作不好维护，但反过来变成添加操作。

识别信号： 出现“删边”“倒序处理”“询问连通块数量”。

核心建模： 把操作离线倒过来，删除变添加，用并查集合并连通块。

应用场景	经典题目	核心思路
离线删边连通性	常见动态图题	倒序加边
岛屿数量动态版	LeetCode 305	加陆地时合并相邻陆地

经典例题

1. luogu-P3367

并查集模板题。直接练习 unite 和 same。

2. luogu-P3366

最小生成树。Kruskal 算法中用并查集判断两端点是否已经连通。

3. luogu-P1525

二元对立关系。可以用种类并查集判断冲突，也可以二分答案后检查二分图。

参考

本文旧版解析保留的核心思路：并查集擅长维护无向图连通性，以及具有传递性的关系。