文章目录
- 并查集的概念
- 主要操作
- 优化技术
- 应用场景
- 并查集的实现
- 基本框架
- 并查集的主要接口
- 总体代码
- 并查集的应用
- 省份的数量
- 等式方程的可满足性
- 总结
并查集的概念
并查集,也称为不相交集,是一种树形的数据结构,用于处理一些不相交集合的合并及查询问题。简单来说,它主要用于处理元素分组的问题。
主要操作
-
查找(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;}
};
总结
并查集(Union-Find)是一种高效的数据结构,广泛应用于解决动态连通性问题。通过支持合并和查找操作,并查集能够有效管理和查询集合关系。其核心优化技术——路径压缩和按秩合并,显著提高了操作的效率,使得在大规模数据处理时依然保持良好的性能。
在实际应用中,理解并掌握并查集的原理和实现方式,能够帮助开发者解决许多复杂问题,如图论算法、网络连接等。通过本次介绍,希望能对并查集的概念和应用提供一个清晰的认识,为进一步的学习和实践打下基础。