问题标签 [union-find]

假设我有五套我想聚类。我了解这里描述的 SimHashing 技术：

https://moultano.wordpress.com/2010/01/21/simple-simhashing-3kbzhsxyg4467-6/

例如，如果它的结果​​是：可以产生三个簇（{A}和{B,C,D}） ：{E}

同样，MMDS 书第 3 章中描述的 MinHashing 技术：

http://infolab.stanford.edu/~ullman/mmds/ch3.pdf

如果其结果是：也可以产生相同的三个集群：

（每组对应一个由三个“波段”组成的MH签名，如果至少有一个签​​名波段匹配，则将两组分组。更多的波段意味着更多的匹配机会。）

但是我有几个与这些相关的问题：

(1) SH可以理解为MH的单频段版本吗？

(2) MH 是否一定意味着使用像 Union-Find 这样的数据结构来构建集群？

(3) 我认为这两种技术中的集群实际上是“预集群”，从某种意义上说，它们只是“候选对”的集合，我是否正确？

(4) 如果 (3) 为真，是否意味着我仍然需要O(n^2)在每个“预集群”内进行搜索，以将它们进一步划分为“真实”集群？（如果我有很多小且相当平衡的预集群，这可能是合理的，否则就不是了）

我正在观看 Robert Sedgewick 关于改进快速联合的视频。( https://youtu.be/sEo6LlPxpHE?t=267 )

在那里，他使用树的大小而不是高度。实际上问题是找到根节点。如果高度很高，则很难找到。所以我们应该找到一种方法来减轻高度的影响。只有当我们比较高度时，它才会按预期工作吗？将较短的树连接到较高的树不会解决问题，而是这样做：将具有较少节点的树连接到具有较多节点的树？

下面的情况呢？

根据视频中的逻辑：

一棵树的大小 = 4

B 树的大小 = 7

如果您将 A 连接到 B 。实际上，我们正在使生成的树更高（高度 4）。但是如果我们根据树的高度来完成它，我们可以通过将树 B 连接到 A 来解决它。因此生成的树的高度为 3。

我对吗 ？如果错了，我错在哪里？

I have a set of intervals on the x-axis and i wish to find out the total number of intervals containing a certain element. I know that the problem can be solved by binary search but am not able to do so. How do I code it up? (the intervals may overlap, otherwise I thought of using union find-disjoint set data structure)

Example :

The above intervals are the intervals on the real line.(inclusive) and suppose I have a vector of points:

How do I proceed with my binary search approach?

基本上，除了检查顶点 u 和 v 是否不在同一个组件中之外，我还试图通过添加一个条件来修改 Kruskal 的算法。我隐约了解 union-find 数据结构的工作原理，所以我想检查一下我是否真的得到了正确的想法。

鉴于我有一个无向图 G = (V, E) 和一个包含 V 中的一些顶点的集合 A（顶点 A ⊂ V 的子集），我想捕获 V 中每个顶点 u 的实例（循环） ，你也在这个集合A中找到。我正在考虑使用：

这会因为设置参数不同（因此标签不同）而不起作用吗？我只是想确认...

为了澄清，我需要知道一条边 (u, v) 是否包含集合 A 中的一个顶点。我试图使用 Union-Find 来实现这一点（因为 find() 需要 O(1) 时间），而不是遍历集合 A 来比较每个元素......谁能告诉我这是否可能？还是我应该只使用数组遍历方法？

谢谢你。

给定 (A,B) 形式的多个元组，其中 A 是父级，B 是二叉树中的子级，查找输入是否有效。提供了 4 个错误条件：

1. 如果父母有两个以上的孩子，
2. 如果输入了重复的元组，
3. 如果树有一个循环，
4. 如果可能有多个根。

对于多个有效性条件的违反，按上述顺序打印最先出现的条件。如果输入有效，则以串行表示形式打印树。例如：如果输入是 (A,B), (B,C), (A,D), (C,E) ，输出： (A(B(C(E)))(D))

我正在考虑通过联合查找数据结构解决它，但无法对其进行编码。任何人都可以帮助我使用 c/c++ 中的逻辑或伪代码吗

在实现 union-find 时，我通常会find像这样编写带有路径压缩的函数：

这很容易记住，并且可以说很容易阅读。这也是有多少书籍和网站描述了该算法。

但是，天真地编译，这将使用与输入大小成线性关系的堆栈内存。在许多默认情况下会导致堆栈溢出的语言和系统中。

我所知道的唯一非递归写作方式find是：

许多编译器似乎不太可能发现这一点。（也许 Haskell 会？）

我的问题是在什么情况下使用以前的版本是安全的find？如果没有广泛使用的语言可以消除递归，我们不应该告诉人们使用迭代版本吗？是否有更简单的迭代实现？

我有以下数据集

现在我如何使用 union-find 确定 5 是否与 7 相关？有人请指导我。

问题：http ://codeforces.com/contest/468/problem/B

Little X 有 n 个不同的整数：p1, p2, ..., pn。他想把它们都分成两组A和B。必须满足以下两个条件：

如果数字x属于集合A，那么数字a-x一定也属于集合A。如果数字x属于集合B，那么数字b-x也一定属于集合B。帮助小X将数字分成两组或确定这是不可能的。

输入 第一行包含三个以空格分隔的整数 n、a、b（1 ≤ n ≤ 105；1 ≤ a、b ≤ 109）。下一行包含 n 个以空格分隔的不同整数 p1, p2, ..., pn (1 ≤ pi ≤ 109)。

输出 如果有办法将数字分成两组，则在第一行打印“YES”。然后打印 n 个整数：b1, b2, ..., bn（bi 等于 0 或 1），描述除法。如果bi等于0，则pi属于集合A，否则属于集合B。

如果不可能，请打印“NO”（不带引号）。

现在，我开发了以下代码：

基本上，尝试将每个元素与 Set A 或 Set B 中的每个元素合并。如果它们都依次合并，则最后输出 NO。但是，这给出了错误的输入答案：

输出应该是：NO而我的代码给出的输出为

我的逻辑哪里出错了？请帮忙！

我创建了一个大小为n的二维数组，其中包含分别代表封闭空间和开放空间的 1 和 0。

现在我需要测试 2d 数组以查看它是否会渗透，但我不知道该怎么做。

我有以下代码用于创建数组并将每个点随机分配给 1 或 0。

这将创建一个具有封闭边界 (1s) 的数组，并在顶部和底部放置 2 个随机进入/退出点 (0s)。我唯一缺少的部分是测试渗透。

任何帮助表示赞赏，谢谢！

我正在使用以下方法研究联合查找算法：

我写了这个方法来找到一个家庭的最后一个成员

它有效，但问题是我将使用大集合处理这个哈希图；所以我想修改 find 方法，使其将 find(src) 设置为 src 的“父亲”。但我不能这样做，而且我有直觉的原因：如果我尝试在方法的开头进行复制

然后在方法结束时

它不起作用，因为它实际上并没有进行“正确”的复制。我试过克隆父母，但它也不起作用。

谢谢大家，圣诞快乐！