Hello大家好！很高兴我们又见面啦！给生活添点passion，开始今天的编程之路！
我的博客：<但凡.
我的专栏：《编程之路》、《数据结构与算法之美》、《题海拾贝》、《C++修炼之路》
欢迎点赞，关注！
目录
1、并查集引入
并查集是一种数据结构，主要用于处理一些不相交集合的合并及查询问题。它支持两种操作：查找某个元素属于哪个集合（Find），以及合并两个集合（Union）。并查集的高效实现通常基于路径压缩和按秩合并的优化。
也就是说，我们可以使用并查集，达到快速判断某两个元素是否在一个集合中。对于传统的并查集，查找的时间复杂度为O(N)，基于后续的优化可以达到更高。
2、并查集的实现
2.1、初始化
其实看框架我们也能看出来并查集很简单，成员变量就一个数组。这个数组的每个下标对应一个节点，这个下标存储的值分为两种情况：如果当前节点是根节点，就存储一个负数，这个负数的绝对值表示当前集合中的元素数量。如果当前节点是叶子节点，就存储一个大于等于0的整数。这个整数是当前节点的父节点的下标。
class UnionFindSet
{
public:
UnionFindSet(int size)
:_set(size, -1)
{}
private:
std::vector<int> _set;
};2.2、查找
查找操作，我们只需要一直往上查找，直到找到根节点就行了。我们重点说一下路径压缩：路径压缩就是把查找过程中遇到的所有节点的父亲都直接设置成当前集合的根节点。这样的话，对于已经路径压缩过的点，下次查找就可以达到O(1)的时间复杂度（准确来说是O(α(n))，其中α(n)是反阿克曼函数，可以视为常数）。
size_t FindRoot(int x)
{
int root = x;
while (_set[root] >= 0)
{
root = _set[root];
}
//路径压缩
while (_set[x] >= 0)
{
//把从这到根的所有节点的父亲都设置成跟节点
int parent = _set[x];
_set[x] = root;
x = parent;
}
return root;
}2.3、合并
当两个节点不是同一集合时，我们对两集合进行合并。按秩合并就是将数量小的树合并到数量大的树上，这样可以尽可能的维护树的平衡。
void Union(int x1, int x2)
{
int root1 = FindRoot(x1);
int root2 = FindRoot(x2);
if (root1 != root2)
{
//按秩合并
//控制数据量小的往数据量大的集合合并
if (abs(_set[root1]) < abs(_set[root2]))
std::swap(root1, root2);
//不是一个组的就合并
//把root2合并到root1
_set[root1] += _set[root2];
_set[root2] = root1;
}
}2.4、其他操作
这两个操作是检测两节点是否在一个集合中和集合数，很简单，大家看看就好：
bool InSet(int x1, int x2)
{
return FindRoot(x1) == FindRoot(x2);
}
size_t SetCount()
{
size_t count = 0;
for (size_t i = 0;i < _set.size();i++)
{
if (_set[i] < 0)
count++;
}
return count;
}经过路径压缩和按秩合并，我们的并查集合并，查找操作时间复杂度可以到达常数级别。
好了，今天的内容就分享到这，我们下期再见！