理解使用并查集
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
目录
前言理解并查集是为了接下来学习图要用而会使用并查集则可以在做某些OJ题目时更加简单。
一.并查集原理
1.概念
在一些问题中需要将n个不同的元素划分成一些不相交的集合。开始时每个元素自成一个单元素集合然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于哪个集合的运算。适合于描述这类问题的抽象数据类型称为并查集。
2.性质
① 数组的下标对应集合中元素的编号
② 数组中如果为负数其中的负号代表它是根数字代表该集合中元素个数
③ 数组中如果为非负数代表该元素父亲在数组中的下标
3.形式
4. 合并方式
如果两个集合中的元素发生合并那么怎么办呢
解决方法
① 查找元素属于哪个集合
沿着数组表示的树形关系往上一直找到根根树中元素为负数的位置
② 查看两个元素是否属于同一个集合
沿着数组表示的树形关系往上一直找到树的根如果根相同说明在同一个集合否则不再同一个集合。
③ 将两个集合归并成一个集合
先将两个集合中的元素合并再将一个集合名称改为另一个集合的名称。
合并的方式就是将其中一个根的数字加到另一个根的数字上然后再将这个根中的数组变成新的根元素的位置。
将0和1的集合合并变成如图所示。
上面的解决方法就是并查集可以解决的问题除了上面3个还有第4个
④ 查看集合的个数
遍历数组数组中元素为负数的个数即为集合的个数。
二.并查集实现
1.成员变量
该成员就为一个vector容器。
private:
std::vector<int> _ufs;2.构造函数
根据想要构造的vector的数量来开辟足够的空间并全部初始化为-1。
UnionFindSet(size_t n)
: _ufs(n, -1)
{}3.查找根
遍历数组找到的第一个为负数的元素就是其中一个集合的根。这里为了优化我们可以进行路径压缩遍历数组找到大于0的元素就先保存它的父节点然后再将该元素直接给root相当于连上了root父亲变为root即将该元素的数字变为root的位置最后再继续往上让他的父节点直接连到root。
size_t FindRoot(int x)
{
int root = x;
while (_ufs[root] >= 0)
{
root = _ufs[root];
}
// 路径压缩
while (_ufs[x] >= 0)
{
int parent = _ufs[x];
_ufs[x] = root;
x = parent;
}
return root;
}4.合并集合
先保存两个集合的根如果这两个根是相同的就说明这两个元素本身就是一个集合的就不需要去合并了。然后为了优化我们让数据量小的往大的合并。因为我们默认root1的集合是数据量大的那个如果实际上root2的数据量更大那么就交换root1和root2。
void Union(int x1, int x2)
{
int root1 = FindRoot(x1);
int root2 = FindRoot(x2);
// 如果本身就在一个集合就没必要合并了
if (root1 == root2)
{
return;
}
// 控制数据量小的往大的集合合并
if (abs(_ufs[root1]) < abs(_ufs[root2]))
{
swap(root1, root2);
}
_ufs[root1] += _ufs[root2];
_ufs[root2] = root1;
}5.判断是否在一个集合
之间通过调用FindRoot函数看根是否相同相同就是在一个集合。
bool InSet(int x1, int x2)
{
return FindRoot(x1) == FindRoot(x2);
}6.查看集合数量
遍历数组有多少个负数就有多少个集合。
size_t SetSize()
{
size_t size = 0;
for (size_t i = 0; i < _ufs.size(); ++i)
{
if (_ufs[i] < 0)
{
++size;
}
}
return size;
}三.并查集总代码
#pragma once
#include <vector>
class UnionFindSet
{
public:
UnionFindSet(size_t n)
: _ufs(n, -1)
{}
size_t FindRoot(int x)
{
int root = x;
while (_ufs[root] >= 0)
{
root = _ufs[root];
}
// 路径压缩
while (_ufs[x] >= 0)
{
int parent = _ufs[x];
_ufs[x] = root;
x = parent;
}
return root;
}
void Union(int x1, int x2)
{
int root1 = FindRoot(x1);
int root2 = FindRoot(x2);
// 如果本身就在一个集合就没必要合并了
if (root1 == root2)
{
return;
}
// 控制数据量小的往大的集合合并
if (abs(_ufs[root1]) < abs(_ufs[root2]))
{
swap(root1, root2);
}
_ufs[root1] += _ufs[root2];
_ufs[root2] = root1;
}
bool InSet(int x1, int x2)
{
return FindRoot(x1) == FindRoot(x2);
}
size_t SetSize()
{
size_t size = 0;
for (size_t i = 0; i < _ufs.size(); ++i)
{
if (_ufs[i] < 0)
{
++size;
}
}
return size;
}
private:
std::vector<int> _ufs;
};