我的算法书 - 并查集

一句话算法

并查集把同一类元素挂到同一个代表元下面，用 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)$ 。

代码实现

普通并查集：

C++

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 {
    using T = int;

    vector<T> fa;  // fa[x] 为 x 的父节点
    vector<T> sz;  // sz[x] 为集合大小（仅根节点有效）

    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);
    }

    // 查询 x 所在集合的根（路径压缩）
    int find(int x) {
        if (fa[x] == x) return x;
        return fa[x] = find(fa[x]);
    }

    // x 与 y 是否在同一集合
    bool same(int x, int y) {
        return find(x) == find(y);
    }

    // 合并 x 与 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;
}

C++ 竞赛版

不用 struct 的精简写法：全局数组加三个函数，适合比赛现场手写。

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

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

// 并查集竞赛精简版（不用 struct）：路径压缩 + 按大小合并
// 输入 n m，接下来 m 行操作：1 x y 合并，2 x y 输出是否同集合（Y/N）
// 口诀：find 找根压到底，unite 小树挂大树
// 易错点：init 别只写 fa[i] = i，sz[i] 也要置 1；合并后 sz 只在新根上有效
// 和别的模板一起用时 maxn 只留一份

const int maxn = 1e6 + 5;
int fa[maxn], sz[maxn];  // sz[x] 仅在根上有效

void init(int n) {
    for (int i = 1; i <= n; i++) fa[i] = i, sz[i] = 1;
}

// 查 x 的根，顺手把整条链压到根上
int find(int x) {
    return fa[x] == x ? x : 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), 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() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    init(n);
    while (m--) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) unite(x, y);
        else cout << (same(x, y) ? "Y" : "N") << "\n";
    }
    return 0;
}

Python

python

        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

        # 并查集：合并两个集合，查询两个元素是否在同一集合。
# 下标约定：元素编号 1..n（fa/sz 都开 n+1，下标 0 不用）。
# 调用示例：d = DSU(5); d.unite(1, 3); d.same(1, 3) -> True
# find 路径压缩 + unite 按大小合并，树高 O(log n)，递归深度安全。


class DSU:
    """并查集 (Disjoint Set Union)"""

    def __init__(self, n: int):
        # 1-indexed, fa 初始指向自己，sz 初始为 1
        self.fa = list(range(n + 1))
        self.sz = [1] * (n + 1)

    def find(self, x: int) -> int:
        """查找根节点，并进行路径压缩"""
        if self.fa[x] != x:
            self.fa[x] = self.find(self.fa[x])
        return self.fa[x]

    def same(self, x: int, y: int) -> bool:
        """判断 x 和 y 是否属于同一个集合"""
        return self.find(x) == self.find(y)

    def unite(self, x: int, y: int) -> bool:
        """按大小合并两个集合 (小树挂大树)"""
        fx, fy = self.find(x), self.find(y)
        if fx == fy:
            return False

        # 确保 fx 始终是较大的树
        if self.sz[fx] < self.sz[fy]:
            fx, fy = fy, fx

        self.fa[fy] = fx
        self.sz[fx] += self.sz[fy]
        return True

Python set 版

不用并查集的替代写法：set 小并大（启发式合并），判同 $O(1)$ 、合并总计 $O(n \log n)$ ，还能直接枚举集合成员。只适合"合并 + 判同"；维护元素间关系（带权/种类并查集）或要撤销时不行。

python

        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

        # 并查集的 set 替代写法：小并大（启发式合并），只适合"合并 + 判同"。
# 下标约定：元素编号 1..n。
# 用法：init(n); unite(1, 3); same(1, 3) -> True; members(1) 直接拿到集合内所有元素
# 复杂度：判同 O(1)；合并 O(小集合大小)，每个元素最多被搬 log n 次，总 O(n log n)。
# 边界：维护元素间关系（带权/种类并查集）或要高效撤销时不能用，老实写并查集。
# 易错点：必须小并大，不比大小直接 s1 |= s2 最坏退化 O(n^2)。

bel: dict[int, set[int]] = {}  # 元素 -> 所在集合对象


def init(n: int) -> None:
    """每个元素各自成集合。"""
    global bel
    bel = {i: {i} for i in range(1, n + 1)}


def same(x: int, y: int) -> bool:
    """x 与 y 是否同一集合：比较集合对象即可，O(1)。"""
    return bel[x] is bel[y]


def unite(x: int, y: int) -> bool:
    """小集合的元素逐个搬进大集合，返回是否真的发生了合并。"""
    s1, s2 = bel[x], bel[y]
    if s1 is s2:
        return False
    if len(s1) < len(s2):
        s1, s2 = s2, s1
    for v in s2:
        bel[v] = s1
    s1 |= s2
    return True


def members(x: int) -> set[int]:
    """x 所在集合的所有元素；len(bel[x]) 就是集合大小——set 写法的加分项。"""
    return bel[x]

种类并查集：

C++

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
62
63
64
65
66
67
68
69

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

