当前位置：首页 > news >正文

【高效管理集合】并查集的实现与应用

news 来源：原创 2024/9/29 21:53:01

在这里插入图片描述

文章目录

并查集的概念
- 主要操作
- 优化技术
- 应用场景
并查集的实现
- 基本框架
- 并查集的主要接口
- 总体代码
并查集的应用
- 省份的数量
- 等式方程的可满足性
总结

并查集的概念

并查集，也称为不相交集，是一种树形的数据结构，用于处理一些不相交集合的合并及查询问题。简单来说，它主要用于处理元素分组的问题。

主要操作

查找（Find）
确定元素所属的集合，通常返回该元素的根节点。
合并（Union）
将两个集合合并为一个集合。

优化技术

路径压缩
在查找操作中，将访问路径上的节点直接连接到根节点，以减少树的高度。
按秩合并
总是将较小的树合并到较大的树下，以保持树的平衡。

应用场景

并查集广泛用于以下问题：

判断两个元素是否在同一集合中。
合并两个集合。
最小生成树算法。
网络连接问题等。

这种数据结构在许多算法中都非常有效，尤其是在处理集合合并和查询时。

并查集的实现

基本框架

class UnionFindset
{
public:UnionFindset(size_t n){}//合并接口void Union(int x1, int x2){}//找根的位置int FindRoot(int x){}//是否在相同一个集合bool IsInSet(int x1, int x2){}//并查集中有多少个集合size_t SetSize(){}//压缩路径void findWithPathCompression(){}
private://下标---->人vector<int> _ufs;
};

在这里插入图片描述

并查集的主要接口

构造函数：
在这里插入图片描述

UnionFindset(size_t n)//将每个位置初始化为-1:_ufs(n, -1)
{}

将每个位置初始化为-1，在并查集中存储的大于零的数表示的是父亲的下标，存储的小于0的值表示的是根节点。
索引根的位置：

//找根的位置
int FindRoot(int x)
{int parent = x;//索引根的位置while (_ufs[parent] > 0) parent = _ufs[parent];return parent;
}

当下标对应的数是负数的时候，当前位置就是根。
合并不相关集合：

//合并接口
void Union(int x1, int x2)
{int parent1 = FindRoot(x1), parent2 = FindRoot(x2);//本身就在一个集合就不需要进行合并if (parent1 == parent2) return;if (parent1 > parent2) swap(parent1, parent2);else{_ufs[parent1] += _ufs[parent2];//索引下标_ufs[parent2] = parent1;}
}

合并两个不相关集合，只需要先找到根，复用上面的接口，然后将这两个集合的根进行合并即可，将任意一个根对应的数加到另一个数的根上，然后将这个跟的下标改为另一个根的下标即可，就完成了合并了。
判断是否在同一集合：
只需要判断两个节点的根是否相同即可。

//是否在相同一个集合
bool IsInSet(int x1, int x2)
{return FindRoot(x1) == FindRoot(x2);
}

查看有多少个集合：
只需要查看数组中有多少个小于0的位置即可。

//并查集中有多少个集合
size_t SetSize()
{size_t size = 0;for (size_t i = 0;i < _ufs.size();i++)if (_ufs[i] < 0)size++;return size;
}

压缩路径：

int FindWithPathCompression(int x)
{if (_ufs[x] < 0){return x; // 找到根节点}// 递归查找根节点，并进行路径压缩_ufs[x] = FindWithPathCompression(_ufs[x]);return _ufs[x]; // 返回根节点
}

总体代码

class UnionFindset
{
public:UnionFindset(size_t n)//将每个位置初始化为-1:_ufs(n, -1){}//合并接口void Union(int x1, int x2){int parent1 = FindRoot(x1), parent2 = FindRoot(x2);//本身就在一个集合就不需要进行合并if (parent1 == parent2) return;if (parent1 > parent2) swap(parent1, parent2);else{_ufs[parent1] += _ufs[parent2];//索引下标_ufs[parent2] = parent1;}}//找根的位置int FindRoot(int x){int parent = x;//索引根的位置while (_ufs[parent] > 0) parent = _ufs[parent];return parent;}//是否在相同一个集合bool IsInSet(int x1, int x2){return FindRoot(x1) == FindRoot(x2);}//并查集中有多少个集合size_t SetSize(){size_t size = 0;for (size_t i = 0;i < _ufs.size();i++)if (_ufs[i] < 0)size++;return size;}//压缩路径int FindWithPathCompression(int x){if (_ufs[x] < 0){return x; // 找到根节点}// 递归查找根节点，并进行路径压缩_ufs[x] = FindWithPathCompression(_ufs[x]);return _ufs[x]; // 返回根节点}
private://下标---->人vector<int> _ufs;
};

并查集的应用

省份的数量

题目信息：

示例：

代码展示：

class Solution 
{
public://给的是城市的下标int findCircleNum(vector<vector<int>>& isConnected) {//vector模拟并查集行为vector<int> ufs(isConnected.size(),-1);//需要用引用进行捕获auto FindRoot=[&ufs](int x){while(ufs[x]>=0) x=ufs[x];return x;};//遍历二维数组for(size_t i=0;i<isConnected.size();i++){for(size_t j=0;j<isConnected[i].size();j++){//如果这两个城市相连，就进入一个集合if(isConnected[i][j]==1){int root1=FindRoot(i),root2=FindRoot(j);if(root1!=root2){//将两个合并ufs[root1]+=ufs[root2];//存父亲的下标ufs[root2]=root1;}}}}int n=0;for(auto e:ufs)if(e<0)n++;return n;}
};

等式方程的可满足性

题目信息：

示例：

代码展示：

class Solution 
{
public:bool equationsPossible(vector<string>& equations) {//开26个空间vector<int> ufs(26,-1);auto FindRoot=[&ufs](int x){while(ufs[x]>=0) x=ufs[x];return x;};//第一遍找相等的字母for(auto& str:equations){if(str[1]=='='){int root1=FindRoot(str[0]-'a'),root2=FindRoot(str[3]-'a');if(root1!=root2){ufs[root1]+=ufs[root2];ufs[root2]=root1;}}}//第二遍找不同的字母，如果不同的字母在一个集合中，返回falsefor(auto& str:equations){if(str[1]=='!'){int root1=FindRoot(str[0]-'a'),root2=FindRoot(str[3]-'a');if(root1==root2) return false;}}return true;}
};