并查集算法（union-find） 接受了大家的反馈，决定将之前的图论告一段落，我在基础的数据结构和数据处理的场景下找一些好玩的算法来写写。...他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。 这题最后让我们求得集合数。...但是拍脑袋想，我们要遍历 N 次每个集合，真的是一个超级耗时的办法。 那么有什么更加优美的数据结构来解决这类问题呢？其实就是今天要讲的并查集（union-find）。 并查集是什么？...并查集是用来管理元素分组状况的数据结构。并查集可以高效地执行如下操作。不过需要注意并查集虽然可以进行合并操作，但是无法进行分割操作。...类似于二叉树，我们同样的也可以通过一维数组来实现，并查集也是如此。
在线学习网站： https://labuladong.github.io/algo/ 读完本文，可以去力扣解决如下题目： 323. 无向图中的连通分量数目（中等） 130....这样，你应该大概明白什么是动态连通性了，Union-Find 算法的关键就在于union和connected函数的效率。那么用什么模型来表示这幅图的连通状态呢？用什么数据结构来实现代码呢？...二、基本思路 注意我刚才把「模型」和具体的「数据结构」分开说，这么做是有原因的。因为我们使用森林（若干棵树）来表示图的动态连通性，用数组来具体实现这个森林。 怎么用森林来表示连通性呢？...竟然可以这样使用数组来模拟出一个森林，如此巧妙的解决这个比较复杂的问题！ 那么这个算法的复杂度是多少呢？...但这个问题也可以用 Union-Find 算法解决，虽然实现复杂一些，甚至效率也略低，但这是使用 Union-Find 算法的通用思想，值得一学。
他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。...Union-Find 算法，也就是常说的并查集算法，主要是解决图论中「动态连通性」问题的。 问题介绍 简单说，动态连通性其实可以抽象成给一幅图连线。...这样，你应该大概明白什么是动态连通性了，Union-Find 算法的关键就在于union和connected函数的效率。那么用什么模型来表示这幅图的连通状态呢？用什么数据结构来实现代码呢？...二、基本思路 注意我刚才把「模型」和具体的「数据结构」分开说，这么做是有原因的。因为我们使用森林（若干棵树）来表示图的动态连通性，用数组来具体实现这个森林。 怎么用森林来表示连通性呢？...我们设定树的每个节点有一个指针指向其父节点，如果是根节点的话，这个指针指向自己。
判断这种「等价关系」非常实用，比如说编译器判断同一个变量的不同引用，比如社交网络中的朋友圈计算等等。...这样，你应该大概明白什么是动态连通性了，Union-Find 算法的关键就在于union和connected函数的效率。那么用什么模型来表示这幅图的连通状态呢？用什么数据结构来实现代码呢？...二、基本思路 注意我刚才把「模型」和具体的「数据结构」分开说，这么做是有原因的。因为我们使用森林（若干棵树）来表示图的动态连通性，用数组来具体实现这个森林。 怎么用森林来表示连通性呢？...我们设定树的每个节点有一个指针指向其父节点，如果是根节点的话，这个指针指向自己。...至此，Union-Find 算法就基本完成了。是不是很神奇？竟然可以这样使用数组来模拟出一个森林，如此巧妙的解决这个比较复杂的问题！ 那么这个算法的复杂度是多少呢？
容易想到，一幅图可以有很多不同的生成树，比如下面这幅图，红色的边就组成了两棵不同的生成树： 对于加权图，每条边都有权重，所以每棵生成树都有一个权重和。...PS：一般来说，我们都是在无向加权图中计算最小生成树的，所以使用最小生成树算法的现实场景中，图的边权重一般代表成本、距离这样的标量。...那么说到连通性，相信老读者应该可以想到 Union-Find 并查集算法，用来高效处理图中联通分量的问题。...这样，最后mst集合中的边就形成了最小生成树，下面我们看两道例题来运用一下 Kruskal 算法。...：每个坐标点是一个二元组，那么按理说应该用五元组表示一条带权重的边，但这样的话不便执行 Union-Find 算法；所以我们用 points 数组中的索引代表每个坐标点，这样就可以直接复用之前的 Kruskal
这样，你应该大概明白什么是动态连通性了，Union-Find 算法的关键就在于union和connected函数的效率。那么用什么模型来表示这幅图的连通状态呢？用什么数据结构来实现代码呢？...二、基本思路 注意我刚才把「模型」和具体的「数据结构」分开说，这么做是有原因的。因为我们使用森林（若干棵树）来表示图的动态连通性，用数组来具体实现这个森林。 怎么用森林来表示连通性呢？...我们设定树的每个节点有一个指针指向其父节点，如果是根节点的话，这个指针指向自己。...竟然可以这样使用数组来模拟出一个森林，如此巧妙的解决这个比较复杂的问题！ 那么这个算法的复杂度是多少呢？...算法的复杂度可以这样分析：构造函数初始化数据结构需要 O(N) 的时间和空间复杂度；连通两个节点union、判断两个节点的连通性connected、计算连通分量count所需的时间复杂度均为 O(1)
使用深度优先搜索查找图中路径： 只需很简单的修改深度优先遍历算法即可实现查找路径。添加一个实例变量edgeTo[]数组用来返回从每个与s相通的顶点返回s顶点的路径。...使用深度优先搜索找到图中所有的连通分量： 使用深度优先算法求解连通分量，递归第一次调用的参数是顶点0，它会标记所有与0连通的顶点。...然后构造函数中的for循环会查找每个没有被标记的顶点并递归调用dfs()来标记和它相邻的所有顶点。 添加了一个id[]数组，同一个连通分量中的顶点的id[]值相同。...marked[w]) dfs(G,w); } 深度优先遍历的预处理使用的时间和空间与V+E成正比且可以在常数时间内处理图的连通性查询。...更重要的是union-find算法是一种动态算法（我们在任何时候都能用接近常数的时间检查两个顶点是否连通，甚至在添加一条边的时候），但深度优先算法必须对图进行预处理。
关于并查集的题目不少，官方给的数据是 30 道（截止 2020-02-20），但是有一些题目虽然官方没有贴并查集标签，但是使用并查集来说确非常简单。...等式方程的可满足性 看完这里的内容，建议拿上面的题目练下手，检测一下学习成果。 概述 并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。...有一个联合-查找算法（Union-find Algorithm）定义了两个用于此数据结构的操作： Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。...由于支持这两种操作，一个不相交集也常被称为联合-查找数据结构（Union-find Data Structure）或合并-查找集合（Merge-find Set）。...如图有两个司令： ? 我们将其合并为一个联通域，最简单的方式就是直接将其中一个司令指向另外一个即可： ?
“根”的数量就足够了 Union-Find中的元素v是否为根可以通过uf.root(v) == v是否为真来判断 基于以上，可以如下实现。...有一个有 N 个顶点和 M 个边的无向图 G，其中第 i 条边连接第 A 顶点和第 B 顶点。连接 G 必须添加的最小边数是多少？ 为了解决这个问题，我们关注连接组件的数量。...这样思考，我们可以看到，通过从两个不同的连通分量中逐一选择顶点并添加连接两个顶点的边，可以将连通分量的数量减少一个。所以答案是（G 的连通分量数）-1。 有几种技术可以在图中找到连通分量的数量。...并查集（Union-Find） Union-Find是将每一组视为一棵树的数据结构，通过两个顶点所属的树的根是否相同来判断两个顶点是否在同一个组中。...在 C++ 的情况下，可以使用 ACL dsu 轻松实现，可以通过包含 atcoder/all 或 atcoder/dsu 来使用。
上一篇：加权无向图的实现 加权无向图----Prim算法实现最小生成树 数据结构： 用一条优先队列将边按照权重从小到大排序 用union-find数据结构来识别会形成环的边 用一条队列来保存最小生成树的所有边...Kruskal算法的计算一个含V个顶点和E条边的连通加权无向图的最小生成树所需空间与E成正比，所需时间与ElogE成正比（最坏情况）。...方法：将边都添加进最小优先权队列中，每次从中取出最小的边，检查会不会与已经选出的边构成环（使用union-find算法），如果构成环，则弃掉这条边，否则将这条边加入最小生成树队列。...for(Edge e: G.edges()) pq.insert(e);//将所有边添加进优先队列 UF uf = new UF(G.V()); //union-find...pq.isEmpty() && mst.size()<G.V()-1) { Edge e = pq.delMin();//从优先队列得到最小的边 int
判断无向图中是否有环 通过上面的定义可知，无论有向图还是无向图中都存在环，但有向图的环涉及到边的方向，要比无向图复杂。...因此，如果你在面试中被要求写一个算法“判断图中是否有环”，首先就应该和面试官确认，要判断的是有向图还是无向图。本文我们讲解的是无向图中是否有环的判断！...在动手编程之前，我们首先要想清楚如何做，也就是说我们先要能够找到一个用自然语言可以描述的办法，来确定无向图中是否有环。...本文中讲的内容比较多，介绍了三种方法：拓扑排序，DFS和Union-Find Set，每一种方法都可以判断无向图或者有向图。...这种方法的描述如下： 使用拓扑排序可以判断一个无向图中是否存在环，具体步骤如下： 1. 求出图中所有节点的度。 2. 将所有度 <= 1 的节点入队。 3.
无向图的表示 今天的主角是无向图，顾名思义，无向图就是边没有方向的图。每当一个概念拿到程序中，总是需要抽象出一个数据结构来表示这个概念。那么，图怎么表示呢？表示图的这个数据结构叫做邻接表。...同时我们也可以看到，如果要访问与顶点3相邻的顶点，我们势必会先访问到2，然后是5，最后是9。但是对与顶点3来说，和它相邻的任何一个顶点低位都是相同的，但这个先后顺序却是确定的。...所以构造这个图的时候，也就是构造这个邻接表的时候就已经决定了我们操作图中结点时的某些顺序。 对与领接表数组中的元素，本身是一个链表，为了方便操作，我们用一个Bag类来实现这个链表。...edgeTo[2]=1，表示1-2是第一次访问2时经过的边。通过edgeTo这个数组我们就可以还原出一个路径。除此之外，深度优先搜索还可以找出图中的所有连通分量。...广度优先搜索 刚才说到深度优先搜索可以找到两个顶点之间的一个路径，但当两个顶点之间有多个路径的时候，我们需要找出最短的那一条时，深度优先搜索就束手无策了。此刻只能我们广度优先搜索出来亮亮相了。
隐藏与 Union-find 不相关的细节；可以使用整数快速获取与对象相关的信息（数组的下标）；可以使用符号表对对象进行转化。 简化有助于我们理解连通性的本质。...如下图所示，图中共包含 63 个组，其中对象 u 和 对象 v 在同一个集合当中，我们可以找到一条从对象 u 到对象 v 的路径（红色路线）但是我们并不关心这条路劲本身，只关心他们是否联通： ?...Union 命令：将包含两个对象的集合替换为它们的并集。 现在目标就是为 Union-Find 设计一个高效的数据结构： Find 查询和 Union 命令可以混合使用。...的概念来优化 union 函数，我们把每一个数的 id 看做是它的父结点。...与 Quick-Find 算法使用一样的数据结构，但是 id[] 数组具有不同的含义： 大小为 的整型数组 id[] 解释：id[i] 表示 i 的父结点 i 的根结点为 id[id[id[..
一 概述 并查集（Disjoint set或者Union-find set）是一种树型的数据结构，经常使用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。...有一个联合-查找算法（union-find algorithm）定义了两个操作用于此数据结构： Find：确定元素属于哪一个子集。它能够被用来确定两个元素是否属于同一子集。...有了这些方法，很多经典的划分问题能够被解决。 为了更加精确的定义这些方法，须要定义怎样表示集合。 一种经常使用的策略是为每一个集合选定一个固定的元素，称为代表。以表示整个集合。 接着。...但在非常多情况下，我们一般选择两个集合之前代表中的一个作为新的代表。 三 不相交集合森林（有根树表示集合） 不相交集合能够用链表实现。可是还有一种更快的方法—–有根树表示集合。...六 应用 并查集常作为还有一种复杂的数据结构或者算法的存储结构。常见的应用有：求无向图的连通分量个数，近期公共祖先（LCA），带限制的作业排序，实现Kruskar算法求最小生成树等。
并查集可以高效的用来解决连接问题（Connectivity Problem），我们来看下面这样的一张图： ? 可以看到，该图中有很多的点，有些点之间有连接，而有些点之间则没有连接。...那么此时就有一个问题是：这图中任意的两个点是否可能通过一条路径连接起来。对于这个问题，我们使用并查集就可以高效的求解，因为并查集可以非常快地判断网络中节点间的连接状态。...根据这两个操作，我们就可以定义出并查集的接口了，这是因为并查集可以有多种实现方式，这里定义接口来做统一抽象： package tree.unionfind; /** * 并查集接口 * * @author...我们可以使用数组来表示并查集中的数据，数组中存放每个元素所在的集合编号，例如 0 和 1。...然而即便是基于 rank 的优化也无法避免数据量较大的情况下导致树的高度过高的问题，所以我们就得使用路径压缩这种优化方式来解决这个问题。 那么我们要如何进行路径压缩呢？
同时，我们还将探讨如何在前端开发中使用ESLint和VS Code工具来设置和检测圈复杂度。什么是圈复杂度？圈复杂度是由Thomas J....使用循环和迭代替代重复的代码块重复的代码块会增加代码的复杂性和重复性。为了降低圈复杂度，可以使用循环和迭代来替代重复的代码块。...使用适当的数据结构和算法选择适当的数据结构和算法可以帮助降低代码的复杂性和提高性能。例如，使用哈希表可以减少查找操作的复杂度，使用排序算法可以提高搜索和比较的效率。...在VS Code中，可以使用插件如ESLint、CodeMetrics等来检测圈复杂度。安装ESLint插件后，可以在VS Code的设置中配置圈复杂度的阈值，并在编辑器中实时检测代码的圈复杂度。...在前端开发中，使用ESLint和VS Code工具可以帮助我们设置和检测圈复杂度，并及时发现和解决代码中的复杂性问题。通过合理的代码设计和优化，我们可以编写出更简洁、高效和易于维护的代码。
那么，本文依然秉持我们号的风格，只讲「图」最实用的，离我们最近的部分，让你心里对图有个直观的认识，文末我给出了其他经典图论算法，理解本文后应该都可以拿下的。...那你可能会问，我们这个图的模型仅仅是「有向无权图」，不是还有什么加权图，无向图，等等…… 其实，这些更复杂的模型都是基于这个最简单的图衍生出来的。 有向加权图怎么实现？...把上面的技巧合起来，就变成了无向加权图…… 好了，关于图的基本介绍就到这里，现在不管来什么乱七八糟的图，你心里应该都有底了。 下面来看看所有数据结构都逃不过的问题：遍历。...，有可能走了一圈又回到这个节点。...当然，图还会有很多其他的有趣算法，比如 二分图判定，环检测和拓扑排序（编译器循环引用检测就是类似的算法），最小生成树，Dijkstra 最短路径算法 等等，有兴趣的读者可以去看看，本文就到这了。
（Union-find algorithm），均表示相同的数据结构或思想。...并查集是一种用来高效地判断 “动态连通性 ” 的数据结构： 即给定一个无向图，要求判断某两个元素之间是否存在相连的路径（连通），这就是连通问题，也叫 “朋友圈” 问题。...并查集使用 “代表元法” 来表示元素之间的连接关系：将相互连通的元素组成一个子集，并从中选取一个元素作为代表元。...典型例题 · 岛屿数量（二维） 前面我们讲的是一维的连通性问题，那么在二维世界里的连通性问题，并查集还依旧好用吗？...我们看 LeetCode 上的另一道典型例题：LeetCode · 200.[5] LeetCode 例题 这个问题直接上 DFS 广度搜索自然是可以的：遍历二维数组，每找到 1 后使用 DFS 遍历将所有相连的
，以及边两倍次的减少key的值，所以总的时间为 image.png 使用斐波那契堆可以达到VlgV+E Kruskal's算法 核心思想：全局最小的corssing cut边必定属于最小生成树，这个过程不能生成环...，需要追踪两个节点是否已经互相连接了 追踪的数据结构是 Union-Find 结构，包含3个功能，Make-Set:创建一个集合；Find-Set:找到当前元素在那个集合；Union:合并集合 刚开始的时候...T什么都没有 对每个节点v都执行一遍Make-Set 为了找到全局最小的crossing cut，对整个的边通过权值按照递增来排序 按照增序遍历所有的边，如果两个节点u和v属于不同的集合(crossing...cut)，那么可以合并边T=TU{e},然后将这两个集合合并Union(u,v) 延伸阅读 Union-Find数据结构与Ackermann函数 时间分析 image.png 在使用Union-Find...数据结构的基础上能够做到时间为O(ElgE+Eα(V))，假设权重为正整数而且最大值是个常量，那么排序可以达到常量的时间，这个时候，算法所需要的时间就是O(E),整体不Prims算法要好 最快的MST
关于并查集的题目不少，官方给的数据是 30 道（截止 2020-02-20），但是有一些题目虽然官方没有贴并查集标签，但是使用并查集来说确非常简单。...等式方程的可满足性[3] 大家可以学了模板之后去套用一下上面的三道题，做不出来的可以看看我的题解。...如果你对这个算法不是很明白，推荐看一下这篇文章Union-Find 算法详解[4]，讲的非常详细。 你可以把并查集的元素看成部门的人，几个人可以组成一个部门个数。...（图来自 labuladong） 模板 这是一个我经常使用的模板，我会根据具体题目做细小的变化，但是大体是不变的。...self.cnt -= 1 def connected(self, p, q): return self.find(p) == self.find(q) 大家可以根据情况使用不同的模板
领取专属 10元无门槛券
手把手带您无忧上云
