并查集的原理

在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个
单元素集合，然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一
个元素归属于那个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(union-find
set)。

举个例子看看
比如：某公司今年校招全国总共招生10人，西安招4人，成都招3人，武汉招3人，10个人来自不
同的学校，起先互不相识，每个学生都是一个独立的小团体，现给这些学生进行编号：{0, 1, 2, 3,
4, 5, 6, 7, 8, 9}; 给以下数组用来存储该小集体，数组中的数字代表：该小集体中具有成员的个
数。

至于，为什么是负号呢？
聪明的小伙伴们，可以先自己思考一下（为什么人数要用负数表示呢）

毕业后，学生们要去公司上班，每个地方的学生自发组织成小分队一起上路，于是：
西安学生小分队s1={0,6,7,8}，成都学生小分队s2={1,4,9}，武汉学生小分队s3={2,3,5}就相互认识
了，10个人形成了三个小团体。假设右三个群主0,1,2担任队长，负责大家的出行。
于是就变成了三个小团体，用三棵树表示

然后，我们将这三棵树，也就是三个集合，用双亲表示法，写到一个数组中，这就是并查集。

所以，并查集其实就是一个森林

看到这里，相信，大家应该能够知道为什么会用负数表示人数

OK，
总结一下，

1. 当数组中的元素大于0的时候，该元素就是该节点的父节点的下标
2. 当数组中的元素小于0的时候，该元素的绝对值就是这颗树，也就是这个集合中的元素的个数

但是，还是存在一个问题，
其实注意看，我们的十名同学编号为0到9，这其实是一个映射，我们在实现的时候建议将这些映射用map存起来，当需要根据同学找编号的时候，就能够发挥作用了。

并查集的实现

并查集主要需要实现以下功能

1. 合并
2. 查找
3. 返回集合的个数
4. 判断两个元素是不是在同一个集合

并查集的结构

本质结构是一个森林，用vector来存
但我们最好还需要存一个map，来存映射关系（当然，也可以不存）

查找根节点的位置

查找根节点的位置是并查集操作的核心

如何查找根节点的位置
我们只需要根据下面的两条性质即可

1. 当数组中的元素大于0的时候，该元素就是该节点的父节点的下标
2. 当数组中的元素小于0的时候，该元素的绝对值就是这颗树，也就是这个集合中的元素的个数

一直循环向上找根节点即可，最后返回下标

int FindRoot(int a)
{while(_uft[a] >= 0){a = _uft[a];}return a;
}

---

集合的合并

集合的合并，我们只需要去处理根即可，比如下图中

如果我们需要合并4和7，我们只需要找到4所在的集合和7所在的集合，将两个集合合并就行
而合并的时候我们只需要处理根，将1合并到0的下面

具体怎么操作
很简单

我们只需要将1对应的下标中存的个数，加到0对应的下标中存的个数中，在将1对应的下标中存的元素改成0的下标即可。

