并查集介绍
文章目录：
- 并查集原理
- 并查集实现
- 并查集的类结构
- 并查集的合并
- 统计集合数量
并查集原理
在一些应用问题中，需要将 n 个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集合，然后按照一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于哪一个集合的运算。适合于描述这类问题的抽象数据类型称为并查集（union-find disjoint sets）。
并查集是一种树形的数据结构，用于处理一些不相交的集合的合并及查询问题。并查集的思想是用一个数组表示整片森林，数的根节点唯一标识了一个集合，我们只要能找到某个元素的树根，就能确定它在哪个集合里面。
例如：某校某班今年新招生10人，西安4人，成都3人，海南3人，10个人来自不同的地方，刚开始互相不认识，每个学生都是一个独立的小团体，现在给10个学生进行编号：0 - 9 号，下面我们用数组来存储该小集体，数组中的数字代表：该小集体中具有成员的个数。
到校之后，每个地方的学生自发组成一个小分队，即西安分队 s1 = {0，6，7，8}，成都分队 s2 = {1，4，9}，海南分队 s3 = {2，3，5}，10个人形成了三个小团体。假设每个小分队的第一个成员 0，1，2 担任队长。
经过一段时间之后他们互相就熟悉起来了。
通过上面两图，可以得出以下结论：
- 数组的下标对应集合中元素的编号
- 数组中如果为负数，负号代表根，数字代表该集合中元素的个数
- 数组中如果为非负数，代表该元素的父亲在数组中的下标
来到学校学习一段时间之后，西安小分队中8号同学与成都小分队中1号同学成为了朋友，通过同学之间的相互结束，最后合并为一个小团体：
现在0集合有7个人，2集合有三个人，总共两个小团体。
通过以上，并查集一般可以解决下列问题：
- 查找元素属于哪个集合（沿着数组表示树形关系往上一直找到根，即树中元素为负数的位置）。
- 查看两个元素是否属于同一个集合（沿着数组表示的树形关系一直往上找到树的个，若两个元素根在同一个集合，那么就在一个集合，否则不在一个集合）。
- 将两个集合合并为一个集合（将两个集合中的元素合并，让其中一个集合的名称改为另外一个集合的名称）。
- 统计集合的个数（遍历数组，统计数组中元素为负数的个数即为集合的个数）。
并查集实现
并查集的类结构
并查集的底层结构使用 vector 实现，在初始化的时候，将 vector 中的每个位置的值置为 -1。便于统计每个小集合中元素的个数。
class UnionFindSet
{
public:// 初始化时，将数组中元素全部设置为-1UnionFindSet(size_t n):_ufs(n, -1){}private:vector _ufs;
};
并查集的合并
并查集合并的步骤：
- 找到待合并的两个元素的根的下标。
- 判断它们是否已经在同一个集合，若不在同一集合，则进行以下步骤。
- 将数据量小的集合往数据量大的集合合并，然后合并两个集合元素，小的集合名称改为大的集合名称。
在每一次查找下标的时候，顺便进行路径压缩。避免路径过长造成效率损失。具体怎么做可以详细看看代码：
// 给一个元素的编号，找到该元素所在集合的名称
int FindRoot(int index)
{// 如果数组中存储的是负数，则找到，否则一直继续查找int root = index;while (_ufs[root] >= 0){root = _ufs[root];}// 路径压缩while (_ufs[index] > 0){int parent = _ufs[index];_ufs[index] = root;index = parent;}return root;
}void Union(int x1, int x2)
{int root1 = FindRoot(x1);int root2 = FindRoot(x2);// 如果root1==root2，本身就在一个集合，就没有必要合并了if (root1 == root2)return;// 若没有在一个集合，则数据量小的集合往数据量大的集合合并if (abs(_ufs[root1]) < abs(_ufs[root2]))swap(root1, root2);// 将两个集合中元素合并_ufs[root1] += _ufs[root2];// 将其中一个集合的名称改为另外一个_ufs[root2] = root1;
}
统计集合数量
// 统计集合的个数，数组中负数的个数，即为集合的个数
size_t Size()const
{size_t count = 0;for (auto e : _ufs){if (e < 0)++count;}return count;
}