问题标签 [union-find]

我的代码试图实现联合查找算法，我有 id[] 数组和 sz[] 数组。我在 Union-Find 构造函数中初始化它们，但是一旦我尝试在 Union-Find 类的方法中使用这些数组，它会将所有数组值更改为 1。我不明白为什么。我有什么明显的遗漏吗？

文件

CPP 文件

目前在 Eclipse 中处理一个问题。数据结构加权快速联合查找

我有的：

- 包含用户 ID 的单独 .txt 文件中的数据列表。例子：

0 5

0 2

1 3

1 2

2 5

3 7

这基本上是说 ID 为 0 的用户在社交网络中与 ID 为 5 的用户连接，依此类推。如果 0 连接到 2，1 连接到 2，那么 0 连接到 2。希望这很清楚。无论如何，通过这个列表，我编写了一个 Main 类和一个 WeightedUnionFind 类。在我的主要课程中，我提出了几种有助于我回答问题的方法：

1. 每个人有多少人连接，（即有多少人连接到 0），有多少人没有连接？
2. 连接了多少组 ID，最大的组是什么？

我不想一个接一个地问这个问题，所以我只是在寻找一个起点。

就像我说的，到目前为止，我只介绍了这些方法，并且只需要一个起点来在 .txt 文件上实现这些方法。

我写了一个单独的类，叫做

希望这很清楚。

是否有解决以下问题的经典算法。假设没有存在量词的并集查找算法具有以下输入：

然后它将构建一些数据结构 u，以便我可以检查 u.root(x)==u.root(y)，以确定 x 和 y 是否在同一个子图中。

输入可以通过以下语法来表征：

现在假设我们也允许存在量词：

什么联合查找算法可以处理这样的输入。我仍然假设该算法构建了一些数据结构 u，我可以在其中通过 u.root(x)==u.root(y) 检查 x 和 y 是否在同一个子图中。

此外 u.root(x) 在与绑定变量一起使用时应该抛出异常。这些变量都应该被消除，不再是数据结构的一部分。意味着子图应该相应地减少，而不改变结果的有效性。

再见

我使用快速查找方法编写了一个简单的联合查找实现。这是我的代码

我还在. _ main当我循环它说 50 或 100 次时，这会打印正确的答案。但是当我循环它像 1000 次或更多次时，它给了我所有的 0。我正在使用代码块 ide。

此外，当我在 codechef 的在线编译器中编译相同的代码时，我得到了正确的输出。谁能告诉我这个异常？

我正在从头开始实现一个 Union-Find 数据结构，并且遇到一个问题，如果尝试重复联合调用，我的 find 方法会导致无限循环。

我正在实现Union By Size，并使用路径压缩进行查找。我创建了一个只有 10 个元素（0 到 N-1）的测试实现

例子：

当我在做第二个U 0 2时，循环被捕获，因为索引 2 处的值为零，根也为零，因此循环重复循环。当我尝试这样做时，遵循相同的逻辑U 1 4。我在 find 中的第二个循环有不正确的逻辑。

我的问题是：如何处理这些情况，以免陷入这个无限循环？

这是我的查找方法：

我如何称呼与联合相关的 find：（位于 main 中）

我说的是union-find-disjoint 数据结构。互联网上有很多关于如何实现这一点的资源。到目前为止，我已经了解了两种联合优化技术。第一个是通过变量 Rank 来“平衡”树，它表示最深节点的深度，因此是 find() 的上限。第二个优化是：设置一个对象的父节点为头节点，同时调用find()（设置中还包含了对象的父节点，所以变成了级联优化）。

但是，当实现同时使用它们两者时，它们通常会不加思索地将两者合并在一起。具体来说，GeeksforGeeks（仅作为示例，没有任何个人内容）这样做。这不会导致排名“损坏”和 O(log n) 复杂性吗？

例如，如果我有一长串节点（5 到 4 到 3 到 2 到 1 到 0，这是头部）并且我调用 find() 到 2，则排名保持 5，即使它应该是 3。

TLDR 在底部

我在学校被分配了一个编程项目来构建一个渗透模型，我遇到了一个让我很困惑的问题。首先，我们应该构建一个 api 来运行渗透模拟

现在，本书提供了quickfindUF和WeightedQuickUnionUF。与我交谈过的所有同学都在使用 PercolationStats 课程进行计时时得到了预期的结果，我们被指示要做，但我的结果非常好。这是课程

当我使用 QuickFindUF 在 percStats(200,100) 运行它时，大约需要 7 秒，如果我使用 WeightedQuickUnionUF 在相同的 200,100 运行它，大约需要 50 多秒？我很确定加权快速联合应该更快，这不仅仅是因为我的可怕的最坏情况随机数生成器变得不走运。我运行了很多次，但结果仍然大致相同，我已经盯着这里的代码看了很长时间，无法弄清楚为什么我的代码如此错误..

TLDR

正确的结果，错误的时间。由于某种原因，较慢的 api 更快，我不知道为什么。QuickFindUF 比 WeightedQuickUnionUF 快。（大约快 7-8 倍）。我究竟做错了什么？

我正在实现 Kruskal 算法，这是一种众所周知的查找加权图的最小生成树的方法。但是，我正在对其进行调整以在图中查找循环。这是 Kruskal 算法的伪代码：

我很难掌握FIND-SET()andMAKE-SET()函数，或者它们在不相交集数据结构中的实现。

我当前的代码如下所示：

当已经存在的两个顶点set vector再次出现时，我的代码在图中检测到一个循环。在我遇到这样的情况之前，这似乎在大多数情况下都有效：

当这些边按排序顺序出现时，会发生这种情况，因为a, b, c,d已经被推入set vector. 加入[a]到[c]不会在图中产生循环，但由于当前实现而被检测为循环。

在我的情况下，是否有任何可行的替代方法来检测周期？或者，如果有人可以解释Kruskal 算法的MAKE-SET、FIND-SET和UNION工作原理，那将有很大帮助。

我是第一次实现 Graph，为此我从 SPOJ 中解决了这个问题。

在 geeksforgeeks 的帮助下，应用联合查找算法来确定图形是否包含循环，但出现运行时错误（SIGSEGV）。

你能帮忙看看为什么会这样吗？