首页
学习
活动
专区
工具
TVP
发布
您找到你想要的搜索结果了吗?
是的
没有找到

是一种用互质的集合对数据进行分类管理的数据结构。 主要实现了两个功能:合并与查询 我们用一个数组fa[i]来表示第i个元素所在集合的根节点。 根节点的父节点指向它自身。...对于题目 DSL_1_A 来说,题目要求实现一个简单的,代码如下: #include #include using namespace std; #define...]==x) return x; int t = find_root(fa[x]); fa[x] = t; return t; } 按秩合并 的按秩合并说白了就是把高度矮的树合并到高度高的树上...只有使用了路径压缩+按秩合并的,时间复杂度才会低于O(logn) 我们需要使用一个数组Rank[i]来存储第i个节点作为根节点时,它的树的高度。...带权 带权就是在的树的连边上附上权值。 带权的合并,需要把权值也加起来。 其实理解并不困难,就是用一个数组s[i],来存储当前节点到路径压缩后的父节点的权值和。

61040

简介 是一种高效的数据结构,常用来解决集合的合并和查找问题,常见于图论问题中。 2. 操作 2.1 构建 一般构建为初始时每个节点所属的集合编号即为自己的节点编号。...// 寻找的根节点 int findfather(int x) { return x == father[x] ?...[x] 改变的只是 x 的根节点,而不是整个的根节点,因为本质是依靠其根节点来维护的,所以应该将的根节点的 father 修改为已另一个集合的根节点,从而保证前一个集合被合并到了后一个集合中...stdc++.h> using namespace std; #ifndef _DSF_ #define _DSF_ #define ll long long #define MAXN 505 // ...x : (father[x] = findfather(father[x])); } // 合并并(将 x 节点所在集合并到 y 节点所在) void mergefather

44230

本篇博客参照了如下博客内容: http://www.cnblogs.com/horizonice/p/3658176.html 是一种树形结构,又叫“不相交集合”,保持了一组不相交的动态集合...---- 初始化 用数组来建立一个,数组下标代表元素,下标对应的值代表父节点,全部初始化为-1,根节点为一个集合的元素个数,数组的长度为的初始连通分量的个数。...要求各集合是不相交的,因此要求x没有在其他集合中出现过。...这里对操作有两种优化:根节点存树高的相反数或者根节点存集合的个数的相反数,这两种方法统称按秩归并。通常选用第二种方法。 归并过程如下图: ?...iostream> #include using namespace std; class UF{ private: int* array; //集中的联通分量的个数

33420

​ 在我们需要判断某一些事物之间是否存在一定的关系的时候,我们最好的办法不是使用图而是使用。因为我们关心的是他们之间是否有关系,而不是关心的他们到底存在怎样的关系。 ​...,简单来说就是 n 个集合,我们通过 union 操作来建立两个节点之间的关系。通过 connected 来判断两个节点之间的关系。...那么现在我们知道了 的基本操作就是 union 和 connected 。 逻辑结构: 一开始我们初始化都是初始化 n 个不相关的独立集合。...} } } ​ 好了现在代码看起来会比较完美了,该用的技巧我们都已经用上了,现在合并操作的时间复杂度是常数,而查找操作的复杂度则是 n+nlogn 应用: ​ 接下来一个的小应用的例子...,就是迷宫是否有解,我们就可以使用来找最上面,和最下面一行之间是不是有联通的节点,如果有的话我们就能找到迷宫的解。 ​

1.3K70

入门

请勿转载@HanKin 简介 ,在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中...性质 算法不支持分割一个集合。 算法思想 用集合中的某个元素来代表这个集合,该元素称为集合的代表元。 一个集合内的所有元素组织成以代表元为根的树形结构。...判断两个元素是否属于同一合,只需要看他们的代表元是否相同即可。 路径压缩 每次查找的时候,如果路径较长,则修改信息,以便下次查找的时候速度更快。...其实本题只是一个对分离集合()操作的问题。 我们可以给每个人建立一个集合,集合的元素值有他自己,表示最开始时他不知道任何人是它的亲戚。...的“路径压缩”算法:在集合的查找过程中顺便将树的深度降低。采用路径压缩后,每一次查询所用的时间复杂度为增长极为缓慢的ackerman函数的反函数—α(x)。

70520

Python笔记:(DSU)结构简介

原理 的核心思想在于将所有相互关联的集合都用一个代表元素进行表征,这样,只要找到两个元素对应的代表元素,判断其是否一致即可判断他们是否属于同一个集合;同样的,如果需要联合两个原本不相交的集合...更详细的原理说明可以参考下面的参考链接3中知乎专栏里的讲解,他对原理的说明讲的非常的详细,我主要就是通过的这篇专栏学习的相关内容。 3. 代码实现 1....一般代码实现 下面,我们来给出一般的的简单代码实现。...Friend Circles 这一题是最为典型的使用场景,我们直接套用集结构就能解答这道题。...参考链接 Disjoint Set Union (DSU) 及其应用 (Disjoint Set) 算法学习笔记(1) : wikipedia:

3.6K31

路径压缩

就是一种结构,通过保存节点以及节点上的标签,来判断这两个节点是否连接在一起。当两个节点绑定时,可以任选其中一个节点的标签,指定另一个节点。...& 1.节点列表 集中的节点只需要保存父亲节点的信息,那么线性结构字典、列表都可以。我们用一维数组,索引是自身id,值指向父亲。 初始化时每个节点指向自身。...举例:一层和二层节点集合合并: 如果二层节点的祖宗节点连接到一层节点上,那么就形成了一个三层节点。 另一种可能,一层节点连接到二层祖宗节点,新还是二层。...总结: 本文两个重点:介绍了和路径压缩;单向列表的反向遍历。

80220

(Union Find)

没想到有一天我也能搞懂,orz......实际上本文算是《Algorithms》一书的读后感 1.概述  的数学模型是一组不相交的动态集合S={A,B,...}...开始的情况是对于一个集合S={0,1,...,9}他们都是孤立的,随着程序的执行,用户输入不同的操作,比如union(3,4),union(3,8)等等,随着数据的输入,整个图的连通性也会发生变化,所以常常用来解决动态连通性问题...Union-Find API  上面介绍了的概念,下面我们就要设计。...= id[p]) { id[p] = id[id[p]]; p = id[p]; } return p; }  至此,算法基本上就介绍完了,从容易想到的...的应用,可以参考我的另外一篇文章应用举例

99910

简单讲解

是一种树型的数据结构,用于处理一些不相交集合的合并以及查询问题 其有两个基本操作: 1.合并两个不相交的集合。...2.在两个做合并的时候,权值也应该更新,一个根结点必定会成为另外一个根结点的子结点,这个权值也需要更新。...在每次在处加入新的值的时候,判断与,的位置是否已经存在,若存在,则用集合并,把贡献全部累加到根节点上即可。...5.所以不妨将每个座位看成一个集合,集合内存可能坐在该位置上的选手的编号,对于1操作,相当合并两个集合,在将,作为权记录下来,用带权来维护即可。(注意本题中根节点本身也有权)。 ?

72220
领券