我正在尝试生成一个具有可遍历和不可遍历位置的随机网格，并确保在 4 个方向之一{右、上、左、下}中存在从一个可遍历位置到任何其他可遍历位置的路径。可遍历位置表示为“[ ]”，不可遍历位置表示为“[X]”

我可以使用什么算法来查找网格中的不相交集并在不相交集之间创建路径？谢谢！

这是我使用的 DisjointSet 类：

这是我的迷宫课：

很长一段时间以来，我一直在寻找一种方法来实现generate()和solve()以及对迷宫墙壁的随机排序，我似乎无法在互联网上找到任何算法或实现来做到这一点.

如果由墙连接的两个部分（房间）不在同一个集合中，则generate()应该穿过迷宫变量中的置换墙并销毁它。该方法还应该在房间图中添加一条边（每个房间都有一个名为路径的邻接列表，并且Room类有一个变量id来标识每个图的顶点）。

solve()应该解决迷宫路径并生成Maze类的向量，其中包含到达出口的房间顺序。第一个房间位于 0 处，最后一个房间位于LASTROOM 处。

注意：迷宫和房间的构造函数如下：

如果有人愿意建议一个可以在 Java 中运行的实现，我将不胜感激，谢谢。

我正在尝试将 boost:disjoint_sets 用于由以下结构表示的非重叠间隔（在我的情况下，集合中的间隔必须在其成员之间没有交集）：

假设我有一个区间列表，例如（[1,3]、[4,5]、[6,10]、[8,9]）。我初始化一个不相交的集合，如下所示：

然后我在列表的所有元素中执行 make_set，这将导致 4 个不相交的集合，对吗？在此之后，我执行以下操作：

我不明白的是为什么最后一个 cout 说我只有一套，在我的理解中应该说我有 2 套 {[1,3], [4,5], [6,10]} 和{[8,9]}。

谁能帮我理解发生了什么？

有人可以帮我找到/制作/指向使用双向链接列表的不相交集实现的正确方向吗？我有一些补充代码，我已经开始编辑它，我想知道是否有人可以帮助我填写其余部分，或者至少给我一些关于如何这样做的指示。

不相交集.h

TemplateDoublyLinkedList.h

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

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

我当前的代码如下所示：

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

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

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

对于给定期限和即时完成利润的作业调度，提出了一种贪心算法，以最大化所有可行任务集的利润。

但是，推荐的程序实施是不相交的集合森林。

我还没有找到任何证明这种实现的文献（对于非计算机科学/数学背景来说很容易）。

任何对这种与编程语言无关的实现的引用都会受到赞赏。

对于那些不熟悉不相交集数据结构的人。

https://en.wikipedia.org/wiki/Disjoint-set_data_structure

我正在努力寻找答案。来自给定朋友组的朋友组及其关系。当然，毫无疑问，这可以使用 BFS/DFS 轻松实现。但是我选择使用不相交集，我也倾向于找到该人所属的朋友组等，并且不相交集听起来确实适合这种情况。

我已经实现了不相交集数据结构，现在我需要找到它包含的不相交集的数量（这会给我组数）。

现在，我坚持如何有效地找到不相交集的数量，因为朋友的数量可以大到 1 00 00 0。

我认为应该有效的选项。

1. 将新套装附在原件背面，并销毁旧套装。

2. 在每个工会中更改每个元素的父级。

但是由于朋友的数量很大，我不确定这是否是正确的方法，也许是否有任何其他有效的方法或者我应该继续实施上述任何方法。

这是我的代码以获取更多详细信息。（我没有在这里实现计数不相交集）

下面是我跟踪不相交集森林中每棵树的大小的实现。

你能告诉我它有什么问题吗？我正在尝试解决 UVa 问题https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3638

上面代码中的链接函数完成了更新树大小的工作。

解决问题的方法是找到元素0所属的集合，得到该集合的代表元素的大小。但是我得到了这个代码的错误答案。

你能帮我么

世界上有N顶点和M边。有三种类型的边：类型“AB”、“BC”和“CA”。

有 A、B 和 C 三个人。每个人都可以使用一条边当且仅当它的类型名称包含该人的姓名。（例如，A 可以使用 AB 类型和 CA 类型的边）

我想选择一些边，这样对于所有人来说，图形都是连接的。因此，如果我们制作一个由 AB 类型和 CA 类型的边组成的图，则该图应该是连通的。（这也应该适用于 AB/BC、BC/CA 型）

我应该如何解决这个问题？有两个版本

1. 如果我想最小化所选边的数量怎么办？
2. 如果我想最小化所选边的总成本怎么办？

这是我尝试过的。

主要是，如果它连接 X 和 Y 的两个图，则添加类型为“XY”的边非常好。所以，首先添加所有非常好的边，然后添加一些连接至少一个图的边为一个人。

• 如果我无限地打乱边缘的顺序，这可能是一个很好的解决方案，但我不确定这一点，它不能解决第二个问题。

• 我有一些贪婪的策略：首先为 A 制作一个连接图，A 的数量（或成本）最小，然后是 B，然后是 C。打乱人的顺序（因此算法将应用 6 次）

我有一种强烈的感觉，这个问题是 NP-hard，但不能将问题变成众所周知的 NP-hard 问题。

我想做的是将一组 ( n ) 项目分成大小相等的组（大小为m的组，为简单起见，假设没有剩菜，即n可被m整除）。多次这样做，我想确保没有一对项目在同一组中两次。

为了使这一点更加具体，对于构建六个项目中的两个的组A..F，一次可以以不同的方式将集合划分五次：

• (A, B), (C, D),(E, F)
• (A, C), (B, E),(D, F)
• (A, D), (B, F),(C, E)
• (A, E), (B, D),(C, F)
• (A, F), (B, C),(D, E)

同一组项目只能被划分为三个一组，而不会重叠：

• (A, B, C),(D, E, F)

_{（正如@DavidHammen 在下面指出的那样，在此示例中创建分区有不同的方法。但是，一旦创建了分区，就再也没有第二个分割将所有成对的项目分开了。这很好 - 我的应用程序没有'不需要生成所有可能的全局分区方法，满足约束的解决方案就可以了）}

我现在的问题是：有没有办法有效地做到这一点？有没有加快生成这些集合的技巧？

因此，到目前为止，我一直将其视为一个精确覆盖问题，并使用回溯算法（DLX 的一种变体）来解决它。这对配对非常有效，但随着组变得更大，算法必须考虑的可能性数量会激增，并且处理变得非常笨拙。

我正在寻找的是加快速度的技巧。任何想法都非常受欢迎，特别是（但不限于）：

• 优化和启发式方法以减少在求解之前需要考虑的可能性数量（例如，从上面的示例中可以清楚地看出，第一次拆分可以简单地任意进行，并且每个分区的第一组 [上面的第一列] 可以自动生成）。
• 是否有可以应对大量候选人的回溯变体？（即不需要预先产生所有的可能性）
• 我应该考虑的其他算法、方法或数学概念？

非常欢迎任何想法和建议。非常感谢您考虑这一点！

更新

好的，这已经有一段时间了，但我在这上面花了很多时间，想回复你。@david-eisenstat 通过给我正确的搜索词（非常感谢！）让我走上了正确的道路——我已经阅读了很多关于社交高尔夫球手问题的文章。

我发现的最好的资源之一，我想在这里分享，是Markus Triska的工作，他在他的论文中讨论了几种方法（然后继续提出一个非常好的算法）。如果有人遇到类似问题，强烈建议这样做！