给出边的最小排列权重，使得给定的边集是最小生成树
Give minimum permutation weight for edges such that a given set of edge is the Minimum Spanning Tree
问题：
给定一个包含 N 个节点和 M 条边的图，边的索引从 1 -> M。保证任意2个节点之间有一条路径。
您需要为M条边分配权重。 权重在[1...M]范围内，每个数只能出现一次
简而言之，答案应该是[1...M]的排列数组，其中arr[i] = x表示edge[i]的权重为x。
给你一组 R 个 n-1 条边。 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
- 如果边[i]被赋值，跳过
有什么方法可以改进我的解决方案，使其可以在 O(N.logN) 或更短的时间内运行吗？
是的，有一个时间复杂度为 O(m log m) 的算法。
非树边e的基本循环由e和e 端点之间树中的路径。给定权重，生成树最小当且仅当对于每个非树边 e，e 的基本循环中最重的边是 e本身。
字典序 objective 适合贪心算法，我们找到边 1 的最无效分配，然后边 2 给定边 1，然后边 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 端点的最不公共祖先的路径给出。为了进行收缩，我们添加了一个布尔字段来指示父边是否收缩，然后使用来自不相交集森林的路径压缩技巧。这项工作将是 O(m log m) 最坏情况，但 O(m) 平均情况。我认为很有可能可以在此处插入离线最不常见祖先算法，以将最坏情况降至 O(m)。
关于号码分配，我们可以在线性时间内处理。对于每条边，记录导致它被分配的边的索引。最后，通过该索引进行稳定的桶排序，通过将树边放在非树之前来打破平局。这可以在 O(m) 时间内完成。
问题：
给定一个包含 N 个节点和 M 条边的图，边的索引从 1 -> M。保证任意2个节点之间有一条路径。
您需要为M条边分配权重。 权重在[1...M]范围内，每个数只能出现一次
简而言之，答案应该是[1...M]的排列数组，其中arr[i] = x表示edge[i]的权重为x。
给你一组 R 个 n-1 条边。 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
- 如果边[i]被赋值，跳过
有什么方法可以改进我的解决方案，使其可以在 O(N.logN) 或更短的时间内运行吗？
是的，有一个时间复杂度为 O(m log m) 的算法。
非树边e的基本循环由e和e 端点之间树中的路径。给定权重，生成树最小当且仅当对于每个非树边 e，e 的基本循环中最重的边是 e本身。
字典序 objective 适合贪心算法，我们找到边 1 的最无效分配，然后边 2 给定边 1，然后边 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 端点的最不公共祖先的路径给出。为了进行收缩，我们添加了一个布尔字段来指示父边是否收缩，然后使用来自不相交集森林的路径压缩技巧。这项工作将是 O(m log m) 最坏情况，但 O(m) 平均情况。我认为很有可能可以在此处插入离线最不常见祖先算法，以将最坏情况降至 O(m)。
关于号码分配，我们可以在线性时间内处理。对于每条边，记录导致它被分配的边的索引。最后，通过该索引进行稳定的桶排序，通过将树边放在非树之前来打破平局。这可以在 O(m) 时间内完成。