题解：CF1761E Make It Connected

KidA · 2024-11-09 17:16:18 · 题解

构造题，先从特殊情况开始。

• 图联通。操作次数显然为 0。

• 有孤点。直接操作一次这个孤点即可。

• 有一个联通块不是完全图。那么操作其中任意一点之后这个点一定还会在这个联通块里，并且还会和其他联通块联通，从而使得整个图联通。

第二种情形手玩样例可以看出，第三种情形则随便构造一个不联通的普通图即可发现。

其中，第三种情况启发我们依据完全图的数量去对一般情形进行分类。

继续手玩样例，可以得出：

• 有恰好两个完全图。选择较小的那个，不停地选点操作即可。

更一般的情形（画图可知）：

• 有多于两个完全图。随便选一个点进行操作，容易发现此时图一定只有两个联通块，且至少有一个不是完全图。这时就转化为第三种情况了。因此仅需操作两次。

然后我们就解决了此题。

本人实现是并查集解法，时间复杂度 O(n^2\alpha(n))。