算法——简单理解并查集

发表于

什么是并查集

​ 并查集是一种树形的数据结构，，用于处理一些不想交集合的合并即查询问题，我们可以通过并查集以接近O(1)的时间完成两个不相交集合的合并，并且以O(1)的时间判断一个元素属于哪个集合

理解并查集

​ 假设我们有[1, 2, 3, 4, 5]和[6, 7, 8, 9]两个集合，以并查集的思想，我们要以如下方式存储它

1
2
3
4
5
6
7
8
9
1    6
|    |
2    7
|    |
3    8
|    |
4    9
|
5

​ 这实际上是两个每个节点只包含一个子节点的树状结构，这样树的根节点即表示集合的名称，而树种所有的叶子节点都存在唯一的一个根节点，我们可以根据这个性质来判断某个元素是否属于一个集合

​ 那么我们如何实现两个集合的合并呢，如果是普通的使用数组存储的集合的话，我们一定需要将其中一个数组整个复制进另一个数组中，这需要很大的时间，并且我们还需要考虑数组的容量问题，如果使用并查集，我们只需要将一个集合的根节点接在另一个集合中，集合完成两个集合的合并，如下图

1
2
3
4
5
6
7
8
9
1————6
|    |
2    7
|    |
3    8
|    |
4    9
|
5

​ 这就是使用并查集存储不想交集合以及实现集合合并和查询元素是否属于某集合的方法

并查集的优化

​ 通过上述的过程，我们发现合并两个集合的操作十分简单，但是判断一个元素是否属于某个集合的过程显得十分复杂，我们需要从一个叶子节点一直回溯到根节点来判断它是否属于一个集合，针对这个问题有一种非常巧妙的优化方式——路径压缩

​ 我们发现，并查集实际上是一颗并不规则的树，它的结构不是固定的，每个节点原则上可以拥有无数个节点，所以如果我们将一个集合中的所有元素都直接和根节点连接，那么通过叶子节点找到根节点的回溯过程就会减少很多时间，如下图：

1
2
3
4
5
   2
   |
5——1——3
   |
   4

​ 这样我们找到一个节点的时间就近乎可以压缩到O(1)了

代码

​ 在代码中，我们使用find函数来实现找到元素所在的集合及路径压缩，我们使用p[x]来表示x属于哪个集合

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
#include <iostream>

using namespace std;

const int N = 100010;

int p[N];
int n, m;

// 返回集合名称并实现路径压缩
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) p[i] = i;
    while (m--) {
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        // 合并操作
        if(op[0] == 'M') p[find(a)] = find(b);
        // 查询操作
        else {
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}
-------------本文结束感谢您的阅读-------------