给定一组边构成的最小生成树，为这些边赋予最小置换权重。

Question

给定一组边构成的最小生成树，为这些边赋予最小置换权重。

algorithmminimum-spanning-treedisjoint-sets

3

问题：

给定一个由N个节点和M条边组成的图，边的索引范围为1 -> M。保证任意两个节点之间都有路径。

您需要为M条边分配权重。 权重的范围在[1 ... M]之间，并且每个数字只能出现一次。

简而言之，答案应该是[1...M]的排列数组，其中arr[i] = x表示边[i]的权重为x。

您将获得n-1条边的集合R。 R保证是图的生成树。

找到一种分配权重的方式，使得R成为图的最小生成树；如果有多个答案，请打印字典序最小的一个。

限制条件：

N, M <= 10^6

例子：

边缘：

3 4
1 2
2 3
1 3
1 4

R = [2, 4, 5]

Answer: 3 4 5 1 2

说明：

如果你对上面的图中的图形分配权重，MST 将是集合 R，并且它具有最小的字典顺序。

我使用 O(N^2) 的方法:

由于需要最小字典顺序，我遍历边的列表，按递增顺序分配权值。最初，w = 1。可能有三种情况：

如果 edge[i] 在 R 中，则将 weight[i] 赋值为 w，将 w 增加 1
如果 edge[i] 不在 R 中：假设 edge[i] 连接节点 u 和 v。为了 R 中从 u 到 v 的每条边（如果该边尚未分配）分配权值并增加 w。然后为 edge[i] 分配权重并增加 w。
如果 edge[i] 已经分配，跳过它。

是否有任何方法可以改进我的解决方案，使其可以在 O(N.logN) 或更少的时间内工作？

- unglinh279

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Eisenstat · Accepted Answer

是的，有一种O(m log m)时间复杂度的算法。

非树边e的基本环由e和树上连接e两端点的路径组成。给定权重，生成树是最小的当且仅当对于每个非树边e，其基本环中最重的边是e本身。

词典式目标适合贪心算法，我们找到第一个有效的分配给边1，然后给出边2，再给出前面的边，以此类推。核心思想是：如果下一个未分配的边是非树边，则将下一个数字分配给其基本环中未分配的树边；然后分配下一个数字。

在这个例子中，首先是3-4边，边1-3和1-4完成了它的基本环。因此我们分配1-3 → 1和1-4 → 2，然后3-4 → 3。接下来是1-2，一条树边，所以1-2 → 4。最后，2-3 → 5（1-2和1-3已经被分配）。

为了高效实现这个算法，我们需要两个要素：一种枚举基本环中未分配边的方法，以及一种分配数字的方法。我对前者的建议是使用带有已分配边缩减的生成树。我们不需要任何花哨的东西，从某个地方开始根化生成树，并运行深度优先搜索以记录父指针和深度。边e的基本环将由其端点的最近公共祖先路径给出。为了进行缩减，我们添加一个布尔字段来指示父边是否被缩减，然后使用不相交集合森林中的路径压缩技巧。最坏情况下的工作量是O(m log m)，但平均情况下是O(m)。我认为离线最近公共祖先算法可以插入到这里，以将最坏情况降至O(m)。

至于数字分配，我们可以在线性时间内处理。对于每条边，记录导致其被分配的边的索引。最后，通过该索引稳定桶排序，将树边放在非树边之前来打破平局。这可以在O(m)时间内完成。