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;
}
那么 判断 这三个元素是否在同一个集合里?
- 其实知道
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]); // 如果根不是自己，就根据数组下标一层一层向下找
}
如何表示 C 也在同一个元素里呢？
- 我们需要
father[C] = C，即C的根也为C，这样就方便表示A，B，C都在同一个集合里了。
⭐️ father数组初始化代码如下：
// 并查集初始化
void init() {
for (int i = 0; i < n; ++i) {
father[i] = i;
}
}
最后我们如何 判断 两个元素是否在同一个集合里？
- 如果通过 find函数 找到 两个元素属于同一个根 的话，那么这两个元素就是同一个集合，
⭐️ 判断 是否同根函数代码如下：
// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {
u = find(u);
v = find(v);
return u == v;
}
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]); // 路径压缩，如果没有找到父节点，会一直更新
}
以上代码在C++中，可以用三元表达式来精简一下，代码如下：
int find(int u) {
return u == father[u] ? u : father[u] = find(father[u]);
}
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;
}
通过模板，我们可以知道，并查集主要有 三个功能。
- 寻找根节点，函数：
find(int u)，也就是判断这个节点的祖先节点是哪个； - 将两个节点接入到同一个集合，函数：
join(int u, int v)，将两个节点连在同一个根节点上； - 判断两个节点是否在同一个集合，函数：
isSame(int u, int v)，就是判断两个节点是不是同一个根节点。
注：仅供学习参考，如有不足，欢迎指正！
