有哪些做买家秀的网站,win2008 iis配置网站,重庆的汽车网站建设,佛山网站建设开发团队并查集是简单的数据结构#xff0c;学会并查集#xff0c;为图打好基础。 并查集的概念
是树状的数据结构#xff0c;用于处理相交集合的合并与查询
通常用森林表示#xff0c;一片森林表示一个集合 并查集一般需要完成 查找元素属于哪个集合查看两个元素是否属于同一个集…并查集是简单的数据结构学会并查集为图打好基础。 并查集的概念
是树状的数据结构用于处理相交集合的合并与查询
通常用森林表示一片森林表示一个集合 并查集一般需要完成 查找元素属于哪个集合查看两个元素是否属于同一个集合将两个集合归并成一个集合集合的个数 并查集的原理
假设有10个人用集合表示为{0123456789}
我们用数组表示这十个人 数组的下标表示人的编号数组的内容表示每个人认识其中人的数目 -1 表示只认识自己) 表示为10片森林 经过一段时间后他们形成三个小团体s1{0,6,7,8} s2{1,4,9} s3{ 2,3,5} 利用并查集表示
数组的下标对应集合中元素的编号数组中如果为负数负号代表根数字代表该集合中元素个数数组中如果为非负数代表该元素双亲在数组中的下标 所以在并查集中我们会关注数组的下标和数组的内容。
如果数组的内容是负数那么他就是根Root
如果数组的内容为非负数那么就指向他的父亲。 所以我们能简单解决这些问题 查找元素属于哪个集合 沿着树形关系一直往上寻找到根直到找到内容为负数的 查看元素是否属于同一个集合 寻找到根不同则表示不是同一个集合 将两个集合归并成一个集合 一个集合归并到另一个集合中并修改集合的内容 集合的个数 多少个负数内容的位置就有多少个集合 接下来来简单实现一个并查集 并查集的模拟
框架
//并查集
class UnionFindSet {
public://构造函数UnionFindSet(int n);//查找元素所在的集合int findRoot(int x);//合并两个元素所在的集合void Union(int x1, int x2)//获取并查集中集合的个数int SetCount();
private:vectorint _set;各个结点之间的关系
};构造
接收vector容器应该预留的空间
初始化为-1 UnionFindSet(int size):_set(size,-1){}
不需要自定析构函数
默认会调用系统默认析构 查找root
一直向上寻找变换x 直到找到内容为负数 //查找元素是否在集合里size_t FindRoot(int x){while (_set[x] 0){x _set[x];}return x;} 合并俩个集合
将B合并到A中A的根内容要改变B的根内容也要改变 //合并void Union(int x1, int x2){int root1 FindRoot(x1);int root2 FindRoot(x2);if (root1 ! root2){_set[root1] _set[root2];_set[root2] root1; }}
路径压缩
如果有大量的数据那么树的层数可能非常高查找的时候就需要一层一层往上迭代。这时候很浪费效率这里就提出路径压缩。
路径压缩一般发送在查找根结点会压缩路径上的所有结点挂接到根上。 size_t FindRoot(int x){//找根size_t root x;while (_set[x] 0){x _set[x];}//压缩while (_set[x] 0){size_t parent _set[x];_set[x] root;x parent;}return root;} Gitee:提取代码 相关题目
LCR 116. 省份数量 思路 运用并查集的相关知识
题目给我们一个相邻矩阵遍历一半矩阵就能知道连通的关系。
我们把矩阵中为1的放到一个集合中返回集合的数目 解题时运用lambda表达式调用找根root的函数。
class Solution {
public:int findCircleNum(vectorvectorint isConnected) {int nisConnected[0].size();vectorint _ufs(n,-1);//找根 0 就往上找auto FindRoot[_ufs](int x){int parentx;while(_ufs[parent]0){parent_ufs[parent];}return parent;};//遍历遇到1 并且根不同 就合并 for(int i0;in;i){for(int j0;ji;j){if(isConnected[i][j]1){int root1FindRoot(i);int root2FindRoot(j);if(root1!root2){_ufs[root1]_ufs[root2];_ufs[root2]root1;}}}}int count 0;for(auto x:_ufs){if(x0)count;}return count;}
};
