构造加逊

题意

给定一个无向图 \(E\) ，每次操作需要选择一个点 \(u\) ，然后对其余的的所有点 \(v\) 进行操作，如果 \((u, v)\in E\) 则删去这条边，否则将这条边加入图中，求最少几次类似操作能够使得图联通并输出操作方案

做法

首先统计联通块数量以及各点的度数

• 当原图为连通图时，答案显然为 \(0\) 。

• 当图中存在一个度数为 \(0\) 的点，答案显然为 \(1\) 。

• 当存在一个连通块不是团时，答案也为 \(1\) 。

  在该连通块中找到任意一个度数小于该连通块大小减一的非割点，并对其进行操作。因为不是团，因此在操作后依然保证原有连通块的联通，且能与其他连通块连边，固操作正确性有保障。

• 当存在三个及以上的连通块时，答案为 \(2\) 。

  第一步为任选一个点进行操作，此时连通块的数量显然为会变成 \(2\) ，并且其中一定有一个连通块不是团，此时即为上一种情况，不再赘述。

• 最后一种情况，两个连通块均为团，答案为较小连通块的大小。

  对小连通块中每个点均进行操作，正确性不难证明。