并查集原理及实现：路径压缩，按秩合并
目录
并查集原理
- 在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集合，然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于那个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(union-find set)。
假设有10个元素，如下所示：0~9为元素值，-1是初始化的值。
现在他们被分为三个小组：0 6 7 8 为一组，0为组长 ；1 4 7 一组，1为组长 ； 2 3 5一组，2为组长；如下集合树的表示：
- 数组的下标对应集合中元素的编号
- 数组中如果为负数，负号代表根，数字代表该集合中元素个数
- 数组中如果为非负数，代表该元素双亲在数组中的下标
现在假设集合0ui集合1要合并，只需要将元素0的内容加上元素1的内容（-4 + -3 = -7），将元素1的内容改为元素0的下标，也就是0；如下图：
常见操作
- 查找（Find）：确定元素所属的集合（通常返回根节点）。
- 合并（Union）：将两个元素所在的集合合并为一个集合。
- 计数（Count）：计算一共有多少个集合。
关键操作与优化
路径压缩（Path Compression）
- 在查找时，将节点直接指向根节点，缩短后续查询路径，使树更扁平。
- 示例：find(x) 时，递归或迭代地将路径上的所有节点父指针指向根。
按秩合并（Union by Rank/Height）
- 合并时，将较矮的树挂到较高树的根下，避免树过高。
- 维护一个rank数组记录树的高度，合并时比较根节点的rank。
查找（Find）代码及解析
//查找它所属集合的根 带路径压缩的代码 循环版本
int FindRoot(int index)
{while (_ufs[index] >= 0){_ufs[index] = _ufs[_ufs[index]];index = _ufs[index];}return index;
}// 查找根节点（带路径压缩） 递归版本
int FindRoot(int index)
{if (_ufs[index] >=0){_ufs[index] = FindRoot(_ufs[index]); // 递归路径压缩}return _ufs[index];
}
合并（Union）代码及解析
//给两个下标，将两个标所属的集合合并成一个集合bool Union(int index1,int index2){int root1 = FindRoot(index1);int root2 = FindRoot(index2);//属于同一个集合 直接返回if (root1 == root2) return false;//第一种情况：root1的高度大于root2，直接将root2合并到root1上，并且因为root1高度小于root2.合并并不会导致高度增加if (_height[root1] > _height[root2]){_ufs[root1] += _ufs[root2];_ufs[root2] = root1;}//第一种情况：root1的高度小于等于root2，直接将root2合并到root1上// （1）root1高度小于root2的高度，所以合并并不会导致高度增加//（2）如果root1的高度等于root2的高度，合并就会导致高度增加--->如果root2合并到root1，则root1高度会+1else{_ufs[root2] += _ufs[root1];_ufs[root1] = root2;if (_height[root1] == _height[root2])_height[root2]++;}return true;}
总代码
class UnionFindSet
{
public:UnionFindSet(size_t N){_ufs.resize(N,-1);_height.resize(N, 1);}//查找它所属集合的根 带路径压缩的代码 循环版本int FindRoot(int index){while (_ufs[index] >= 0){_ufs[index] = _ufs[_ufs[index]];index = _ufs[index];}return index;}// 查找根节点（带路径压缩） 递归版本int FindRoot(int index){if (_ufs[index] >=0){_ufs[index] = FindRoot(_ufs[index]); // 递归路径压缩}return _ufs[index];}//给两个下标，将两个标所属的集合合并成一个集合bool Union(int index1,int index2){int root1 = FindRoot(index1);int root2 = FindRoot(index2);//属于同一个集合 直接返回if (root1 == root2) return false;//第一种情况：root1的高度大于root2，直接将root2合并到root1上，并且因为root1高度小于root2.合并并不会导致高度增加if (_height[root1] > _height[root2]){_ufs[root1] += _ufs[root2];_ufs[root2] = root1;}//第一种情况：root1的高度小于等于root2，直接将root2合并到root1上// （1）root1高度小于root2的高度，所以合并并不会导致高度增加//（2）如果root1的高度等于root2的高度，合并就会导致高度增加--->如果root2合并到root1，则root1高度会+1else{_ufs[root2] += _ufs[root1];_ufs[root1] = root2;if (_height[root1] == _height[root2])_height[root2]++;}return true;}// 检查两个元素是否属于同一集合bool isConnected(int x, int y){return FindRoot(x) == FindRoot(y);}//统计集合的个数size_t Count()const{size_t count = 0;for (auto e : _ufs){if (e < 0) ++count;}return count;}~UnionFindSet() {}
private:vector<int> _ufs;vector<int> _height;
};
并查集的应用
力扣：省份的数量
我的代码：
class Solution {
public:int findCircleNum(vector<vector<int>>& isConnected) {int n = isConnected.size();vector<int> _ufs(n,-1);auto FindRoot = [&_ufs](int x){while(_ufs[x]>=0){x = _ufs[x];}return x;};for(int i = 0;i<n;++i){for(int j = 0;j<n;++j){if(isConnected[i][j]==1){int x = FindRoot(i);int y = FindRoot(j);if(x!=y){_ufs[x]+=_ufs[y];_ufs[y]=x;}}}}int Count = 0;for(auto e:_ufs){if(e<0) ++Count;}return Count;}
};
等式方程的可满足性
class Solution {
public:/*解题思路：1. 将所有"=="两端的字符合并到一个集合中2. 检测"!=" 两端的字符是否在同一个结合中，如果在不满足，如果不在满足*/bool equationsPossible(vector<string>& eq) {vector<int> _ufs(26, -1);auto FindRoot = [&_ufs](int x) {while (_ufs[x] >= 0) {x = _ufs[x];}return x;};// 第一遍：把相等的合并for (auto str : eq) {if (str[1] == '=') {int rootx = FindRoot(str[0] - 'a');int rooty = FindRoot(str[3] - 'a');if (rootx != rooty) {_ufs[rootx] += _ufs[rooty];_ufs[rooty] = rootx;}}}// 第二遍：遍历，如果发现不相等的两个元素在一个集合，说明相悖，返回falsefor (auto str : eq) {if (str[1] == '!') {int rootx = FindRoot(str[0] - 'a');int rooty = FindRoot(str[3] - 'a');if (rootx == rooty)return false;}}return true;}
};