一文搞懂并查集

1 背景意义

首先要知道并查集可以解决什么问题呢？

• 并查集常用来解决 连通性 问题。
• 大白话就是当我们需要判断 两个元素 是否在 同一个集合 里的时候，我们就要想到用并查集。

并查集主要有两个功能：

• 将 两个元素 添加 到一个集合中；
• 判断 两个元素 在不在 同一个集合。

接下来围绕并查集的这两个功能来展开讲解。

2 原理讲解

从代码层面，我们如何将两个元素 添加 到同一个集合中呢？

举个栗子：

我们将三个元素 A，B，C （分别是数字）放在同一个集合，其实就是将三个元素连通在一起，如何连通呢。

• 只需要用一个 一维数组 来表示，即：father[A] = B，father[B] = C 这样就表述 A 与 B 与 C连通了（有向连通图）。
• A 连通 B，A 是 索引下标，根据 father[A] 的数值就知道 A 连通 B

⭐️ 添加元素代码如下：

// 将v，u 这条边加入并查集
void join(int u, int v) {
    u = find(u); // 寻找u的根
    v = find(v); // 寻找v的根
    if (u == v) return; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
    father[v] = u;
}
1
2
3
4
5
6
7

那么 判断 这三个元素是否在同一个集合里?

• 其实知道 A 连通 B 就已经足够了，也就是 寻根 思路，只要 A ，B，C 在同一个根下就是同一个集合；
  • 给出 A 元素，就可以通过 father[A] = B，father[B] = C，找到根为 C。
  • 给出 B 元素，就可以通过 father[B] = C，找到根也为为 C，说明 A 和 B 是在同一个集合里。

⭐️ find 函数代码如下：

// 并查集里寻根的过程
int find(int u) {
    if (u == father[u]) return u; // 如果根就是自己，直接返回
    else return find(father[u]); // 如果根不是自己，就根据数组下标一层一层向下找
}
1
2
3
4
5

如何表示 C 也在同一个元素里呢？

• 我们需要 father[C] = C，即 C 的根也为 C，这样就方便表示 A，B，C 都在同一个集合里了。

⭐️ father数组初始化代码如下：

// 并查集初始化
void init() {
    for (int i = 0; i < n; ++i) {
        father[i] = i;
    }
}
1
2
3
4
5
6

最后我们如何 判断 两个元素是否在同一个集合里？

• 如果通过 find函数 找到 两个元素属于同一个根 的话，那么这两个元素就是同一个集合，

⭐️ 判断 是否同根函数代码如下：

// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}
1
2
3
4
5
6

3 路径压缩

在实现 find 函数的过程中，我们知道，通过递归的方式，不断获取 father 数组下标对应的数值，最终找到这个集合的根。

• 如果这棵多叉树高度很深的话，每次 find 函数 去寻找跟的过程就要递归很多次；
• 所以可以将 非根节点 的 所有节点 直接指向 根节点；
• 在递归的过程中，让 father[u] 接住 递归函数 find(father[u]) 的 返回结果。

因为 find 函数向上寻找根节点，father[u] 表述 u 的父节点，那么让 father[u] 直接获取 find函数 返回的 根节点，这样就让节点 u 的父节点 变成根节点。

⭐️ 代码如下，注意看注释，路径压缩就一行代码：

// 并查集里寻根的过程
int find(int u) {
    if (u == father[u]) return u;
    else return father[u] = find(father[u]); // 路径压缩，如果没有找到父节点，会一直更新
}
1
2
3
4
5

以上代码在C++中，可以用三元表达式来精简一下，代码如下：

int find(int u) {
    return u == father[u] ? u : father[u] = find(father[u]);
}
1
2
3

4 代码模板

综上整理，模板如下

int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好
vector<int> father = vector<int> (n, 0); // C++里的一种数组结构

// 并查集初始化
void init() {
    for (int i = 0; i < n; ++i) {
        father[i] = i;
    }
}
// 并查集里寻根的过程
int find(int u) {
    return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩
}

// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}

// 将v->u 这条边加入并查集
void join(int u, int v) {
    u = find(u); // 寻找u的根
    v = find(v); // 寻找v的根
    if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
    father[v] = u;
}
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

通过模板，我们可以知道，并查集主要有 三个功能。

1. 寻找根节点，函数：find(int u)，也就是判断这个节点的祖先节点是哪个；
2. 将两个节点接入到同一个集合，函数：join(int u, int v)，将两个节点连在同一个根节点上；
3. 判断两个节点是否在同一个集合，函数：isSame(int u, int v)，就是判断两个节点是不是同一个根节点。

注：仅供学习参考，如有不足，欢迎指正！