「CF1559D2」Mocha and Diana (Hard Version)
给出两个森林,节点数均为 n,节点编号均为 1 \sim n。
你可以进行加边操作。每次操作,你需要选择两个不同的正整数 x, y,然后在两个森林中都加上 (x, y)。你需要保证两个森林在加边后仍然是森林。
求最多可以加几条边。并给出加边方案。
数据范围:1 \leq n \leq 10^5,0 \leq m_1, m_2 < n。
时空限制:2s / 250MiB。
Solution
首先一条边 (u, v) 能添加,当且仅当 u, v 在 G_1, G_2 中均不连通。
可以证明:最终状态下,必定有其中一个森林被合并成了一棵树。
由上述结论,可以得知加边的选择是无关紧要的。
考虑优化这个贪心过程。先尽可能多地加入形如 (1, x) 的边,此时所有节点至少在其中一个图中,与 1 在同一个连通块。所有的点 x 可以被分成三类:
- 1 类点:在 G_1, G_2 中都与 1 连通。
- 2 类点:在 G_1 中与 1 连通,在 G_2 中与 1 不连通。
- 3 类点:在 G_1 中与 1 不连通,在 G_2 中与 1 连通。
注意到 (u, v) 能添加,当且仅当其中一个点为 2 类点,另外一个点为 3 类点。将 2 类点与 3 类点依次配对连边即可。
特别要注意,对于 G_1 来说,每个连通块只能选出一个 3 类点,对于 G_2 来说,每个连通块只能选出一个 2 类点。解决方法也很简单,每次找到一个 2 类点或 3 类点 x 时,就令 x 在对应图中与 1 连通。