CSES 1685 New Flight Routes 题解

b6e0_ · 2024-04-18 15:38:04 · 题解

题目链接

简要题意

给定一个 n 个点 m 条边的有向图，求最少要添加多少条有向边使得图强连通，并构造方案。1\le n\le10^5,1\le m\le2\times10^5。

做法

首先将图强连通缩点，变成 DAG。

若图只由孤点组成，则答案为点数，方案显然。

否则，图由一些非孤点连通块和一些孤点组成。对于非孤点连通块中连的某条边，我们将它串上每个孤点，注意到这会使答案增加孤点数。并且，每个孤点至少让答案增加 1，所以这种方案达到了最优解。于是我们只需要解决图中无孤点的情况。

记入度为 0 的点集为 S，出度为 0 的点集为 T。显然，我们任何时刻连的边，一定是当前出度为 0 的一个点到入度为 0 的一个点，否则换成这样的边一定更优。

若 S 或 T 大小为 1，那么将 S 与 T 中的点两两连边就能达到最优解。对于 |S|,|T|\ge2 的情况，注意到如果存在 u\in S,v\in T 满足 u 能到达除 v 之外的某个 T 中的点，v 也能被除 u 之外的某个 S 中的点到达，那么连边 v\to u 后新图的 |S|,|T| 都减小 1。并且，任何连边方式都最多使 |S|,|T| 减小 1。这意味着，如果任何 |S|,|T|\ge2 的图都能找到一组 u,v，那么答案为 \max(|S|,|T|)。

实际上，这是满足的。因为，若 |S|,|T| 中点两两可达，那么任取一组 u,v 均可；否则取 u,v 满足 u 不可达 v 即能满足要求。

下面解决构造方案的问题。

做法一

考虑如下算法：对于 S 中的每个点 u，在 DAG 上以它为起点搜索，只走之前没访问过的点，若遇到了一个 T 中的点 v 则直接停止搜索，记录下这对 (u,v)。这样我们得到了若干对 (u_i,v_i)。然后，我们对于所有 i，将 v_i 和 u_{i+1} 连边，v_n 和 u_1 连边。这样，所有的 u_i,v_i 形成了一个环。然后，将新图重新缩点得到 S',T'，此时 S' 与 T' 中点两两可达，随便连即可。

显然这样的构造只有 \max(|S|,|T|) 条边，我们只需要证明 S' 与 T' 中点两两可达。我们只要证明，新图 S' 中每个点可达环上一个点，T' 中每个点可被环上一个点到达。考虑搜索算法的过程容易证明，搜索算法中每个访问过的点都能到达环上的点，每个没访问过的点都能被环上的点到达。于是得证。

时间复杂度 \mathcal O(n+m)。

做法二

结论：对于任意 |S|,|T|\ge2 的图，不满足条件的 u,v 最多有 |S|+|T|-1 对。证明：若每一对不满足条件的 u,v 连边，则形成若干点不交的菊花，边数显然小于等于点数减一。

这意味着，若我们随机选取一对 (u,v)，满足条件的概率最小为 \frac{(|S|-1)(|T|-1)}{|S||T|}。

若我们等概率选取 k=\frac{\min(|S|,|T|)}2 对不含公共元素的 (u,v)，全部满足条件的概率为：

期望随机 \mathcal O(1) 次即可得到满足条件的方案。判断是否全部满足条件只需要将新图重新求一遍答案，看看答案是否恰好减少了 k 即可。

因为 \min(|S|,|T|) 每次除以 2，所以 \mathcal O(\log n) 次会变为 \min(|S|,|T|)=1 的平凡情况。总时间复杂度 \mathcal O((n+m)\log n)。

参考资料

https://oi-wiki.org/misc/rand-technique/#%E4%BE%8Bcses-1685-new-flight-routes

https://vjudge.net/solution/42972073