【C++高阶数据结构】并查集-创新互联
💙系列文章💙🏆个人主页:企鹅不叫的博客
创新互联建站专业为企业提供城子河网站建设、城子河做网站、城子河网站设计、城子河网站制作等企业网站建设、网页设计与制作、城子河企业网站模板建站服务,十年城子河做网站经验,不只是建网站,更提供有价值的思路和整体网络服务。 🌈专栏
- C语言初阶和进阶
- C项目
- Leetcode刷题
- 初阶数据结构与算法
- C++初阶和进阶
- 《深入理解计算机操作系统》
- 《高质量C/C++编程》
- Linux
⭐️ 博主码云gitee链接:代码仓库地址
⚡若有帮助可以【关注+点赞+收藏】,大家一起进步!
文章目录
- 💙系列文章💙
- 💎一、概念
- 💎二、实现
- 🏆1.框架
- 🏆2.查找元素属于哪个集合
- 压缩路径
- 🏆3.合并两个集合
- 🏆4.判断两个元素是否在同一个集合当中
- 🏆5.统计集合个数
- 💎三、练习
- 🏆1.剑指 Offer II 116. 省份数量
- 🏆2.990. 等式方程的可满足性
💎一、概念
并查集是多个独立集合的合集,用于表示数据之间的关系,并查集中的每一个集合是用多叉树来表示的。
💎二、实现 🏆1.框架举例:现在有十个元素,每个元素的值都初始化为-1
现在将0,3,4这三个元素构成一个集合,我们让0为根,将根放到3和4下标对应的元素上,同时将3和4原本对应的元素加给0下标对应的元素
同理将2,5,7,8和1,6,9构成一个集合,默认2和1为根
同理将0集合和1集合合并,默认0是根
总结:
- 数组的下标对应集合中元素的编号
- 数组中如果为负数,负号代表根,数字的绝对值代表该集合中元素个数
- 数组中如果为非负数,代表该元素双亲在数组中的下标
🏆2.查找元素属于哪个集合底层使用vector实现,并且全部初始化为-1
class UnionFindSet {public: UnionFindSet(int sz) :_ufs(sz, -1) {} private: vector
_ufs; };
压缩路径
- 当元素对应的下标对应的内容为正数时(也就是该元素不为根),我们需要更新该下标,也就是index=_ufs[index],让自己成为双亲
- 继续判断,如果对应内容为负数,说明该下标是根,直接返回
int FindRoot(int x){while (_ufs[x] >= 0) {//更新亲人 x = _ufs[x]; } return x; }
🏆3.合并两个集合并查集的访问是依靠数组下标实现的随机访问,时间复杂度为
O(1)
,只有数据样本量极大的时候,可以考虑路劲压缩//查找元素属于哪个集合 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; }
🏆4.判断两个元素是否在同一个集合当中
- 找到两个集合对应的根
- 如果两个根相等说明两个集合相等,如果两个根不相等则让其中一个根归并到一个根的下面,更新新的双亲的内容和被并入的根的内容
void Union(int x, int y) {int root1 = FindRoot(x); int root2 = FindRoot(y); if (root1 != root2) {_ufs[root1] += _ufs[root2]; _ufs[root2] = root1; } }
🏆5.统计集合个数如果两个集合根相等说明在同一个集合当中
bool isUnion(int x, int y) {return FindRoot(x) == FindRoot(y); }
💎三、练习 🏆1.剑指 Offer II 116. 省份数量遍历一遍数组,统计内容为负数的下标的个数,即统计了集合个数
int size() {int count = 0; for (auto e : _ufs) { if (e< 0) { ++count; } } return count; }
🏆2.990. 等式方程的可满足性传送门
思路:遍历所有元素,将相关联的数放到同一个集合当中,最后统计集合数量即可
class Solution {public: int FindRoot(const vector
& v, int x){ while(v[x] >0){ x = v[x]; } return x; } int findCircleNum(vector >& isConnected) { vector v(isConnected.size(), -1); for(int i = 0; i< isConnected.size(); ++i){ for(int j = 0; j< isConnected[0].size(); ++j){ if(isConnected[i][j] == 1){//1表示该元素在同一个元素中 int root1 = FindRoot(v, i); int root2 = FindRoot(v, j); if(root1!=root2){ v[root1] += v[root2]; v[root2] = root1; } } } } int count = 0; for(auto e : v){ if(e< 0){ ++count; } } return count; } };
传送门
思路:如果两个字符相等,则放入同一个集合之中。
如果两个字符不相等,它们应当在不同的集合中,此时查找它们所在集合的根,如果相同则说明这两个字符在同一个集合中,返回false。class Solution {public: int FindRoot(const vector
& v, int x){while(v[x] >= 0){ x = v[x]; } return x; } bool equationsPossible(vector & equations){vector v(26, -1); //第一遍遍历,将相同的值放到同一个集合当中 for(auto& e : equations){if(e[1] == '='){ int root1 = FindRoot(v, e[0]-'a'); int root2 = FindRoot(v, e[3]-'a'); if(root1 != root2){ v[root1]+=v[root2]; v[root2] = root1; } } } //第二遍遍历,讲不同的值比较,如果相同说明悖论了,返回false for(auto& e : equations){if(e[1] == '!'){ int root1 = FindRoot(v, e[0]-'a'); int root2 = FindRoot(v, e[3]-'a'); if(root1 == root2){ return false; } } } return true; } };
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
分享题目:【C++高阶数据结构】并查集-创新互联
分享网址:http://myzitong.com/article/deojgc.html