问题:
给定一个包含 N 个节点和 M 条边的图，边的索引从 1 -> M。保证任意 2 个节点之间存在路径。
您需要为 M 条边分配权重。 权重在[1...M]范围内，每个数字只能出现一次。
简而言之，答案应该是 [1...M] 的排列数组，其中 arr[i] = x 表示 edge[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。可以有 3 种情况:
- 如果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) 或更短的时间内运行？
最佳答案
是的，有一个时间复杂度为 O(m log m) 的算法。
非树边e的基本循环由e和树中端点之间的路径组成>e。给定权重，生成树最小当且仅当对于每个非树边 e，e 的基本循环中最重的边是 e 本身。
词典编目目标适用于贪婪算法，在该算法中，我们为边 1 找到最无效的分配，然后在给定边 1 的情况下找到边 2，然后在给定之前的边的情况下找到边 3，等等。核心思想如下:如果下一个未分配的边为非树边，在其基本循环中将下一个编号分配给未分配的树边；然后分配下一个数字。
在示例中，第 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 的基本循环将由到 e 端点的最不公共(public)祖先的路径给出。为了进行收缩，我们添加了一个 bool 字段来指示父边是否收缩，然后使用来自不相交集森林的路径压缩技巧。这项工作将是 O(m log m) 最坏情况，但 O(m) 平均情况。我认为很有可能可以在此处插入离线最不常见祖先算法，以将最坏情况降低到 O(m)。
至于数字分配，我们可以在线性时间内处理。对于每条边，记录导致它被分配的边的索引。最后，通过该索引进行稳定的桶排序，通过将树边放在非树之前来打破平局。这可以在 O(m) 时间内完成。
关于algorithm - 给出边的最小排列权重，使得给定的边集是最小生成树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/70530290/