归档157

661 字

3 分钟

并查集

2025-12-04

数据结构与算法

并查集#

并查集用来维护“若干个元素属于哪些集合”。

它最常见的两个操作是：

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

1、可以解决什么问题#

比如有 1 ~ 5 五个点，刚开始每个点都是单独集合：

1
{1} {2} {3} {4} {5}

执行：

1
合并 1 和 2
2
合并 2 和 3

之后集合变成：

1
{1, 2, 3} {4} {5}

这时查询 1 和 3 是否连通，答案就是是。

2、核心思想：用父节点表示集合#

并查集用数组 p 表示每个点的父节点。

如果：

1
p[x] == x

说明 x 是这个集合的根节点，也叫祖宗节点。

两个点是否在同一个集合，就看它们的祖宗节点是否一样。

3、查找祖宗节点#

基础写法：

1
int find(int x) {
2
    if (p[x] != x) return find(p[x]);
3
    return x;
4
}

但这样树可能很深，所以通常加路径压缩：

1
int find(int x) {
2
    if (p[x] != x) p[x] = find(p[x]);
3
    return p[x];
4
}

路径压缩会把查询路径上的点直接挂到根节点下面，后续查询更快。

4、合并两个集合#

合并 a 和 b 所在集合：

1
p[find(a)] = find(b);

意思是：让 a 的祖宗节点指向 b 的祖宗节点。

5、C++ 模板#

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

4
const int N = 100010;
5

6
int n, m;
7
int p[N];
8

9
int find(int x) {
10
    if (p[x] != x) p[x] = find(p[x]);
11
    return p[x];
12
}
13

14
int main() {
15
    cin >> n >> m;
16

17
    for (int i = 1; i <= n; i++) p[i] = i;
18

19
    while (m--) {
20
        char op;
21
        int a, b;
22
        cin >> op >> a >> b;
23

24
        if (op == 'M') {
25
            p[find(a)] = find(b);
26
        } else {
27
            if (find(a) == find(b)) cout << "Yes" << endl;
28
            else cout << "No" << endl;
29
        }
30
    }
31

32
    return 0;
33
}

6、带集合大小的并查集#

有些题会问某个集合里有多少个点，可以多维护一个 sz 数组。

1
int p[N], sz[N];
2

3
for (int i = 1; i <= n; i++) {
4
    p[i] = i;
5
    sz[i] = 1;
6
}
7

8
void merge(int a, int b) {
9
    int pa = find(a);
10
    int pb = find(b);
11

12
    if (pa != pb) {
13
        p[pa] = pb;
14
        sz[pb] += sz[pa];
15
    }
16
}

查询集合大小时：

1
sz[find(x)]

7、容易写错的地方#

（1）初始化不能漏#

1
for (int i = 1; i <= n; i++) p[i] = i;

刚开始每个点都是自己的祖宗。

（2）合并的是祖宗，不是普通节点#

错误写法：

1
p[a] = b;

正确写法：

1
p[find(a)] = find(b);

（3）查询也要用 `find`#

1
find(a) == find(b)

不能直接比较 p[a] 和 p[b]。

原图笔记#

总结#

并查集可以记住两个函数：

1
find：找祖宗
2
merge：合并集合

路径压缩是并查集高效的关键。只要所有查询和合并都通过 find，模板就比较稳定。

文章分享

如果这篇文章对你有帮助，欢迎分享给更多人！

并查集

https://blog.tjcheng.cn/posts/migrated/old-90/

作者

TengJinCheng

发布于

2025-12-04

许可协议

CC BY-NC-SA 4.0

线段树与懒标记

图的存储

音乐

音乐

并查集#

1、可以解决什么问题#

2、核心思想：用父节点表示集合#

3、查找祖宗节点#

4、合并两个集合#

5、C++ 模板#

6、带集合大小的并查集#

7、容易写错的地方#

（1）初始化不能漏#

（2）合并的是祖宗，不是普通节点#

（3）查询也要用 `find`#

原图笔记#

总结#

文章分享

音乐

文章目录

音乐

音乐

并查集

并查集#

1、可以解决什么问题#

2、核心思想：用父节点表示集合#

3、查找祖宗节点#

4、合并两个集合#

5、C++ 模板#

6、带集合大小的并查集#

7、容易写错的地方#

（1）初始化不能漏#

（2）合并的是祖宗，不是普通节点#

（3）查询也要用 find#

原图笔记#

总结#

文章分享

音乐

文章目录

（3）查询也要用 `find`#