CF1559D Mocha and Diana

发布于 2021-08-16  1.22k 次阅读


题目链接

题目大意

给出两个 $n$ 个点的无向无环图(可能不连通),你可以进行若干次加边操作,每次加边操作可以在两个图上同时加入一条边 $(x,~y)$,要求加边操作结束后两个图仍然是无向无环图。让你求出最大的加边次数并输出任意一种方案。

$n \le 10^5$

分析

CF1559D1 我们会发现以任何顺序尽可能多地加入合法边都不会影响最终答案。

考虑先尽可能多地加入形如 $(1,~x)$ 的边,加入完这些边后所有的结点至少在一个图中与 $1$ 在同一个联通块中,此时我们可以将所有的点分为三类:

  1. 第一个图中与 $1$ 联通,第二个图中与 $1$ 联通。
  2. 第一个图中与 $1$ 不联通,第二个图中与 $1$ 联通。
  3. 第一个图中与 $1$ 联通,第二个图中与 $1$ 不联通。

容易发现对于所有的 1 类点其不可能再与其他点连边。因为对于每一个点, $1$ 在至少一个图中与他们联通,而该点在两个图中均与 $1$ 联通,所以每一个点均与该点在至少一个图中联通。

我们将所有的 2 类点和 3 类点找出并放入两个集合。此时对于所有的剩余的合法边,其两个端点一定为 2 类点或 3 类点。而我们发现 2 类点之间互相连通,3 类点间也互相连通,所以所有的可能的合法连边的两个端点一定是一个 2 类点和一个 3 类点,且任意一个 2 类点与任意一个 3 类点均可组成一条合法边。每次从两个集合中分别取出一个点,将他们连边后再从两个集合中删去不符合 2 类点或是 3 类点性质的点并重复此操作至集合为空即可。

代码

View on Github


我缓慢吐出一串啊吧啊吧并不再想说话