《代码随想录》刷题打卡day47：图论-part05（并查集）-北京尧图网络

文章目录并查集理论基础背景原理讲解路径压缩代码模板常见误区模拟过程复杂度分析【107.寻找存在的路线】并查集理论基础背景首先要知道并查集可以解决什么问题呢并查集常用来解决连通性问题。大白话就是当我们需要判断两个元素是否在同一个集合里的时候我们就要想到用并查集。并查集主要有两个功能将两个元素添加到一个集合中。判断两个元素在不在同一个集合接下来围绕并查集的这两个功能来展开讲解。原理讲解从代码层面我们如何将两个元素添加到同一个集合中呢。我们可能会想到可以把他放到同一个数组里或者set 或者 map 中这样就表述两个元素在同一个集合。那么问题来了对这些元素分门别类可不止一个集合可能是很多集合成百上千那么要定义这么多个数组吗提出想法那可以定义一个二维数组。但如果我们要判断两个元素是否在同一个集合里的时候我们又能怎么办只能把而二维数组都遍历一遍。而且每当想添加一个元素到某集合的时候依然需要把把二维数组都遍历一遍才知道要放在哪个集合里。这仅仅是一个粗略的思路如果沿着这个思路去实现代码非常复杂因为管理集合还需要很多逻辑。那么我们来换一个思路来看看。我们将三个元素ABC 分别是数字放在同一个集合其实就是将三个元素连通在一起如何连通呢。只需要用一个一维数组来表示即father[A] Bfather[B] C 这样就表述 A 与 B 与 C连通了有向连通图。代码如下// 将vu 这条边加入并查集voidjoin(intu,intv){ufind(u);// 寻找u的根vfind(v);// 寻找v的根if(uv)return;// 如果发现根相同则说明在一个集合不用两个节点相连直接返回father[v]u;}可能会有疑问这样我可以知道 A 连通 B因为 A 是索引下标根据 father[A]的数值就知道 A 连通 B。那怎么知道 B 连通 A呢我们的目的是判断这三个元素是否在同一个集合里知道 A 连通 B 就已经足够了。这里要讲到寻根思路只要 A BC 在同一个根下就是同一个集合。给出A元素就可以通过 father[A] Bfather[B] C找到根为 C。给出B元素就可以通过 father[B] C找到根也为为 C说明 A 和 B 是在同一个集合里。大家会想第一段代码里find函数是如何实现的呢其实就是通过数组下标找到数组元素一层一层寻根过程代码如下// 并查集里寻根的过程intfind(intu){if(ufather[u])returnu;// 如果根就是自己直接返回elsereturnfind(father[u]);// 如果根不是自己就根据数组下标一层一层向下找}如何表示 C 也在同一个元素里呢我们需要 father[C] C即C的根也为C这样就方便表示 ABC 都在同一个集合里了。所以father数组初始化的时候要 father[i] i默认自己指向自己。代码如下// 并查集初始化voidinit(){for(inti0;in;i){father[i]i;}}最后我们如何判断两个元素是否在同一个集合里如果通过 find函数找到两个元素属于同一个根的话那么这两个元素就是同一个集合代码如下// 判断 u 和 v是否找到同一个根boolisSame(intu,intv){ufind(u);vfind(v);returnuv;}路径压缩在实现 find 函数的过程中我们知道通过递归的方式不断获取father数组下标对应的数值最终找到这个集合的根。搜索过程像是一个多叉树中从叶子到根节点的过程如图如果这棵多叉树高度很深的话每次find函数去寻找根的过程就要递归很多次。我们的目的只需要知道这些节点在同一个根下就可以所以对这棵多叉树的构造只需要这样就可以了如图除了根节点其他所有节点都挂载根节点下这样我们在寻根的时候就很快只需要一步如果我们想达到这样的效果就需要路径压缩将非根节点的所有节点直接指向根节点。那么在代码层面如何实现呢我们只需要在递归的过程中让 father[u] 接住递归函数 find(father[u]) 的返回结果。因为 find 函数向上寻找根节点father[u] 表述 u 的父节点那么让 father[u] 直接获取 find函数返回的根节点这样就让节点 u 的父节点变成根节点。代码如下注意看注释路径压缩就一行代码// 并查集里寻根的过程intfind(intu){if(ufather[u])returnu;elsereturnfather[u]find(father[u]);// 路径压缩}以上代码在C中可以用三元表达式来精简一下代码如下intfind(intu){returnufather[u]?u:father[u]find(father[u]);}代码模板那么此时并查集的模板就出来了整体模板C代码如下intn1005;// n根据题目中节点数量而定一般比节点数量大一点就好vectorintfathervectorint(n,0);// C里的一种数组结构// 并查集初始化voidinit(){for(inti0;in;i){father[i]i;}}// 并查集里寻根的过程intfind(intu){returnufather[u]?u:father[u]find(father[u]);// 路径压缩}// 判断 u 和 v是否找到同一个根boolisSame(intu,intv){ufind(u);vfind(v);returnuv;}// 将v-u 这条边加入并查集voidjoin(intu,intv){ufind(u);// 寻找u的根vfind(v);// 寻找v的根if(uv)return;// 如果发现根相同则说明在一个集合不用两个节点相连直接返回father[v]u;}通过模板我们可以知道并查集主要有三个功能。寻找根节点函数find(int u)也就是判断这个节点的祖先节点是哪个将两个节点接入到同一个集合函数join(int u, int v)将两个节点连在同一个根节点上判断两个节点是否在同一个集合函数isSame(int u, int v)就是判断两个节点是不是同一个根节点常见误区这里可能会有疑问模板中的 join 函数里的这段代码ufind(u);// 寻找u的根vfind(v);// 寻找v的根if(uv)return;// 如果发现根相同则说明在一个集合不用两个节点相连直接返回与 isSame 函数的实现是不是重复了如果抽象一下呢代码如下// 判断 u 和 v是否找到同一个根boolisSame(intu,intv){ufind(u);vfind(v);returnuv;}// 将v-u 这条边加入并查集voidjoin(intu,intv){if(isSame(u,v))return;// 如果发现根相同则说明在一个集合不用两个节点相连直接返回father[v]u;}这样写可以吗好像看出去没问题而且代码更精简了。其实这么写是有问题的在join函数中我们需要寻找 u 和 v 的根然后再进行连线在一起而不是直接用 u 和 v 连线在一起。举一个例子join(1,2);join(3,2);此时构成的图是这样的此时问 13是否在同一个集合我们调用join(1, 2); join(3, 2);很明显本意要表示 13是在同一个集合。但我们来看一下代码逻辑当我们调用isSame(1, 3)的时候find(1) 返回的是1find(3)返回的是3。return 1 3返回的是false代码告诉我们 1 和 3 不在同一个集合这明显不符合我们的预期所以问题出在哪里问题出在我们精简的代码上即 join 函数一定要先通过find函数寻根再进行关联。如果find函数是这么实现再来看一下逻辑过程。voidjoin(intu,intv){ufind(u);// 寻找u的根vfind(v);// 寻找v的根if(uv)return;// 如果发现根相同则说明在一个集合不用两个节点相连直接返回father[v]u;}分别将这两对元素加入集合。join(1,2);join(3,2);当执行join(3, 2)的时候会先通过find函数寻找 3的根为32的根为1 第一个join(1, 2)将2的根设置为1所以最后是将1 指向 3。构成的图是这样的因为在join函数里我们有find函数进行寻根的过程这样就保证元素 123在这个有向图里是强连通的。此时我们在调用isSame(1, 3)的时候find(1) 返回的是3find(3) 返回的也是3return 3 3返回的是true即告诉我们元素 1 和元素3 是在同一个集合里的。模拟过程凸显途径合并的过程每一个join都要画图通过以上讲解之后一步一步去画一下并查集内部数据连接方式。1、join(1, 8);2、join(3, 8);join(3, 8)在图中为什么将元素1 连向元素 3 而不是将元素 8 连向元素 3 呢这一点在「常见误区」标题下已经详细讲解了因为在join(int u, int v)函数里要分别对 u 和 v 寻根之后再进行关联。3、join(1, 7);4、join(8, 5);这里8的根是3那么 5 应该指向 8 的根 3这里的原因我们在上面「常见误区」已经讲过了。但为什么图中 8 又直接指向了 3 了呢因为路经压缩了即如下代码在寻找根的过程中会有路径压缩减少下次查询的路径长度。// 并查集里寻根的过程intfind(intu){returnufather[u]?u:father[u]find(father[u]);// 路径压缩}5、join(2, 9);6、join(6, 9);这里为什么是 2 指向了 6因为 9的根为 2所以用2指向6。大家看懂这个有向图后相信应该知道如下函数的返回值了。coutisSame(8,7)endl;coutisSame(7,2)endl;返回值分别如下表示8 和 7 是同一个集合而 7 和 2 不是同一个集合。true false复杂度分析这里对路径压缩版并查集来做分析。空间复杂度 O(n) 申请一个father数组。关于时间复杂度这里做一个简单的分析思路路径压缩后的并查集时间复杂度在O(logn)与O(1)之间且随着查询或者合并操作的增加时间复杂度会越来越趋于O(1)。了解到这个程度对于求职面试来说就够了。在第一次查询的时候相当于是n叉树上从叶子节点到根节点的查询过程时间复杂度是logn但路径压缩后后面的查询操作都是O(1)而 join 函数和 isSame函数里涉及的查询操作也是一样的过程。【107.寻找存在的路线】思路为什么说这道题目是并查集基础题目题目中各个点是双向图链接那么判断一个顶点到另一个顶点有没有有效路径其实就是看这两个顶点是否在同一个集合里。如何算是同一个集合呢有边连在一起就算是一个集合。此时我们就可以直接套用并查集模板。使用 join(int u, int v)将每条边加入到并查集。最后 isSame(int u, int v) 判断是否是同一个根就可以了。先给出并查集C模板如下只要修改n的大小即可。intn1005;// n根据题目中节点数量而定一般比节点数量大一点就好vectorintfathervectorint(n,0);// C里的一种数组结构// 并查集初始化voidinit(){for(inti0;in;i){father[i]i;}}// 并查集里寻根的过程intfind(intu){returnufather[u]?u:father[u]find(father[u]);// 路径压缩}// 判断 u 和 v是否找到同一个根boolisSame(intu,intv){ufind(u);vfind(v);returnuv;}// 将v-u 这条边加入并查集voidjoin(intu,intv){ufind(u);// 寻找u的根vfind(v);// 寻找v的根if(uv)return;// 如果发现根相同则说明在一个集合不用两个节点相连直接返回father[v]u;}并查集主要有三个功能寻找根节点函数find(int u)也就是判断这个节点的祖先节点是哪个将两个节点接入到同一个集合函数join(int u, int v)将两个节点连在同一个根节点上判断两个节点是否在同一个集合函数isSame(int u, int v)就是判断两个节点是不是同一个根节点#includeiostream#includevectorusingnamespacestd;intn;// 节点数量vectorintfathervectorint(101,0);// 按照节点大小定义数组大小// 并查集初始化voidinit(){for(inti1;in;i){father[i]i;}}// 并查集里寻根的过程intfind(intu){returnufather[u]?u:father[u]find(father[u]);}// 判断u和v是否找到同一个根boolisSame(intu,intv){ufind(u);vfind(v);returnuv;}// 将v-u这条边加入并查集voidjoin(intu,intv){ufind(u);// 寻找u的根vfind(v);// 寻找v的根if(uv)return;// 如果发现根相同则说明在同一个集合不用两个节点相连直接返回father[v]u;}intmain(){intm,s,t,source,destination;cinnm;init();while(m--){cinst;join(s,t);}cinsourcedestination;if(isSame(source,destination))cout1endl;elsecout0endl;return0;}

《代码随想录》刷题打卡day47：图论-part05（并查集）

相关推荐

Channels 2.0.1 发布详解：异步 WebSocket 消费者、Origin 校验中间件与 URLRouter 路由修复

Orchard Core 2.1.8 稳定性修复版本深度解析：站点设置预加载、PDF 索引与 GraphQL 排序

西门子工业软件代理商怎么选？实施与技术服务完整指南

更多资讯

MLA 在极长上下文下的显存带宽突围：128K 场景下的算子访存深度解析

ponytail插件开发实战：从零搭建聚合层工作流与性能调优

基于语义缓存（Semantic Cache）的大模型降本：利用 Milvus 过滤 20% 高频重复请求

半桥驱动芯片原理与实战：自举升压、死区时间与MOS管可靠驱动

ESP32云端开发新姿势：ESP-Mosaico与烧录工具v3.6.5实操指南

故障诊断 Agent 的上下文管理：如何在有限 Context 窗口内高效组装指标、日志与事件

今日更新

基于sEMG与IMU的手语手势识别：从数据采集到实时部署避坑指南

装配车间MES落地指南：SimpleMES工单流转、BOM与齐套检查实战

AI获客怎样减少重复线索？意客AI的原文复用与版本筛选

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

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

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

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

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