void Union(int a,int b)
{int root1 = FindRoot(a);int root2 = FindRoot(b);if(root1 == roo2)//在同一个集合就不用合并return;_uft[root1] += _uft[root2];_uft[root2] = root1;}

---

并查集中集合的个数

太简单了，直接遍历vector，记录其中负元素的个数
返回即可。

int SetSize()
{int ret = 0;for(auto& e:_uft){if (e < 0)ret++;}return ret;
}

---

判断两个元素是不是在同一个集合

太简单了，直接找两个元素的根，然后进行比较即可

bool IsSameSet(int a, int b)
{return FindRoot(a) == FindRoot(b);
}

---

并查集的优化

并查集确实挺不错的，但是，可能在合并多次之后，导致其中有集合的高度过高了，这个时候，查找的时候就不那么好用了。

于是，这里就进行路径压缩，来缩短集合的高度。

网络上有一些地方写这里路径压缩的时候采用递归去写
但是呢，高度已经很高了，用递归的话，资源消耗有会继续加大，所以，我建议采用非递归去写。

主要在两个地方可以进行优化

合并的优化

在合并的时候，我们规定节点少的集合合并到节点多的集合
这样集合的高度就没有增加，这里有点抽象
我们这么想

当节点少的集合合并到节点多的集合
新的高度就是max(节点多的集合，节点少的集合 + 1)
高度没有发生变化

而当节点多的集合合并到节点少的集合
新的高度就是max(节点多的集合 + 1，节点少的集合）
高度增加了

显然，我们应该要将节点少的集合合并到节点多的集合
所以，优化后的合并代码如下

void Union(int a, int b)
{int root1 = FindRoot(a);int root2 = FindRoot(b);if (root1 == root2)//如果在同一个集合就不用合并return;if (abs(_uft[root1]) < abs(_uft[root2]))//把节点少的集合合并到节点大的集合{swap(root1, root2);}_uft[root1] += _uft[root2];_uft[root2] = root1;
}

---

查找根节点的优化

这里就是真正的路径压缩了
我们在查找根的时候，如果经历了多次才找到根，那么就可以将这个节点，直接加到根下面去，这样就可以缩短高度。

其实就是，我们在找到根之后，将路径上的节点全部都挂到根下面去，通过这样的操作来缩短高度

int FindRoot(int a)
{int root = a;;while (_uft[root] >= 0){root = _uft[root];}while (_uft[a] >= 0)//路径压缩{int parent = _uft[a];//记录上一个节点的下标_uft[a] = root;a = parent;}return root;
}

并查集的应用

我们在这里看两道题目

省份数量

链接：leetcode链接

思路分析
我们将一个省份作为一个集合，当两个城市相连，就合并
遍历完之后，再返回并查集中集合的个数即可。

template<class K>
class UnionFindSet
{
private:vector<int> _uft;//并查集map<K, int> _indexMap;//下标映射关系public:UnionFindSet(int n = 10){_uft.resize(n, -1);}void Union(int a, int b){int root1 = FindRoot(a);int root2 = FindRoot(b);if (root1 == root2)//如果在同一个集合就不用合并return;if (abs(_uft[root1]) < abs(_uft[root2]))//把节点少的集合合并到节点大的集合{swap(root1, root2);}_uft[root1] += _uft[root2];_uft[root2] = root1;}int FindRoot(int a){int root = a;;while (_uft[root] >= 0){root = _uft[root];}while (_uft[a] >= 0)//路径压缩{int parent = _uft[a];//记录上一个节点的下标_uft[a] = root;a = parent;}return root;}int SetSize(){int ret = 0;for (int i = 0; i < _uft.size(); ++i){if (_uft[i] < 0)ret++;}return ret;}bool IsSameSet(int a, int b){return FindRoot(a) == FindRoot(b);}
};class Solution {
public:int findCircleNum(vector<vector<int>>& isConnected) {UnionFindSet<int> uft(isConnected.size());for(int i = 0;i < isConnected.size();++i){for(int j = 0;j < isConnected[0].size();++j){if(isConnected[i][j]==1){uft.Union(i,j);}}}return uft.SetSize();}
};

等式方程式的可满足性

链接：leetcode链接

我们用26个字母去建立一个26个元素的并查集
我们遍历字符串数组，遇到等式的时候，就去合并等式两边的元素所在的集合
遍历完之后，就建立好了并查集
然后开始查找即可
接着再去遍历一遍字符串数组，遇到不等式的时候，去判断等式两边的元素是否不在同一个集合

template<class K>
class UnionFindSet
{
private:vector<int> _uft;//并查集map<K, int> _indexMap;//下标映射关系public:UnionFindSet(int n = 10){_uft.resize(n, -1);}void Union(int a, int b){int root1 = FindRoot(a);int root2 = FindRoot(b);if (root1 == root2)//如果在同一个集合就不用合并return;if (abs(_uft[root1]) < abs(_uft[root2]))//把节点少的集合合并到节点大的集合{swap(root1, root2);}_uft[root1] += _uft[root2];_uft[root2] = root1;}int FindRoot(int a){int root = a;;while (_uft[root] >= 0){root = _uft[root];}while (_uft[a] >= 0)//路径压缩{int parent = _uft[a];//记录上一个节点的下标_uft[a] = root;a = parent;}return root;}int SetSize(){int ret = 0;for (int i = 0; i < _uft.size(); ++i){if (_uft[i] < 0)ret++;}return ret;}bool IsSameSet(int a, int b){return FindRoot(a) == FindRoot(b);}
};class Solution {
public:bool equationsPossible(vector<string>& equations) {UnionFindSet<string> uft(26);for(auto& e:equations){if(e[1] == '='){uft.Union(e[0] - 'a',e[3] - 'a');}}for(auto& e:equations){if(e[1] == '!'){if(uft.IsSameSet(e[0] - 'a',e[3] - 'a') == true)return false;}}return true;}
};

---

在做算法提的时候简化并查集

并查集用起来爽啊，这么方便，但是，真的每次都要手搓一个并查集出来吗？

其实是不需要的，我们借助lambda表达式，可以实现出找根节点下标的函数即可，其他的函数，可以很快的在过程中写出来

我们以第二道题为例
简化一下代码

bool equationsPossible(vector<string>& equations) {vector<int> uft(26,-1);auto FindRoot = [&uft](int a){while(uft[a] >= 0)a = uft[a];return a;};for(auto& e:equations){if(e[1] == '='){int root1 = FindRoot(e[0] - 'a');int root2 = FindRoot(e[3] - 'a');if(root1 != root2){uft[root1] += uft[root2];uft[root2] = root1;}}}for(auto& e:equations){if(e[1] == '!'){int root1 = FindRoot(e[0] - 'a');int root2 = FindRoot(e[3] - 'a');if(root1 == root2)return false;}}return true;}

利用lambda表达式可以快速构建起来简化并查集，在做题的时候非常好用。

---