-
题意
给定一个无向图 \(E\) ,每次操作需要选择一个点 \(u\) ,然后对其余的的所有点 \(v\) 进行操作,如果 \((u, v)\in E\) 则删去这条边,否则将这条边加入图中,求最少几次类似操作能够使得图联通并输出操作方案
-
做法
首先统计联通块数量以及各点的度数
-
当原图为连通图时,答案显然为 \(0\) 。
-
当图中存在一个度数为 \(0\) 的点,答案显然为 \(1\) 。
-
当存在一个连通块不是团时,答案也为 \(1\) 。
在该连通块中找到任意一个度数小于该连通块大小减一的非割点,并对其进行操作。因为不是团,因此在操作后依然保证原有连通块的联通,且能与其他连通块连边,固操作正确性有保障。
-
当存在三个及以上的连通块时,答案为 \(2\) 。
第一步为任选一个点进行操作,此时连通块的数量显然为会变成 \(2\) ,并且其中一定有一个连通块不是团,此时即为上一种情况,不再赘述。
-
最后一种情况,两个连通块均为团,答案为较小连通块的大小。
对小连通块中每个点均进行操作,正确性不难证明。
-