Description

Link：CF1559D2

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$ 连通。