阅读量:1
1. 并查集的介绍
并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题（即所谓的并、查）。
在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集合，然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于那个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(union-find set)。
比如：某公司今年校招全国总共招生10人，西安招4人，成都招3人，武汉招3人，10个人来自不同的学校，起先互不相识，每个学生都是一个独立的小团体，我们给这10个人进行编号。
每个地方的学生自发组织成小分队一起上路，于是：西安的4名同学（编号为0，6，7，8）组成了一个团体，成都的三名同学（编号为1，4，9）组成了一个团体，武汉的3名同学（编号为2，3，5）组成了一个团体。假设由编号最小的同学担任队长。
有了这个结构之后，我们很容易就能判断出来某两位同学是否属于同一个团体，并且合并两个集合也非常方便，这就是并查集的价值所在。
2. 并查集的原理
在实际中我们可以通过一个数组来实现并查集，还是上面那个例子。我们定义一个数组，这个数组的下标就是每个成员的编号，数组中的值有两层意思：
1.对队长（根节点）来说，数组中保存这个集合中所有元素的个数 * -1。
2.对成员（除了根节点的其他结点）来说，数组中保存的是他的父节点的下标。
所以数组中值 < 0 的都是根节点，根节点得绝对值是这个集合的元素个数。
最初一开始所有同学都是一个独立的团体，所以先初始化为 -1。
后续相同城市的同学组成了一个团体。
物理结构图如下：
逻辑结构图如下：
并查集可以用来解决哪些问题？
1.查找元素属于哪个集合
由于数组中保存的是他父节点的下标，所以我们可以根据这个特点，一路向上查找，直到找到一个是值为负数的结点即可
2.查找两个元素是否属于同一集合
沿着数组表示的树形关系往上一直找到树的根，如果根相同表明在同一个集合，否则不在
3.将两个集合合并成一个集合
需要做以下两步
- 将两个集合中的元素合并
- 将一个集合名称改成另一个集合的名称
比如上面的例子，{0，6，7，8}集合和{1，4，9}进行合并。
注意观察数组的变化，1号由原来的-3变成0，0号由原来的-4变成了-7。
4.集合的个数
遍历数组，数组中元素为负数的个数即为集合的个数。
3. 并查集的实现
并查集的实现通常包含如下接口：
- 1.查找父节点下标
- 2.合并两个集合
- 3.返回集合的个数
- 4.判断两个值是否在同一个集合中
class UnionFindSet { public: UnionFindSet(size_t n) : _ufs(n, -1) {} //返回父节点的下标 size_t FindRoot(size_t posi); //合并两个集合 bool Union(size_t x1, size_t x2); //返回集合的个数 size_t Count(); //判断两个值是否在同一个集合中 bool InSameSet(size_t x1, size_t x2); private: vector<int> _ufs; };并查集的特点：
1.数组的下标对应集合中元素的编号
2. 数组中如果为负数，负号代表根，数字代表该集合中元素个数
3. 数组中如果为非负数，代表该元素双亲在数组中的下标
3.1 找到根节点
size_t FindRoot(size_t posi) { while (_ufs[posi] >= 0) { posi = _ufs[posi]; } return posi; }查找思路：如果一个结点是根节点，那么直接返回下标即可，如果不是根节点，那么就一路向上查找，直到找到根。
以上图为例，比如我们要查找9的根。根据数组我们可以看到9的父节点是1。继续向上查找，1号的父节点是0，到了0号，我们发现数据中保存的是-7，一个小于0的数，表示这个结点就是一个父节点。所以我们最终得到了9的根节点是0号。
3.2 合并两个集合
bool Union(size_t x1, size_t x2) { int root1 = FindRoot(x1); int root2 = FindRoot(x2); // 如果他们本身就在同一个集合中 if (root1 == root2) return false; // 默认将root1为较大的集合 if (_ufs[root1] > _ufs[root2]) swap(root1, root2); //将root2合并到root1下 _ufs[root1] += _ufs[root2]; _ufs[root2] = root1; return true; }先找到两个集合的根，如果这两个不在一个集合我们就进行合并，合并的方式是将一个集合当作另一个集合的根。
当然，上面的只是逻辑图，物理模型如下：
还有一点值得注意，就是我们要让root1为较大的那个集合，root2为较小的那个集合，这样做可以提高一点效率，因为我们是将root2合并到root1上的，如果root2的元素过多，root2再接到root1下，那么将会导致，root2中的所有元素每次都要多找一个值才能找到。
3.3 集合的个数
size_t Count() { size_t count = 0; for (auto e : _ufs) { if (e < 0) ++count; } return count; }遇到一个小于0的数说明这是一个集合，每遇到一个集合直接++，最后返回最终的结果。
3.4 判断两个数是否在同一个集合
bool InSameSet(size_t x1, size_t x2) { int root1 = FindRoot(x1); int root2 = FindRoot(x2); if (root1 == root2) return true; else return false; }直接找根即可，如果是同一个根就说明在同一个集合。
3.5 路径压缩
并查集的优势就是，能快速的查看两个数是否属于同一集合。但是有个问题，我们的合并两个集合是将一个集合直接变成另一个集合的孩子。也就是说，如果数据量较大的情况下，会导致并查集的高度变得很大，也就影响了查找效率，所以我们可以使用路径压缩的方式，减少树的高度。
路径压缩的方式是：我们使用FindRoot查找一个结点时，就把这个结点到根节点路径上的所有结点都变成根的孩子结点。
以下图为例：我们使用FIndRoot查找9号结点的根。
将9到根结点0路径上所有的结点都变成根节点0的孩子，也就是将9和1变成0的孩子。
我们发现以后再查找9所在的集合，只需找两次就行了。
//返回父节点的下标 size_t FindRoot(size_t posi) { int root = posi; while (_ufs[root] >= 0) { root = _ufs[root]; } //路径压缩 while (_ufs[posi] >= 0) { int parent = _ufs[posi]; _ufs[posi] = root; posi = parent; } return posi; }3.6 完整代码
class UnionFindSet { public: UnionFindSet(size_t n) : _ufs(n, -1) {} //返回父节点的下标 size_t FindRoot(size_t posi) { int root = posi; while (_ufs[root] >= 0) { root = _ufs[root]; } //路径压缩 while (_ufs[posi] >= 0) { int parent = _ufs[posi]; _ufs[posi] = root; posi = parent; } return posi; } bool Union(size_t x1, size_t x2) { int root1 = FindRoot(x1); int root2 = FindRoot(x2); // 如果他们本身就在同一个集合中 if (root1 == root2) return false; // 默认将root1为较大的集合 if (_ufs[root1] > _ufs[root2]) swap(root1, root2); //将root2合并到root1下 _ufs[root1] += _ufs[root2]; _ufs[root2] = root1; return true; } size_t Count() { size_t count = 0; for (auto e : _ufs) { if (e < 0) ++count; } return count; } bool InSameSet(size_t x1, size_t x2) { int root1 = FindRoot(x1); int root2 = FindRoot(x2); if (root1 == root2) return true; else return false; } private: vector<int> _ufs; };4. 并查集相关题目
4.1 省份数量
题目链接：LCR 116. 省份数量 - 力扣（LeetCode）
题目描述：
解题思路：如果两个城市连接了，就将他们加入同一个集合，最终判断有几个集合即可。
方法一：使用我们自己写的并查集
class UnionFindSet { public: UnionFindSet(size_t n) : _ufs(n, -1) {} //返回父节点的下标 size_t FindRoot(size_t posi) { int root = posi; while (_ufs[root] >= 0) { root = _ufs[root]; } //路径压缩 while (_ufs[posi] >= 0) { int parent = _ufs[posi]; _ufs[posi] = root; posi = parent; } return posi; } bool Union(size_t x1, size_t x2) { int root1 = FindRoot(x1); int root2 = FindRoot(x2); // 如果他们本身就在同一个集合中 if (root1 == root2) return false; //将root2合并到root1下 _ufs[root1] += _ufs[root2]; _ufs[root2] = root1; return true; } size_t Count() { size_t count = 0; for (auto e : _ufs) { if (e < 0) ++count; } return count; } bool InSameSet(size_t x1, size_t x2) { int root1 = FindRoot(x1); int root2 = FindRoot(x2); if (root1 == root2) return true; else return false; } void Print() { for (auto e : _ufs) { std::cout << e << " "; } std::cout << std::endl; } private: vector<int> _ufs; }; class Solution { public: int findCircleNum(vector<vector<int>>& isConnected) { int n = isConnected.size(); UnionFindSet ufs(n); for (size_t i = 0; i < n; i++) { for (size_t j = 0; j < n; j++) { if (isConnected[i][j] == 1) { ufs.Union(i, j); } } } ufs.Print(); return ufs.Count(); } };发现相同省份就将他们加入同一个集合即可。
但是这种方式非常麻烦，要先手动实现一个并查集，实际上我们可以发现，我们只用到了Union函数和Count函数。
方案二：模拟并查集
我们完全可以用数组模拟出一个并查集，只需要实现其中的合并功能就行了。
class Solution { public: int findCircleNum(vector<vector<int>>& isConnected) { int n = isConnected.size(); vector<int> ufs(n, -1); auto FindRoot = [&ufs](size_t index) { int root = index; while (ufs[root] >= 0) { root = ufs[root]; } return root; }; for (size_t i = 0; i < n; i++) { for (size_t j = 0; j < n; j++) { if (isConnected[i][j] == 1) { //先找根 int root1 = FindRoot(i); int root2 = FindRoot(j); if (root1 != root2) { ufs[root1] += ufs[root2]; ufs[root2] = root1; } } } } size_t count = 0; for (auto e : ufs) { if (e < 0) ++count; } return count; } };4.2 等式方程的可满足性
题目链接：990. 等式方程的可满足性 - 力扣（LeetCode）
题目描述：
解题思路：如果表达式的符号为==，就将左右两个操作数加入同一个集合中，遍历一遍之后，再次遍历，找到表达式为 != 的符号，判断左右两边是否在同一个集合中，如果不满足条件则返回false，满足则返回true。
class Solution { public: bool equationsPossible(vector<string>& equations) { int n = equations.size(); vector<int> ufs(26, -1); auto FindRoot = [&ufs](size_t index) { while (ufs[index] >= 0) { index = ufs[index]; } return index; }; for (auto& str : equations) { if (str[1] == '=') { int root1 = FindRoot(str[0] - 'a'); int root2 = FindRoot(str[3] - 'a'); if (root1 != root2) { ufs[root2] = root1; } } } for (auto& str : equations) { if (str[1] == '!') { int root1 = FindRoot(str[0] - 'a'); int root2 = FindRoot(str[3] - 'a'); if (root1 == root2) return false; } } return true; } };