问题标签 [disjoint-sets]

通常使用秩和路径压缩的启发式方法来实现快速的不相交集数据结构操作。不知何故，我发现按重量和路径压缩的启发式方法对我来说更明智。以下实现是否通过等级和路径压缩实现了与启发式方法相同的运行时间？

注意：结构节点中使用的排名是用词不当，它指的是孩子的数量而不是树的高度（排名一般意味着）

我想从 TopCoder 解决这个问题，其中给出了一个字符串，并且在每个步骤中，您必须将所有出现的字符（您选择的）替换为另一个字符（您选择的），以便在最后步骤你得到一个回文。问题是确定替换的最小总数。

到目前为止的想法： 我可以确定每一步之后的字符串只是图中的一个节点/顶点，并且每条边的成本是该步骤中进行的替换次数，但我不知道如何使用贪婪那（这绝对不是最小生成树问题）。我认为识别所有可能的节点和边缘成本并将问题转换为最短路径问题是没有意义的。另一方面，我认为在每一步中，将字符 X 替换为冲突次数最多的字符是有意义的，而字符 Y 与字符串中出现最多的 X 冲突。

无论如何，我也无法证明它有效。我也无法确定任何已知问题。有任何想法吗？

我的算法课上有一个问题，我无法解决。问题指出 Theres 是一种排序算法，O(nlogn)搜索是通过 Binary searchtaking 完成的O(log n)。两组是给定的P，Q我必须设计一个算法来确定这两组是否不相交。

我在 SO 和其他地方看到过文章，其中引用了以下方法来确定图中两个节点之间是否存在路径。我想知道是否有人比另一个更好？

1. 广度优先搜索 -O(V + E)

2. 深度优先搜索 -O(V + E)

3. 使用不相交集- O(n log n)（不确定是否是O(n log n)）

所有这些方法是否适用于有向图和无向图、循环图和非循环图？

对其中一个有什么偏好吗？

我正在使用不相交集的查找/联合方法在无向图中实现循环检测代码。

这是实现：

这是isConnecteddisjoinset的

如果两个节点具有相同的根，（由 返回find），则表明存在一个循环。对于像这样没有循环的图(1,2),(2,3),(3,4)，我的方法返回 true。我不明白出了什么问题。

编辑最新：根据以下建议：

我明白了node:java.util.NoSuchElementException

尝试用 Java 自己编写代码......我创建了一个 GraphNode 类来表示具有指向其父级的指针的节点。

我还创建了一个 DisjointSet 类，其中包含一个 MakeSet 方法，该方法创建一个 GraphNode 对象并使其父引用引用自身。

问题是：我如何存储每个节点，以便稍后在 Union 和 FindSet 中轻松访问它？我首先想到将它存储在 BST 中，但我必须创建一个自定义 TreeNode 类，该类不仅存储值，还存储对 GraphNode 的引用。有没有更简单的方法？

假设我们有一个有限集 S 和一个 S 的子集列表。然后，集合打包问题询问列表中的一些 k 子集是否成对不相交。该问题的优化版本，最大集打包，要求列表中成对不相交集的最大数量。

http://en.wikipedia.org/wiki/Set_packing

所以让S = {1,2,3,4,5,6,7,8,9,10}

则成对不相交集的最大数量为 3 ( Sa, Sc, Sd )

我找不到任何有关所涉及算法的文章。你能解释一下吗？

我的做法：

根据大小对集合进行排序。从最小尺寸的集合开始。如果下一个集合中没有元素与当前集合相交，那么我们将集合合并并增加最大集合的计数。这听起来不错吗？有更好的想法吗？

我正在尝试解决这个问题，但无法快速解决。

简而言之 - 我们有一个图（有向图），我们想找出从哪个节点（给出一组可供选择的节点）我们可以访问最多的节点。一个简单的实现是从每个节点运行 DFS/BFS，看看我们可以访问多少。但是它太慢了，因为图中有超过 5000 个节点。运行 5000 BFS/DFS 需要很长时间。

另一方面我也觉得这个问题可能与不相交集数据结构有关？但是我无法以这种方式制定它，因为在我不相交的集合实现中提到了一些提到的规则。

有人可以提示如何解决这个问题吗？

我正在尝试在 Cormen 等人的算法简介中做这个练习，这与 Disjoin Set 数据结构有关：

假设我们希望添加操作PRINT-SET(x)，给定一个节点并以任意顺序x打印 集合的所有成员。x展示我们如何向不相交集森林中的每个节点添加一个属性，从而使PRINT-SET(x)时间与的集合的成员数成线性关系x，并且其他操作的渐近运行时间保持不变。假设我们可以在 O(1) 时间内打印出集合中的每个成员。

现在，我很确定需要的属性是一个尾指针，所以它可以跟踪孩子。

由于不相交的集合结构已经有一个父属性，find-set(x)可以很容易地打印出一个方向的节点。但是现在，有了一个尾指针，让我们也转向另一个方向。

但是，我不确定如何编写算法来做到这一点。如果有人可以用伪代码帮助我，那将不胜感激。

这里我有一个有向图G。我需要确定是否存在一组顶点不相交的循环，以便每个顶点都属于一个循环。

我不确定这是否可以在多项式时间内完成，或者它是否是 NP-Complete？谁能至少指出我正确的方向？