★ FEATURED ARTICLE 文章目录并查集理论基础背景原理讲解路径压缩代码模板常见误区模拟过程复杂度分析【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;}
阅读完成 · 觉得有帮助？
