问题标签 [union-find]

我正在尝试解决 Union-Find 的这个问题，就像

后继删除。给定一组 N 个整数 S={0,1,…,N−1} 和以下形式的请求序列：

从 S 中删除 x 找到 x 的后继：S 中最小的 y，使得 y≥x。设计一种数据类型，以便所有操作（除了构造）都应该花费对数时间或更好。

尽管我发现很少有解决方案和文章解释如何使用 来完成此操作Union-Find，但我无法想象它是如何工作的。

例如： Delete(X)可以通过 来完成Union(X,X+1)，但它是如何作为删除我无法想象的。与 find 类似Successor(X)。

任何帮助/方向或解释的详细说明都会有很大帮助。

test.txt 文件包含以下输入：

第一列包含顶点（ 1 - 5 ）

上排（第一排）的意思Node 1是，连接到Node 2和Node 3

上排（第 2 排）表示 ,Node 2连接到Node 1,Node 4并且Node 5

现在这里的问题是，接受它总是说的任何输入：图包含循环。（虽然图不包含循环） 现在在上面的输入图中不包含循环但说图包含循环。我哪里错了？？谁能帮我 ？？

我原以为会包含这样一个有用的数据结构，C++ Standard Library但我似乎找不到它。

我有一个代表记录集的表格，例如

我想产生这样的输出

其中相交集被合并（注意集合a和集合b已合并；d和f也已合并）。

有没有用 SQL 做这个的好方法，而不是存储过程。我知道我正在寻找一种联合查找程序。

据我了解，当处理一对时，我们首先执行 FIND 操作并检查存在这些对象的树的根是否相等。在它们不相等的情况下，我们通过链接 2 个不同的根来执行 UNION 操作。

在 Sedgewick pg-15 property:1.2-"假设输入对的顺序是 1-2，然后是 2-3，然后是 3-4，依此类推。在 N-1 个这样的对之后，我们有 N 个对象都在同样的集合，快速联合算法形成的树是一条直线，N指向N-1，N-1指向N-2，N-3指向N-3，以此类推。”

根据我的说法，形成的树有根 1，从 2 到 N 的所有其他对象都是它的孩子——当我们扫描 1-2 时，有根本身，所以我们将它们链接起来，当我们扫描 2-3 时，2 的根是1 3 的根是 3 本身，所以我们链接 1 和 3 而不是 2 和 3。

在这种情况下，树怎么可能是一条直线？

问题如下：

在使用联合查找进行 Kruskal 查找最小生成树之后，

我们得到一个由 10 个顶点组成的不相交集数组。

您能否恢复 Kruskal 仅使用给定数组找到的 MST：

注意：如果下面的例子不清楚，则表示节点 1 的父节点是 7，以此类推。

如果我重建给定的数组，它看起来像这样：

注意：我知道使用路径压缩是不可能的，但是假设Union-Find没有使用路径压缩，它仍然是不可能的吗？

我刚开始普林斯顿算法课程，并尝试在 C 中实现一个非常基本的快速查找算法，如下所示 -

该程序没有按预期运行。当我尝试做 aunion(4,3)然后 aunion(3,8)时，只会arr[3]改变它的值而不是arr[4]。另外，我不确定为什么我必须使用getchar（程序没有它就一直结束）。

DFS with coloring would take O(V+E) vs union find would take O(ElogV) reference: http://www.geeksforgeeks.org/detect-cycle-undirected-graph/

So union find approach is slower. If V = 100, E = 100, DFS = 200, Union find is 1,000. Is there a reason to use Union find? I personally like it because it produces a clean code. Or anything I missed that union find is better in real practice?

所以我在做面试练习题，我遇到了这个问题：给定一个字符串 str 和一对数组，指示字符串中的哪些索引可以交换，返回执行允许交换后的字典顺序最大的字符串。您可以多次交换索引。

例子

对于 str = "abdc" 和 pairs = [[1, 4], [3, 4]]，输出应该是 swapLexOrder(str, pairs) = "dbca"。

通过交换给定的索引，您可以获得字符串：“cbda”、“cbad”、“dbac”、“dbca”。此列表中按字典顺序排列的最大字符串是“dbca”。

我有一个涉及寻找工会的有效答案，但我的答案太慢了：

有人可以帮我调整代码以提高速度吗？这是我的代码：

它可能是我用来查找工会的功能，但我在想也许我可以在不创建哈希的情况下做到这一点？此外，如果你知道解决问题的更好方法，我总是愿意学习一些新的东西。谢谢！

我正在寻找工会。我想根据其中一个索引是否与另一对索引共享一个数字来对数字对进行分组。所以：

我有一系列对，例如：

将它们分组到这样的工会中的最佳方法是什么：

（[1,3] 和 [3,8] 在一起，因为它们共享 3。该组与 [6,8] 联合，因为它们共享 8。在 javascript 中执行此操作的最佳方法是什么？

以下是其他示例：

编辑 这是我目前使用的方法：