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