网站建设代理平台有哪些_青岛高端网站设计公司_长沙正规seo优化价格_直通车优化推广

• 并查集是一种树型的数据结构
• 是一种森林，森林中的每棵树表示一个集合，树中的结点对应一个元素

并查集的原理

现在有10个人（从0开始编号），刚开始这10个人互不认识，所以各自属于一个集合。

并查集会用一个数组来表示这10个人之间的关系，数组的下标对应就是这10个人的编号，刚开始时数组中的元素都初始化为-1。

数组中的值为负数，即该位置是一颗树的根，且负数的绝对值表示的这棵树（集合）中数据的个数
经过一段时间的相处最终形成了三个朋友圈

并查集数组中各个位置的值更新

4号和8号认识了，他们所在的两个集合就需要进行合并，最终变成了两个集合

合并时，先分别找到这两个元素所在集合的根结点，再将一个集合合并到另一个集合，最后更新数组中根结点的值

并查集的实现

从上面的分析中，我们可以看出并查集的本质是一个数组，我们对数组内元素不断进行调整，所以我们这样定义并查集

class UnionFind
{
public:// 刚开始每个人都是独立的，所以刚开始时数组中的元素都初始化为-1UnionFind(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;
};