第7讲：并查集-北京尧图网络

目录本节目标1. 并查集原理2. 并查集实现3. 并查集应用省份数量等式方程的可满足性本节目标并查集原理并查集实现并查集应用1. 并查集原理在一些应用问题中需要将n个不同的元素划分成一些不相交的集合。开始时每个元素自成一个单元素集合然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于哪个集合的运算。适合于描述这类问题的抽象数据类型称为并查集union-find set。比如某公司今年校招全国总共招生 10 人西安招 4 人成都招 3 人武汉招 3 人10 个人来自不同的学校起先互不相识每个学生都是一个独立的小团体现给这些学生进行编号{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}给以下数组用来存储该小集体数组中的数字代表该小集体中具有成员的个数。负号下文解释毕业后学生们要去公司上班每个地方的学生自发组织成小分队一起上路于是西安学生小分队s1{0,6,7,8}成都学生小分队s2{1,4,9}武汉学生小分队s3{2,3,5}就相互认识了10 个人形成了三个小团体。假设由三个群主 0、1、2 担任队长负责大家的出行。一趟火车之旅后每个小分队成员就互相熟悉成为了一个朋友圈。从上图可以看出编号 6、7、8 同学属于 0 号小分队该小分队中有 4 人包含队长 0编号为 4 和 9 的同学属于 1 号小分队该小分队有 3 人包含队长 1编号为 3 和 5 的同学属于 2 号小分队该小分队有 3 个人包含队长 2。仔细观察数组中的内容变化可以得出以下结论数组的下标对应集合中元素的编号数组中如果为负数负号代表根数字代表该集合中元素个数数组中如果为非负数代表该元素双亲在数组中的下标在公司工作一段时间后西安小分队中 8 号同学与成都小分队 1 号同学奇迹般地走到了一起两个小圈子的学生相互介绍最后成为了一个小圈子现在 0 集合有 7 个人2 集合有 3 个人总共两个朋友圈。通过以上例子可知并查集一般可以解决以下问题查找元素属于哪个集合沿着数组表示的树形关系一直找到根即树中元素为负数的位置。查看两个元素是否属于同一个集合沿着数组表示的树形关系往上一直找到树的根如果根相同表明在同一个集合否则不在。将两个集合归并成一个集合将两个集合中的元素合并。将一个集合名称改成另一个集合的名称。集合的个数遍历数组数组中元素为负数的个数即为集合的个数。2. 并查集实现classUnionFindSet{public:// 初始时将数组中元素全部设置为-1UnionFindSet(size_t size):_ufs(size,-1){}// 给一个元素的编号找到该元素所在集合的名称intFindRoot(intindex){// 如果数组中存储的是负数找到否则一直继续while(_ufs[index]0){index_ufs[index];}returnindex;}boolUnion(intx1,intx2){introot1FindRoot(x1);introot2FindRoot(x2);// x1已经与x2在同一个集合if(root1root2)returnfalse;// 将两个集合中元素合并_ufs[root1]_ufs[root2];// 将其中一个集合名称改变成另外一个_ufs[root2]root1;returntrue;}// 数组中负数的个数即为集合的个数size_tCount()const{size_t count0;for(autoe:_ufs){if(e0)count;}returncount;}private:vectorint_ufs;};3. 并查集应用LCR 116. 省份数量classSolution{public:intfindCircleNum(vectorvectorintisConnected){// 手动控制并查集vectorintufs(isConnected.size(),-1);// 查找根autofindRoot[ufs](intx){while(ufs[x]0)xufs[x];returnx;};for(size_t i0;iisConnected.size();i){for(size_t j0;jisConnected[i].size();j){if(isConnected[i][j]1){// 合并集合introot1findRoot(i);introot2findRoot(j);if(root1!root2){ufs[root1]ufs[root2];ufs[root2]root1;}}}}intn0;for(autoe:ufs){if(e0)n;}returnn;}};990. 等式方程的可满足性/* 解题思路 1. 将所有两端的字符合并到一个集合中 2. 检测!两端的字符是否在同一个集合中如果在则不满足如果不在则满足 */classSolution{public:boolequationsPossible(vectorstringequations){vectorintufs(26,-1);autofindRoot[ufs](intx){while(ufs[x]0)xufs[x];returnx;};// 第一遍先把相等的值加到一个集合中for(autostr:equations){if(str[1]){introot1findRoot(str[0]-a);introot2findRoot(str[3]-a);if(root1!root2){ufs[root1]ufs[root2];ufs[root2]root1;}}}// 第二遍先检查不相等的字符是否在一个集合中在一起就相悖了// 返回falsefor(autostr:equations){if(str[1]!){introot1findRoot(str[0]-a);introot2findRoot(str[3]-a);if(root1root2){returnfalse;}}}returntrue;}};

第7讲：并查集

相关推荐

Django+Vue宠物商店实战：库存原子扣减、订单状态机与RBAC权限落地

零基础本地部署DeepSeek-R1：Ollama三步跑通与强化学习原理解析

交通标志检测实战：YOLO数据体检与训练避坑指南

更多资讯

多微电网拓扑设计的约束差分进化算法与Matlab实现

破解登记之后的运营难题：qData 数据中台专业版六大能力，接住企业数据资产五个问题

基于SpringBoot+Vue的教师工作量管理系统开发实战

AI面试八股文-16_16-简历相关

【鸿蒙心迹】HarmonyOS学习笔记04：ArkTS变量与类型

AI 选题成主流，计算机专业毕设热门选题：含大数据 / 小程序 / 深度学习 / RAG/Web 系统等方向，可以照着抄

今日更新

智能硬件视频会议集成：从芯片选型到场景落地的全栈实践

FFmpeg音视频处理与5路RTMP推流实战：从原理到118克盒子部署

RK3528+1GB内存如何变身直播节点？硬编解码与六协议实战复盘

本周精选

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？