问题标签 [disjoint-union]

这是disjoin set算法的一段代码请问return parent[v] = find_set(parent[v]);的意义和目的是什么？通常返回的是整数、布尔值或其他数据类型。

我使用 DSU（不相交数据集）解决了经典的母亲顶点问题。我使用了路径压缩。

我想知道它是否正确。我认为时间复杂度 O(E log(V))。

解决方案如下

1. 将每个顶点的父节点初始化为自身
2. 一旦优势出现，请尝试加入他们。请注意，如果 2 已经有其他父级，则 1->2 不能合并！就像如果图是 1->2 , 3->4 , 2->4
3. 这里边 1->2 合并为 par[1] = par[2]= 1 和 3->4 合并为 par[3]= par[4] =3。
4. 当涉及到合并 2->4 时，我们不能因为 par[4]!=4，也就是说，它有一些其他的传入边缘，在这个组之外。
5. 最后，检查所有父顶点，如果它们都相等，则母顶点存在。

代码是：

我被困在这个问题上： https ://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1099

目前，我有集合，集合中的每个元素都是朋友。但是，我不知道如何对付敌人。谁能指出我正确的方向？

有很多关于摊销复杂性或联合查找、快速查找操作的资料，但我找不到任何关于单一联合操作复杂性证明的信息。

那么，我怎样才能证明联合操作的摊销复杂度是O(log n)。

谢谢。

From cp-algorithms website:

Sometimes in specific applications of the DSU you need to maintain the distance between a vertex and the representative of its set (i.e. the path length in the tree from the current node to the root of the tree).

and the following code is given as implementation:

I don't understand how this distance to representative could be useful because it just represents distance to leader of the set in our data structure which might not be related to our original problem.
I tried several examples to see how distance changes when we do operations like union_sets and make_set but did not figure anything out. My question is what does this "distance to representative" represent or like what is the significance or any use of it. Any help in visualizing or understanding it is appreciated.

我尝试对这个问题使用 Union find 方法，但没有通过这个案例，有人可以让我了解为什么会这样吗？

find() : 对于 find 方法有路径压缩 union() : 对于 union 有按等级联合

问题链接

到目前为止通过 108/113 例 返回 5 预期 4

我正在解决图中的 Hackerrank 问题一个特定的问题https://www.hackerrank.com/challenges/journey-to-the-moon/problem

我应用了 DSU，但即使代码适用于某些测试用例，答案也是错误的。

它给出了部分正确我认为逻辑是正确的，但解决方案有一些问题

测试用例：10 7 0 2 1 8 1 4 2 8 2 6 3 5 6 9 我的输出->29 实际输出->23

我正在解决LeetCode.com上一个名为 Number of Islands 的问题：

给定一个表示“1”（陆地）和“0”（水）的地图的 mxn 2D 二进制网格网格，返回岛屿的数量。岛屿四面环水，由相邻陆地水平或垂直连接而成。您可以假设网格的所有四个边缘都被水包围。

我知道如何用 DFS 解决它，但我正在学习union-find并提出以下方法：

它对样本输入产生正确的答案，但对[["1","1","1"],["0","1","0"],["1","1","1"]].

在高层次上，我的逻辑是每当我遇到一个岛（1）时，我都会增加计数器并调用unionf()并尝试将它与它的邻居统一起来。如果这样的统一是可能的，我会减少counter，unionf()因为它链接到它的父岛（一个连接的组件）而不是一个新岛。

有人可以指出我的逻辑中缺少什么吗？谢谢！

所以我在 C++ 中做不相交联合集 (DSU) 数据结构。我vector<int> parent没有显示任何错误，但vector<int> rank显示出模棱两可的错误。为什么我收到错误：

为什么我会收到此错误？

我如何解决它 ？