题解：CF605B Lazy Student

CF605B Lazy Student

题目传送门

题意

思路

• 对于 MST 边，连接从点 $1$ 出发到新点的一条边。
• 对于非 MST 边：
  • 若需要连接的点超过了实际存在的点，输出 -1。
  • $1$ 已经给 MST 边了，所以左端点初始为 $2$，右端点初始为 $3$。左端点保持递增、右端点固定。
  • 当左端点追上右端点，左端点重置，右端点前进。
  这样的构造策略可以保证无环且充分利用每一条边。

代码