首页
学习
活动
专区
工具
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],来存储当前节点到路径压缩后的父节点的权值和。

62840
您找到你想要的搜索结果了吗?
是的
没有找到

Sample Input 6 M 1 6 C 1 M 2 4 M 2 6 C 3 C 4 Sample Output 1 0 2 题目链接POJ-1988-Cube Stacking 解题思路...把递归和完美的结合在一起的,我们需要先设置三个数组分别 用于 1,找该节点的父节点,2该节点到其祖先节点的距离,3以该节点为祖先节点的点有几个;每次查找然后更新一旦遇到C,就用该节点的祖先节点包含的点数减去这个点到其祖先节点的数量就可以啦...,&c); if(c=='M') { scanf("%d%d",&x,&y); jion(...y的队伍里面,Q x表示查询x然后需要输出x现在的祖先节点是谁,这个节点一共有几个成员,x被移动了几次;另外每组开始的时候需要输出Case x:(这是第几组测试) 解题思路 这个题真的是麻烦,还是带权...这个题意识属于带权,构图之类的都很容易但是如何确定关系呢?我怎么确定这两个点冲突了呢?

74820

简介 是一种高效的数据结构,常用来解决集合的合并和查找问题,常见于图论问题中。 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

45530

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

34220

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

1.3K70

入门

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

72020

Union Find

严格来讲并不是一个数据结构,而是一个算法,毕竟其英文名直译是联合查找,但作为一个系列,还是当做数据结构讲了。 学术一点讲的话,是用来找一个无向图的联通分量。...接下来以此为例分析一下如何使用算法。 首先我们有一个parent数组来代表每一个节点的祖先,数组的每一项默认为节点的序号。...这样一个就建立好了,我们可以通过比较祖先判断两个节点是否连通。...应用 可应用在社交媒体中判断两个用户是否在同一个圈子中,也可以用于判断两个地点间是否有交通线路。...,大家应该理解掌握,最关键的是判断出一个场景是适用于,如果当时PAT考试的时候我看出来最后一题用的是,也能拿98分了。

2K70

简单讲解

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

74420
领券