CF1383C

AsunderSquall · 2021-08-24 07:48:56 · 题解

将 WCC 和 DAG 加粗是因为认为这样看上去比较美观。

感觉现有的两篇题解对最优性的证明都迷迷糊糊看不懂，这里来补充一个证明。

感谢 @AThousandMoon 的帮助。

在此之前，请您先阅读其他两篇题解。

我们称原来的图为 G，按照时间顺序添加的边生成的图为 G'，且只考虑 G 是一个弱连通分量（以下简称 WCC，Weakly Connected Component），图中有 n 个点，图中最大 DAG 大小为 m。

显然最终生成的 G' 也是 WCC。（不然会有 G 中直接有连边的 u \to v，在 G' 中 u 无法到达 v）

我们动态维护 G 中的所有 WCC，以及点集 |S|，初始的时候有 n 个大小为 1 的 WCC，|S| 为所有点的集合。

我们考虑按照时间顺序进行一次操作，添加了边 (u,v) 进 G'。

• 如果 u,v 在同一个 WCC 里，如果 v 存在于 |S|，那么将 v 从 |S| 中删去。
• 如果 u,v 在不同 WCC 里，那么合并这两个 WCC。

如果 G 中有环，那么 G' 中存在时间递增的从某个点走回这个点的路径，可以发现这样的构造方式，可以使 |S| 中没有这样的点。

这样最终这个 G 生成一个大的 DAG，假设我们总共进行了 k 次操作。
第二种情况发生了 n-1 次，所以第一种情况发生了 k-n+1 次，最多删去了 k-n+1 个点，那么 |\mathrm{DAG}|\ge 2n-k-1 ，所以 k\ge 2n-|\mathrm{DAG}|-1。

于是我们就知道了，G 对应的 G' 边数 \ge2n-m-1。

构造方案见其他题解就行了。