C/C++实现并查集disjoint_set的模板(带路径压缩优化) 实现一个百万级推送服务,除了它,还有谁 “健康守护者”——STM32标准库和HAL库的比较 程序员被公司辞退12天后,前领导要求回公司讲清代码,结果懵了 RTTR实现C++反射(1)集成rttr库 lotus node 远程运行 CCF历年4,5题收录 N卡 RTX3070/RTX3080/RTX3090挖矿算力推测 最高算力86MH 理论+实验:MySQL索引、事物与存储引擎 PostgreSQL JOIN 多表查询 TP框架实现Excel批量导入数据库数据 MySQL中的列转行 这次是真拯救了我,MySQL索引优化,explain讲得非常清楚了 Oracle快速入门(PLSQL编程) MySQL字符串拼接、截取 MySQL事务管理及存储引擎 《浪姐》万茜点赞宁静、郁可唯黑贴坐实?盗号者和程序员是背锅侠 程序员被公司辞退12天后,前领导要求回公司讲清代码,结果懵了 易语言大漠多线程foobar在游戏多窗口中时时显示输出信息 非科班,自学两年,复盘两个月,侥幸拿到头条、阿里offer 2020年全国数学建模大赛B题源代码以及模型的建立 (2) 2020年数学建模-校园供水系统智能管理 windows破解锁屏密码(亲测有效:再也不怕别人锁屏防你啦!) 清华大佬力荐的JVM学习路线+实战笔记+阿里真题,嚼碎吃透吊打面试官 打造多模块+高可用+高扩展Spring Cloud版分布式电商项目源码分享 Python爬虫入门教程 89-100 定个小目标,先用Python爬个一亿B站用户 五大分布式事务,你了解多少? 2020-09-12 九大核心专题,630页内容,熬夜23天吃透,我收割了3个大厂offer 防抖节流 防抖和节流 函数节流 debounce throttle 每天补充一点 一些零碎的小知识点 JavaScript作用域和作用域链知多少 01-jquery概述 简单概述JSONP原理 02-$符号-jquery与js相互转换 遇见 vue.js --------阿文的vue.js学习笔记(2)----- 基本使用 全国鞋服行业首个5G专项应用落地柒牌 自动搬运作业提升效率150% 大数据系统提高生产效率超10% [网络安全自学篇] 九十四.《Windows黑客编程技术详解》之提权技术(令牌权限提升和Bypass UAC) 鸿蒙OS 2.0 开源蹭热浅读 蚂蚁三面滑铁卢!遭分布式截胡,靠这些笔记潜修30天,挺进京东 【高并发】Redis如何助力高并发秒杀系统,看完这篇我彻底懂了!! K8s概述:几种集群方案的对比 Linux到底该怎么学?RHCA架构师整理了300页学习笔记 到了2020年,技术水平到底需要达到怎样的程度才能成为顶级的阿里P8架构师 Linux怎么学?一张思维导图带你深入Linux核心原理 金九银十首战告捷!凭借这份Alibaba爆款“面试宝典”成功斩获美团Offer 大数据杀熟:我投之以元宝,它报之以砍刀! “物联网加持”下的社区长啥样儿? 潘云鹤院士:大数据智能是人工智能2.0的核心组成部分 防小孩和老人走失,定位精度达1厘米?上海社区为先进物联网产品提供落地场景
您的位置:首页 >计算机基础 >

C/C++实现并查集disjoint_set的模板(带路径压缩优化)

并查集没有固定的写法,其可以由个人写法习惯或具体使用环境的不同而不同,意会此模板再内化自用即可。 B站推荐学习视频

//开始前必须初始化根节点数组parent和层数数组rankfor(int i=0;i<节点数;++i){parent[i]=-1;//或parent[i]=i;rank[i]=0;}//实现并查集首先要实现查找根节点功能//为了便于表达,写成函数int find_root(int x){int x_root=x;//如果不是用-1初始化parent这句不用写while(parent[x_root]!=-1/*如果不是用-1初始化parent改为parent[x_root]!=x_root*/){x_root=parent[x_root];}return x_root;}//实现并查集需要实现合并两个点到一个集合的功能//为了便于描述,写成函数,返回1合并成功,返回0合并失败int union_vertices(int x,int y){int x_root=find_root(x);int y_root=find_root(y);if(x_root==y_root){//根节点相同,两个点在一个集合,合并出现环,不能合并return 0;}else {//根节点不同,可以合并,以下结论可画图验证//两棵树层数不等时,层数小的树合并到层数大的树上时,//合并后树高度未改变,为本次合并的两棵树中高度较大的树的高度if(rank[x_root]>rank[y_root]){parent[y_root]=x_root;}else if(rank[y_root]>rank[x_root]){parent[x_root]=y_root;}//两颗树层数相同,哪颗树的根节点做合并后的根节点都一样,//结果都是使合并后树的高度增1else {parent[x_root]=y_root;++rank[y_root];}return 1;}}//使用并查集时,只要有一次合并失败,就说明图中有环

郑重声明:本文版权归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们修改或删除,多谢。