// 并查集判二分图：把每个点拆成"本体"和"对立面"，矛盾即非二分图
struct DSU {
    using T = int;

    vector<T> fa;  // fa[x] 为 x 的父节点
    vector<T> sz;  // sz[x] 为集合大小（仅根节点有效）

    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);
    }

    // 查询 x 所在集合的根（路径压缩）
    int find(int x) {
        if (fa[x] == x) return x;
        return fa[x] = find(fa[x]);
    }

    // x 与 y 是否在同一集合
    bool same(int x, int y) {
        return find(x) == find(y);
    }

    // 合并 x 与 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;

    // 拆点：i 表示点 i，i+n 表示"点 i 的对立面"
    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;
}

C++ 竞赛版

不用 struct 的精简写法：拆点后 x + n 就是 x 的对立面，适合比赛现场手写。

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

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

// 种类并查集（并查集判二分图）竞赛精简版：每个点拆成 x 与 x+n（对立面）
// 输入 n m 与 m 条边 x y（x 与 y 必须不同类），输出 YES/NO
// 口诀：要求不同类，就把 x 挂到 y 的对立面、y 挂到 x 的对立面
// 易错点：拆点后容量翻倍，init 要开到 2n；x 与 y 同集合才是矛盾，合并本身不会矛盾
// 和别的模板一起用时 maxn 只留一份

const int maxn = 1e6 + 5;
int fa[maxn * 2], sz[maxn * 2];  // 拆点后下标 1..2n

void init(int n) {
    for (int i = 1; i <= n; i++) fa[i] = i, sz[i] = 1;
}

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

// 小树挂大树
void unite(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return;
    if (sz[fx] < sz[fy]) swap(fx, fy);
    fa[fy] = fx;
    sz[fx] += sz[fy];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    init(2 * n);  // 拆点：i 是点 i，i+n 是它的对立面
    bool ok = true;
    while (m--) {
        int x, y;
        cin >> x >> y;
        if (find(x) == find(y)) ok = false;  // 同类却要求不同类：矛盾
        unite(x, y + n);  // x 和 y 的对立面同类
        unite(x + n, y);  // x 的对立面和 y 同类
    }
    cout << (ok ? "YES" : "NO") << "\n";
    return 0;
}

Python

Python 版抽成 DSU 类（init 即构造），单文件即可复制使用。

python

        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

        # 种类并查集（判二分图）：把每个点 x 拆成"本体 x"与"对立面 x+n"。
# 下标约定：点编号 1..n，并查集规模 2n；"x 与 y 异类" 转成合并 (x, y+n) 与 (x+n, y)。
# is_bipartite 对应 C++ main 的判定逻辑；DSU 与 dsu.py 一致，单文件即可复制使用。


class DSU:
    """并查集 (Disjoint Set Union)"""

    def __init__(self, n: int):
        # 1-indexed, fa 初始指向自己，sz 初始为 1
        self.fa = list(range(n + 1))
        self.sz = [1] * (n + 1)

    def find(self, x: int) -> int:
        """查找根节点，并进行路径压缩"""
        if self.fa[x] != x:
            self.fa[x] = self.find(self.fa[x])
        return self.fa[x]

    def same(self, x: int, y: int) -> bool:
        """判断 x 和 y 是否属于同一个集合"""
        return self.find(x) == self.find(y)

    def unite(self, x: int, y: int) -> bool:
        """按大小合并两个集合 (小树挂大树)"""
        fx, fy = self.find(x), self.find(y)
        if fx == fy:
            return False

        # 确保 fx 始终是较大的树
        if self.sz[fx] < self.sz[fy]:
            fx, fy = fy, fx

        self.fa[fy] = fx
        self.sz[fx] += self.sz[fy]
        return True


def is_bipartite(n: int, edges: list[tuple[int, int]]) -> bool:
    """n 个点、给定"必须异类"边集能否二染色；x 与 y 已同类即矛盾。

    点编号 1..n。调用示例：is_bipartite(3, [(1, 2), (2, 3), (1, 3)]) -> False
    """
    dsu = DSU(2 * n)  # 拆点：i 是点 i，i+n 是它的对立面
    for x, y in edges:
        if dsu.same(x, y):
            return False  # 已有约束要求同类，新约束要求异类，矛盾
        dsu.unite(x, y + n)  # x 和 y 的对立面同类
        dsu.unite(x + n, y)  # x 的对立面和 y 同类
    return True

测试用例

普通并查集输入：

输出：

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

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

参考

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

一句话算法

问题模型

核心直觉

状态设计

算法步骤

查询代表元 find(x)

合并集合 unite(x, y)

算法证明

复杂度分析

代码实现

测试用例

应用分类详解

一、动态连通性

二、最小生成树

三、二元对立关系

四、离线区间与网格连通

经典例题

1. luogu-P3367

2. luogu-P3366

3. luogu-P1525

参考

查询代表元 `find(x)`

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