并查集算法（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 算法的通用思想，值得一学。
不过，如果我们考虑一个特定的图结构，即并查集（Union-Find）在某些情况下可以用于检测图中的环（尽管这通常用于检测有向图中的环，特别是涉及强连通分量时），但在无向图中，我们可以利用它来检测一个特殊的图...讯飞星火： 我们可以使用深度优先搜索（DFS）算法来判断一个无向图是否包含环路。在遍历过程中，如果我们遇到一个已经在当前路径中的节点，那么就说明存在环路。...最后，在main函数中，我们创建了一个示例图并测试了IsCyclic函数。 360智脑： 要在O(V)时间内检测无向图中的环，我们可以使用深度优先搜索（DFS）并记录每个节点的状态。...请注意，这段代码的时间复杂度是O(V+E)，这是在一般无向图上检测环路的常见复杂度。 chatgpt： 可以使用深度优先搜索（DFS）算法来判断无向图是否包含环路。...混元： 要判断一个无向图是否包含环路，并且要求算法的时间复杂度在O(V)数量级，我们可以使用并查集（Union-Find）数据结构。
然后，我们实现了find和union函数，这两个函数是并查集算法的一部分，用于检测图中是否存在环。...但是，如果我们已经有了一个最小生成树，并且只是添加了一个新的节点和一些边，那么我们可以利用现有的最小生成树信息来加速更新过程。...接着，它使用Prim算法来更新最小生成树。在这个过程中，我们假设mst切片已经包含了原始的最小生成树，并且我们有足够的空间来添加新的边。...在这个例子中，我们假设图是一个加权无向图，并且通过邻接矩阵来存储图的结构。...使用Union-Find数据结构：如果你使用Union-Find数据结构来辅助构建最小生成树，添加新边后，你可以将其加入到边的集合中，并使用Union-Find来检查是否形成环。
判断这种「等价关系」非常实用，比如说编译器判断同一个变量的不同引用，比如社交网络中的朋友圈计算等等。...这样，你应该大概明白什么是动态连通性了，Union-Find 算法的关键就在于union和connected函数的效率。那么用什么模型来表示这幅图的连通状态呢？用什么数据结构来实现代码呢？...二、基本思路 注意我刚才把「模型」和具体的「数据结构」分开说，这么做是有原因的。因为我们使用森林（若干棵树）来表示图的动态连通性，用数组来具体实现这个森林。 怎么用森林来表示连通性呢？...我们设定树的每个节点有一个指针指向其父节点，如果是根节点的话，这个指针指向自己。...至此，Union-Find 算法就基本完成了。是不是很神奇？竟然可以这样使用数组来模拟出一个森林，如此巧妙的解决这个比较复杂的问题！ 那么这个算法的复杂度是多少呢？
他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。...Union-Find 算法，也就是常说的并查集算法，主要是解决图论中「动态连通性」问题的。 问题介绍 简单说，动态连通性其实可以抽象成给一幅图连线。...这样，你应该大概明白什么是动态连通性了，Union-Find 算法的关键就在于union和connected函数的效率。那么用什么模型来表示这幅图的连通状态呢？用什么数据结构来实现代码呢？...二、基本思路 注意我刚才把「模型」和具体的「数据结构」分开说，这么做是有原因的。因为我们使用森林（若干棵树）来表示图的动态连通性，用数组来具体实现这个森林。 怎么用森林来表示连通性呢？...我们设定树的每个节点有一个指针指向其父节点，如果是根节点的话，这个指针指向自己。
这样，你应该大概明白什么是动态连通性了，Union-Find 算法的关键就在于union和connected函数的效率。那么用什么模型来表示这幅图的连通状态呢？用什么数据结构来实现代码呢？...二、基本思路 注意我刚才把「模型」和具体的「数据结构」分开说，这么做是有原因的。因为我们使用森林（若干棵树）来表示图的动态连通性，用数组来具体实现这个森林。 怎么用森林来表示连通性呢？...我们设定树的每个节点有一个指针指向其父节点，如果是根节点的话，这个指针指向自己。...竟然可以这样使用数组来模拟出一个森林，如此巧妙的解决这个比较复杂的问题！ 那么这个算法的复杂度是多少呢？...算法的复杂度可以这样分析：构造函数初始化数据结构需要 O(N) 的时间和空间复杂度；连通两个节点union、判断两个节点的连通性connected、计算连通分量count所需的时间复杂度均为 O(1)
容易想到，一幅图可以有很多不同的生成树，比如下面这幅图，红色的边就组成了两棵不同的生成树： 对于加权图，每条边都有权重，所以每棵生成树都有一个权重和。...PS：一般来说，我们都是在无向加权图中计算最小生成树的，所以使用最小生成树算法的现实场景中，图的边权重一般代表成本、距离这样的标量。...那么说到连通性，相信老读者应该可以想到 Union-Find 并查集算法，用来高效处理图中联通分量的问题。...这样，最后mst集合中的边就形成了最小生成树，下面我们看两道例题来运用一下 Kruskal 算法。...：每个坐标点是一个二元组，那么按理说应该用五元组表示一条带权重的边，但这样的话不便执行 Union-Find 算法；所以我们用 points 数组中的索引代表每个坐标点，这样就可以直接复用之前的 Kruskal
CONNECTED-COMPONENTS 算法是一种找出图中所有连通分量的算法。 我们可以使用深度优先搜索（DFS）来实现这个算法。...在实现连通分量算法，如KRUSKAL或DFS时，通常会使用一个集合数据结构来跟踪每个顶点所属的连通分量。...并查集是一种数据结构，用于处理一些不交集的合并及查询问题。有一个联合-查找算法（Union-Find Algorithm）定义了两个用于此数据结构的操作： 1. Find：确定元素属于哪个集合。...在Go语言中，可以使用并查集（Union-Find）数据结构来实现这一功能。...现在我们来证明题目中的结论。使用 UNION-FIND 算法处理图的边时，我们会遍历每一条边，将边的两个顶点所在的集合进行合并。最终，两个顶点在同一个连通分量中当且仅当它们在同一个集合中。
关于并查集的题目不少，官方给的数据是 30 道（截止 2020-02-20），但是有一些题目虽然官方没有贴并查集标签，但是使用并查集来说确非常简单。...等式方程的可满足性 看完这里的内容，建议拿上面的题目练下手，检测一下学习成果。 概述 并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。...有一个联合-查找算法（Union-find Algorithm）定义了两个用于此数据结构的操作： Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。...由于支持这两种操作，一个不相交集也常被称为联合-查找数据结构（Union-find Data Structure）或合并-查找集合（Merge-find Set）。...如图有两个司令： ? 我们将其合并为一个联通域，最简单的方式就是直接将其中一个司令指向另外一个即可： ?
使用深度优先搜索查找图中路径： 只需很简单的修改深度优先遍历算法即可实现查找路径。添加一个实例变量edgeTo[]数组用来返回从每个与s相通的顶点返回s顶点的路径。...使用深度优先搜索找到图中所有的连通分量： 使用深度优先算法求解连通分量，递归第一次调用的参数是顶点0，它会标记所有与0连通的顶点。...然后构造函数中的for循环会查找每个没有被标记的顶点并递归调用dfs()来标记和它相邻的所有顶点。 添加了一个id[]数组，同一个连通分量中的顶点的id[]值相同。...marked[w]) dfs(G,w); } 深度优先遍历的预处理使用的时间和空间与V+E成正比且可以在常数时间内处理图的连通性查询。...更重要的是union-find算法是一种动态算法（我们在任何时候都能用接近常数的时间检查两个顶点是否连通，甚至在添加一条边的时候），但深度优先算法必须对图进行预处理。
“根”的数量就足够了 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[..
用 |V|、|E| 和 k 来表示答案，我们可以说： • FIND-SET 至少被调用 2|E| 次（在没有优化的情况下）。 • UNION 被调用 |E| 次。...对于一个有k个连通分量的无向图G=(V, E)，我们可以这样分析： 1. FIND-SET的调用次数：在最坏情况下，每个顶点都需要调用一次FIND-SET来确定它所属的连通分量。...（Union-Find）数据结构来进行连通分量的计算。...混元： 在无向图中，使用并查集（UNION-FIND）算法处理连通分量问题时，FIND-SET 和 UNION 操作的次数与图的边数和连通分量的数量有关。下面我们来分析这两种操作需要的调用次数。...Go 语言代码示例 以下是一个简单的 Go 语言实现，展示了如何使用并查集来计算无向图的连通分量数量： package main import ( "fmt" ) type UnionFind
一 概述 并查集（Disjoint set或者Union-find set）是一种树型的数据结构，经常使用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。...有一个联合-查找算法（union-find algorithm）定义了两个操作用于此数据结构： Find：确定元素属于哪一个子集。它能够被用来确定两个元素是否属于同一子集。...有了这些方法，很多经典的划分问题能够被解决。 为了更加精确的定义这些方法，须要定义怎样表示集合。 一种经常使用的策略是为每一个集合选定一个固定的元素，称为代表。以表示整个集合。 接着。...但在非常多情况下，我们一般选择两个集合之前代表中的一个作为新的代表。 三 不相交集合森林（有根树表示集合） 不相交集合能够用链表实现。可是还有一种更快的方法—–有根树表示集合。...六 应用 并查集常作为还有一种复杂的数据结构或者算法的存储结构。常见的应用有：求无向图的连通分量个数，近期公共祖先（LCA），带限制的作业排序，实现Kruskar算法求最小生成树等。
在 Go 语言中，我们可以使用 map 来存储每个顶点的连通分量标签，并用一个集合（可以用 map 模拟）来存储每个连通分量的顶点。...为了简化，我假设所有边都已处理，并在最后输出了所有连通分 讯飞星火： 首先，我们需要定义一个无向图的数据结构，然后根据给定的边来构建这个图。...智谱清言： 在处理无向图的连通分量时，常用的算法是深度优先搜索（DFS）或并查集（Union-Find）。这里，我们将使用DFS算法来找出连通分量。 首先，我们需要创建一个顶点的邻接表来表示图。...我们可以使用并查集（Union-Find）数据结构来高效地完成这个任务。下面是一个使用Go语言实现的示例代码，它将根据给定的边的处理顺序来更新连通分量。...在这个例子中，我们将使用并查集（Union-Find）数据结构来实现这个算法。 1. 初始化并查集：每个顶点都是一个单独的集合。 2.
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
实时音视频
云直播
