并查集的实现(朴素版)
这是C++算法基础-数据结构专栏的第二十九篇文章,专栏详情请见此处。
由于作者即将参加CSP,所以到比赛结束前将不再发表文章!
引入
并查集是一种可以快速合并查找集合的一种数据结构,这次我们将通过三道题来详细讲解并查集(朴素版、维护并查集大小版和维护到祖宗节点距离版),而这次我们要学习朴素版的并查集。
下面我们就来讲并查集的实现(朴素版)。
定义
并查集是一种用于管理元素所属集合的数据结构,实现为一个森林,其中每棵树表示一个集合,树中的节点表示对应集合中的元素。
过程
例题:合并集合
题目大意:起初一共有
个数,每个数都各自在一个集合中。现在要进行
个操作,操作共两种:将两个数
所在的集合合并;询问两个数
是否在同一个集合中;
操作:合并和查找
并查集,顾名思义,它就是支持两种基本操作的数据结构:并(合并)和查(查找)。它的原理就是用一个数组记录每个节点的祖宗节点,通过对这个数组的更新实现数据之间的联系。刚开始所有节点的根都是它本身。
首先,我们需要实现一个函数find(),用来寻找一个节点的根,方法很简单,只需不断递归,一直访问现在节点的祖宗节点,直到访问到根节点(即该节点的是本身)。
首先是第一个操作:合并。合并时只需要将其中一个节点的根的赋值为另一个节点的根。
第二个操作:查找。查找两个节点是否在同一棵树上,仅仅判断两个节点的find()是否相同即可。
Q:为什么不直接比较
呢?
A:因为在合并时,若有两棵树进行合并,可能中途的节点的
不会被直接连到根上,所以需要不断寻找才能找到最终的根。
优化:路径压缩和按秩合并
接下来我们进行优化,在实现find()函数的过程中,很明显,一路上经过的点都在这个集合中,为了加快后续查询,我们可以将其直接连到根上。这一优化我们称为路径压缩。这个优化大大的降低了时间复杂度。
有时题目需要保留原有的树的结构,这时我们就不能采用路径压缩了。合并时,我们可以在每棵树的根上记录树的层数,把层数小的树合并到层数大的树,很明显,这样做可以减少合并后树的层数,这叫做按秩合并。
由于路径压缩的优化程度比按秩合并要大,所以我们一般仅仅采用路径压缩就足够了。课程中也只是提到了按秩合并,并没有讲解,所以在代码中我们也不采用按秩合并。
代码
下面给出朴素版并查集的实现代码:
int p[N];int find(int x){if(p[x]!=x) p[x]=find(p[x]);return p[x];
}for(int i=1;i<=n;i++) p[i]=i;p[find(a)]=find(b);
代码解释
第一行是存储每个节点的祖宗节点的数组;find()函数的作用是寻找根节点;for循环中的内容的作用是初始化;最后一行的作用是合并。
上一篇-Trie树之最大异或对问题 C++算法基础专栏文章 下一篇-并查集的实现(维护并查集大小版版)
每周一更新一篇文章,内容一般是自己总结的经验或是在其他网站上整理的优质内容
点个赞,关注一下呗~
相关文章:
并查集的实现(朴素版)
这是C算法基础-数据结构专栏的第二十九篇文章,专栏详情请见此处。 由于作者即将参加CSP,所以到比赛结束前将不再发表文章! 引入 并查集是一种可以快速合并查找集合的一种数据结构,这次我们将通过三道题来详细讲解并查集ÿ…...
WPF 为button动态设置不同的模板
有时候需要动态的设置一些按钮的状态模板。使一个button显示不同的内容,比如Button未点击安装显示: 安装后显示: 可以通过设置button的content,通过content来设置不同的模板来实现功能,以下是代码: MainWi…...
【C++贪心 DFS】2673. 使二叉树所有路径值相等的最小代价|1917
本文涉及知识点 C贪心 反证法 决策包容性 CDFS LeetCode2673. 使二叉树所有路径值相等的最小代价 给你一个整数 n 表示一棵 满二叉树 里面节点的数目,节点编号从 1 到 n 。根节点编号为 1 ,树中每个非叶子节点 i 都有两个孩子,分别是左孩子…...
虚幻引擎GAS入门学习笔记(一)
虚幻引擎GAS入门(一) Gameplay Ability System(GAS) 是一个模块化且强大的框架,用于管理虚幻引擎中的游戏玩法逻辑。它的核心组成部分包括 Gameplay Ability(定义和执行能力)、Gameplay Effect(应用和管理…...
Excel:vba实现合并工作表(表头相同)
这个代码应该也适用于一些表头相同的工作表的汇总,只需要修改想要遍历的表,适用于处理大量表头相同的表的合并 这里的汇总合并表 total 是我事先创建的,我觉得比用vba代码创建要容易一下,如果不事先创建汇总表就用下面的代码&…...
Redis:分布式 - 主从复制
Redis:分布式 - 主从复制 概念配置主从模式info replicationslave-read-onlytcp-nodelay 命令slaveof 主从结构一主一从一主多从 主从复制流程数据同步命令全量同步部分同步实时同步 节点晋升 概念 Redis的最佳应用,还是要在分布式系统中。对于非分布式…...
el-date-picker设置只有某些日期可选
示例图: <el-date-pickerv-model"topFormObj.upTime"type"date"value-format"timestamp"format"dd/MM/yyyy":picker-options"pickerOptions" /> 固定限制每周的周末周三不可选 data() {return {pickerOp…...
java数据库操作-cnblog
创建lib目录,填入jar包 选择 libraries添加lib目录 package nb;import java.sql.Connection; import java.sql.DriverManager; import java.sql.SQLException;public class JDBCtest {private static final String url "jdbc:mysql://localhost:3306/test?c…...
HCIP-HarmonyOS Application Developer 习题(九)
(多选) 1、HarmonyOS多窗口交互能力提供了以下哪几种交互方式? A. 全局消息通知 B.平行视界 C.悬浮窗 D.分屏 答案:BCD 分析:系统提供了悬浮窗、分屏、平行视界三种多窗口交互,为用户在大屏幕设备上的多任务并行、便捷的临时任务…...
redis集成到spring boot中使用
(一)添加依赖 redis服务器在官网中公开了自己使用的协议--RESP,所以我们可以使用这个协议来访问redis服务器,但是如果我们要自己实现库,那肯定是非常麻烦的,所以我们可以使用网上的库,我们直接调…...
Spring Boot、Spring MVC和Spring有什么区别
人要长大,就要学会不断接受事件的变化 —— 24.10.14 spring是一个IOC容器,用来管理Bean,使用依赖注入实现控制反转,可以很方便的整合各种框架,提供AOP机制弥补OOP的代码重复问题、更方便将不同类不同方法中的共同处理…...
Flip动画
前言 最近在做复图标库功能时,感觉这个功能在使用上有些“生硬”。如随机删除一个图标,后面的元素在视觉上是“瞬间移动”过来补位的。想着做个小优化,简单加个动画效果吧。 看起来确实“花里胡哨”了,实现也很简单, …...
Java通过RAG构建专属知识问答机器人_超详细
RAG:融合检索与生成的文本精准生成技术 检索增强生成(RAG)是一种技术,它通过结合检索模型和生成模型来提高文本生成的准确性。具体来说,RAG首先利用检索模型从私有或专有的数据源中搜索相关信息,然后将这些…...
2.1 使用点对点信道的数据链路层
欢迎大家订阅【计算机网络】学习专栏,开启你的计算机网络学习之旅! 文章目录 前言1 通信信道类型2 数据链路3 帧4 透明传输5 差错检测 前言 在计算机网络通信中,数据链路层起着关键作用。它为直接相连的网络设备之间提供可靠的数据传输服务。…...
台式机来电自启动设置
在前司时,由于有些工作需要用到台式机,且一到节假日或者突然停电等情况,电脑每次都需要自己手动开机,后来研究了一下,发现可以在BIOS里面更改设置,从而变成关机的情况下,只要来电就能自动开机&a…...
【最新华为OD机试E卷-支持在线评测】考勤信息(100分)多语言题解-(Python/C/JavaScript/Java/Cpp)
🍭 大家好这里是春秋招笔试突围 ,一枚热爱算法的程序员 💻 ACM金牌🏅️团队 | 大厂实习经历 | 多年算法竞赛经历 ✨ 本系列打算持续跟新华为OD-E/D卷的多语言AC题解 🧩 大部分包含 Python / C / Javascript / Java / Cpp 多语言代码 👏 感谢大家的订阅➕ 和 喜欢�…...
netdata保姆级面板介绍
netdata保姆级面板介绍 基本介绍部署流程下载安装指令选择设置KSM为什么要启用 KSM?如何启用 KSM?验证 KSM 是否启用注意事项 检查端口启动状态 netdata和grafana的区别NetdataGrafananetdata各指标介绍总览system overview栏仪表盘1. CPU2. Load3. Disk…...
苹果最新论文:LLM只是复杂的模式匹配 而不是真正的逻辑推理
大语言模型真的可以推理吗?LLM 都是“参数匹配大师”?苹果研究员质疑 LLM 推理能力,称其“不堪一击”!苹果的研究员 Mehrdad Farajtabar 等人最近发表了一篇论文,对大型语言模型 (LLM) 的推理能…...
Python知识点:基于Python工具,如何使用Scikit-Image进行图像处理与分析
开篇,先说一个好消息,截止到2025年1月1日前,翻到文末找到我,赠送定制版的开题报告和任务书,先到先得!过期不候! 基于Python的Scikit-Image图像处理与分析指南 在Python的科学计算生态系统中&am…...
MongoDB初学者入门教学:与MySQL的对比理解
🏝️ 博主介绍 大家好,我是一个搬砖的农民工,很高兴认识大家 😊 ~ 👨🎓 个人介绍:本人是一名后端Java开发工程师,坐标北京 ~ 🎉 感谢关注 📖 一起学习 &…...
SpringBoot-17-MyBatis动态SQL标签之常用标签
文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...
深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...
stm32G473的flash模式是单bank还是双bank?
今天突然有人stm32G473的flash模式是单bank还是双bank?由于时间太久,我真忘记了。搜搜发现,还真有人和我一样。见下面的链接:https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...
智慧医疗能源事业线深度画像分析(上)
引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...
基于服务器使用 apt 安装、配置 Nginx
🧾 一、查看可安装的 Nginx 版本 首先,你可以运行以下命令查看可用版本: apt-cache madison nginx-core输出示例: nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...
【HTML-16】深入理解HTML中的块元素与行内元素
HTML元素根据其显示特性可以分为两大类:块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...
【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...
学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...
Android第十三次面试总结(四大 组件基础)
Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成,用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机: onCreate() 调用时机:Activity 首次创建时调用。…...
FFmpeg:Windows系统小白安装及其使用
一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】,注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录(即exe所在文件夹)加入系统变量…...
