数据结构之并查集
- 并查集是一种树型的数据结构
- 是一种森林，森林中的每棵树表示一个集合，树中的结点对应一个元素
并查集的原理
现在有10个人（从0开始编号），刚开始这10个人互不认识，所以各自属于一个集合。
并查集会用一个数组来表示这10个人之间的关系，数组的下标对应就是这10个人的编号，刚开始时数组中的元素都初始化为-1。
数组中的值为负数，即该位置是一颗树的根，且负数的绝对值表示的这棵树（集合）中数据的个数
经过一段时间的相处最终形成了三个朋友圈
并查集数组中各个位置的值更新
4号和8号认识了，他们所在的两个集合就需要进行合并，最终变成了两个集合
合并时，先分别找到这两个元素所在集合的根结点，再将一个集合合并到另一个集合，最后更新数组中根结点的值
并查集的实现
从上面的分析中，我们可以看出并查集的本质是一个数组，我们对数组内元素不断进行调整，所以我们这样定义并查集
class UnionFind
{
public:
// 刚开始每个人都是独立的，所以刚开始时数组中的元素都初始化为-1
UnionFind(size_t size)
:_ufs(size, -1)
{}
private:
vector<int> _ufs;
};
找根的函数
bool findRoot(int x)
{
int parent = x;
while (parent >= 0)
parent = _ufs[parent];
//路径压缩.提高下次查找效率
while (_ufs[x] >= 0)
{
int tmp = _ufs[x];
_ufs[x] = parent;
x = tmp;
}
return parent;
}
并查集完整代码
#include<iostream>
#include<vector>
using namespace std;
class UnionFind
{
public:
UnionFind(size_t size)
:_ufs(size, -1)
{}
bool findRoot(int x)
{
int parent = x;
while (parent >= 0)
parent = _ufs[parent];
//路径压缩.提高下次查找效率
while (_ufs[x] >= 0)
{
int tmp = _ufs[x];
_ufs[x] = parent;
x = tmp;
}
return parent;
}
void Union(int x1, int x2)
{
int root1 = findRoot(x1);
int root2 = findRoot(x2);
if (root1 != root2)
{
_ufs[root1] += _ufs[root2];
_ufs[root2] = root1;
}
}
bool inSame(int x1, int x2)
{
return findRoot(x1) == findRoot(x2);
}
int size()
{
size_t size = 0;
for (auto x : _ufs)
if (x < 0)
size++;
return size;
}
private:
vector<int> _ufs;
};
原文地址：https://blog.csdn.net/m0_74317866/article/details/142432039
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！