数据结构 -并查集
博客主页：【夜泉_ly】
本文专栏：【数据结构】
欢迎点赞👍收藏⭐关注❤️
文章目录
- 一、作用
- 二、结构
- 三、实现
- 四、处理非数字类型的元素
- 五、路径压缩
今天来简单聊聊并查集。
先贴代码：
#pragma once
#include <vector>
#include <iostream>
#include <unordered_map>
template<class T>
class UnionFindSet
{
private:
int FindRoot(int cur) const
{
if (_ufs[cur] < 0) return cur;
return _ufs[cur] = FindRoot(_ufs[cur]);
}
int GetIndex(const T& target) const
{
return _index[target];
}
public:
UnionFindSet(const std::vector<T>& input)
: _ufs(input.size(), -1)
{
for (int i = 0; i < input.size(); i++)
{
_index[input[i]] = i;
}
}
int Find(const T& e) const
{
return FindRoot(GetIndex(e));
}
void Union(const T& e1, const T& e2)
{
int p1 = Find(e1), p2 = Find(e2);
if (p1 != p2)
{
if (_ufs[p1] > _ufs[p2]) std::swap(p1, p2);
_ufs[p1] += _ufs[p2];
_ufs[p2] = p1;
}
}
bool IsSameSet(const T& e1, const T& e2) const
{
return Find(e1) == Find(e2);
}
int GetSetSize(const T& e) const
{
return -_ufs[Find(e)];
}
private:
std::vector<int> _ufs;
std::unordered_map<T, int> _index;
};
// 注：请不要尝试查找一个不存在的元素
一、作用
首先，我们需要知道并查集的作用：
- 快速合并两个集合。
- 快速查找一个元素所在的集合。
Q：它是如何做到的呢？
A：森林。
二、结构
来看看结构吧：
- 逻辑结构：森林（由多棵树组成的结构）。
- 物理结构：数组（用于记录树节点之间的关系）。
把结构对应到功能，是不是有点感觉了？
-
快速合并：
本质上就是将两棵树的根节点连在一起。 -
快速查找：
本质上就是找到当前节点所在树的根节点。
而“快速”的关键，
就是数组与下标。
具体来说，
并查集使用的是双亲表示法：
（一直觉得这个称呼挺怪的，
明明只存了一个值，还叫双亲）
对于数组中每个位置存储的值，
- 如果值大于等于 0，
表示存储的是父节点的下标。 - 如果值小于 0，
说明这是树的根节点，
并且 |它的值| 表示这棵树包含的节点个数。
三、实现
假如我们有 (n) 个元素，
它们的编号是从 (0) 到 (n - 1)。
初始时，每个元素都属于一个独立的集合。
我们需要实现以下三种操作：
- 合并两个数所在的集合。
- 查询两个数是否在同一个集合中。
- 查询某个数所在集合的大小。
首先，
创建一个大小为 (n) 的数组 _ufs ，
初始值全部设为 -1。
初始化的 -1 有两层含义：
- 这个节点是树的“根节点”；
- 它所属的集合当前只有 1 个元素。
vector<int> _ufs(n, -1); // 初始化数组
然后，
编写一个核心方法：“找祖先”方法。
这个方法的作用是找到某个节点所在集合的根节点：
function<int(int)> Find = [&](int cur)
{
if (_ufs[cur] >= 0)
{
return Find(_ufs[cur]); // 递归寻找父节点
}
return cur; // 找到根节点
};
-
如果
_ufs[cur] >= 0，
说明当前节点cur不是根节点，
而_ufs[cur]存储的是它父节点的下标，
所以递归处理_ufs[cur]。 -
如果
_ufs[cur] < 0，
说明已经到达根节点，
直接返回。
接着，
我们实现三种操作：
-
合并两数所在的集合：
首先找到两个数的祖先（根节点）。
然后合并。int p1 = Find(num1), p2 = Find(num2); if (p1 != p2) { if (_ufs[p1] > _ufs[p2]) std::swap(p1, p2); _ufs[p1] += _ufs[p2]; _ufs[p2] = p1; }比如，如果我要合并红的和绿的：
那么[红的根] += [绿的根]，即更新集合的元素数量，
[绿的根] = 红的根，即合并集合：
这里需要注意的是swap，
我们得将小的树合并到大的树，
不然可能会出现路径较长的现象。额，比如说：
-1 -1 -1 -1 -1
然后我倒着合并，且没有swap，
就会变成这样：
-5 0 1 2 3想象一下？
如果路径太长，Find又用的递归。。。 -
查询两数是否在同一个集合中：
检查两数的根节点是否相同即可：
if (Find(num1) == Find(num2)) cout << "Yes" << endl; else cout << "No" << endl; -
查询某数所在集合的元素个数：
找到该数所在集合的根节点，
根节点的值即为集合大小（注意是负数的绝对值）：cout << -_ufs[Find(num)] << endl; // 注意取负
四、处理非数字类型的元素
如果元素不是数字，
简单，用unordered_map映射就行。
例如，假设元素类型为 T。
首先，
创建一个映射关系 _index，
将元素映射到数组下标：
unordered_map<T, int> _index;
void Init(const vector<T>& input)
{
for (int i = 0; i < input.size(); i++)
{
_index[input[i]] = i;
}
}
然后，
编写一个函数，
用于根据元素找到其对应的下标：
int FindIndex(const T& t)
{
return _index[t];
}
五、路径压缩
名字很高级，写法很简单，
改改find就行：
function<int(int)> Find = [&](int cur)
{
if(ufs[cur] < 0) return cur;
return ufs[cur] = Find(ufs[cur]);
};
作用就是让路径上的所有点，都指向祖先。
希望本篇文章对你有所帮助！并激发你进一步探索编程的兴趣！
本人仅是个C语言初学者，如果你有任何疑问或建议，欢迎随时留言讨论！让我们一起学习，共同进步！