2024“钉耙编程”中国大学生算法设计超级联赛（8）

Problems	AC
1001. cats 的快乐 CF 刷题
1002. cats 的随机原神
1003. cats 的飞机坠毁
1004. cats 的重力拼图	○
1005. cats 的二分答案	⊕
1006. cats 的最小生成树	⊕
1007. cats 的 k-xor	○
1008. cats 的数据结构	⊕
1009. cats 的凸包计算
1010. cats 的集合 1	⊕
1011. cats 的集合 2
1012. cats 的电脑中毒	○

1006

cats 有一个有 n 个点，m 个边的可能有重边的无向图。边有边权，其中第 i 条边的边权为 i。

在一次操作中，cats 会找出这个图的最小生成树，然后将图中所有属于最小生成树的边移除。cats 会不断重复以上操作直到图不连通为止。

现在，你需要告诉 cats 图中的每一条边是在第几次操作中被移除的。若一条边在操作结束时未被移除，你需要输出 −1。

可以证明在以上条件下，cats 每次选择的最小生成树一定是唯一的。

注：一个有 n 个点的图的最小生成树即为这个图的所有的包含全部 n 个点和刚好 n−1 条边的连通子图中使子图所有边的边权总和最小的子图。

有启发性的一道题。

解法一

朴素的想法就是按题意模拟 m / (n - 1) 轮 Kruscal，这样的话耗时 O(m / (n - 1) * m)