制作自助网站,中华建设,做网站用什么面板好,wordpress xml文件目录 一#xff0c;什么是并查集
二#xff0c;并查集的结构
三#xff0c;并查集的代码实现
1#xff0c;并查集的大致结构和初始化
2#xff0c;find操作
3#xff0c;Union操作
4#xff0c;优化
小结#xff1a;
四#xff0c;并查集的应用场景
省份…目录 一什么是并查集
二并查集的结构
三并查集的代码实现
1并查集的大致结构和初始化
2find操作
3Union操作
4优化
小结
四并查集的应用场景
省份数量[OJ题] 一什么是并查集
核心概念并查集是一种 用于管理元素分组 的数据结构。
在一些应用问题中需将n个不同的元素划分成一些不相交的集合开始时n个元素各自成一个集合然后按照一定规律将部分集合合成一个集合也就是集合合并。并查集union-find)适合来描述这类问题。 对于并查集我们可以将它看成是一个森林森林是由多棵树组成的并查集中的一个个集合就可以看作是树。 示例 二并查集的结构
并查集的存储结构和树的双亲表示法相似。 所谓双亲表示法就是在树的节点中只存储父节点的指针不存储孩子节点的指针。通过指针可以找到父节点。因为对于一颗树来说可能有多个孩子 但只有一个父节点。 对于上图中 节点0的数组值为-4说明该节点为根节点。 节点6的数组值为0说明该节点的父节点为0。 节点7的数组值为0说明该节点的父节点为0。 节点8的数组值为0说明该节点的父节点为0。 三并查集的代码实现
并查集主要支持一下操作
查询find查询一个元素在哪个集合中。合并union)将两个集合合并为一个。
1并查集的大致结构和初始化 class UnionFind { public: UnionFind(size_t n) :_ufs(n,-1) {} //...... private: vectorint _ufs; }; 2find操作
在并查集中找到包含x的根 int findRoot(int x) { int root x; while (_ufs[root] 0) root _ufs[root]; return root; } 3Union操作
合并两个集合 void Union(int x1, int x2) { int root1 findRoot(x1); int root2 findRoot(x2); if (root1 root2) return; //在同一个集合中 //这里在合并的时候采用数据量小的向数据量大的合并 //也就是小树向大树合并 if (abs(_ufs[root1]) abs(_ufs[root2]))//root1节点更少 { _ufs[root2] _ufs[root1]; _ufs[root1] root2; //小树合并到大树 } else { //root2节点更少 _ufs[root1] _ufs[root2]; _ufs[root2] root1; } } 4优化
当树比较高时我们在反复查某个节点的根节点时每次都会花费大量时间。 优化方法路径压缩只要查找某个节点一次就将查找路径上的所有节点挂到根节点下面。 如图查找D的根A查找路径上包含节点B将节点D和节点B直接挂在根节点A的下面。 //路径压缩
int findRoot(int x)
{int root x;while (_ufs[root] 0)root _ufs[root];//路径压缩while (_ufs[x] 0){int parent _ufs[x];_ufs[x] root; //挂在根节点的下面x parent;}return root;
} 小结 上述实现的并查集支持连续元素。如果是处理非连续元素需要使用哈希表代替数组需额处理元素与索引的映射。 核心思路 哈希映射用unordered_map将任意类型元素映射为连续整数ID内部用数组管理父节点 动态扩容自动添加新元素无需预先指定规模。 模板化支持泛型数据类型如string等。 四并查集的应用场景 连通性检测判断网络中两个节点是否连通。 最小生成树Kruskal算法动态合并边避免环。 社交网络分组快速合并好友关系查询是否属于同一社交圈。 总结 并查集通过高效的查找与合并操作成为处理动态连通性问题的核心数据结构。其优化方法路径压缩、按秩合并确保了接近常数的单次操作时间复杂度适用于大规模数据场景。 其中的按秩合并就是合并集合时小树向大树合并。 省份数量[OJ题]
题目链接LCR 116. 省份数量 - 力扣LeetCode isConnected[i][j]1表示城市i和j连通连通的城市为一个省份。用并查集将连通的数据放入一个集合再统计最后的集合个数即可。
class Solution {
public:int findCircleNum(vectorvectorint isConnected) {int nisConnected.size();vectorint _ufs(n,-1);//查找根auto find[](int x)-int{int rootx;while(_ufs[root]0)root_ufs[root];return root;};for(int i0;in;i)for(int j0;jn;j){if(isConnected[i][j]1){//合并i和j集合int rootifind(i),rootjfind(j);if(rooti!rootj){_ufs[rooti]_ufs[rootj];_ufs[rootj]rooti;}}}//统计集合数int ret0;for(auto x:_ufs){if(x0)ret;}return ret;}
};
冗余连接[OJ题]
题目链接684. 冗余连接 - 力扣LeetCode class Solution {
public:vectorint findRedundantConnection(vectorvectorint edges) {//遍历edges数组//将在同一条边中的两个顶点放入一个集合//如果这条边的两个顶点已经在同一个集合中加入这条边后会出现环 返回这条边vectorint ufs(1010);int szedges.size();//初始化时各元素自成一个集合自己就是根for(int i0;isz;i)ufs[i]i;for(int j0;jsz;j){//找到边的两个顶点所在的集合也就是根节点int root1find(edges[j][0],ufs);int root2find(edges[j][1],ufs);//如果在一个集合加入这条边后会出现环if(root1root2)return edges[j];else{//两个集合独立合并两个集合ufs[root1]root2;}}return {0,0};}int find(int num,vectorint ufs){int rootnum;while(ufs[root]!root)rootufs[root];return root;}
};
等式方程的可满足性[OJ题]
本题链接990. 等式方程的可满足性 - 力扣LeetCode class Solution {
public:bool equationsPossible(vectorstring equations) {//并查集vectorint ufs(26,-1);auto findroot[](int x){int parentx;while(ufs[parent]0)parentufs[parent];return parent;};//将相等的放入同一集合中for(auto str:equations)if(str[1]){int root1findroot(str[0]-a);int root2findroot(str[3]-a);if(root1!root2){ufs[root1]ufs[root2];ufs[root2]root1;}}//遇到如果在同一个集合返回falsefor(auto str:equations){if(str[1]!){int root1findroot(str[0]-a);int root2findroot(str[3]-a);if(root1root2)return false;}}return true;}
};
