题目

n(n<=4e3)个点不包含自环和重边的无向图，

你可以执行以下操作若干次：

1. 选择一个点u

2. 对于每个点v(v≠u)来说，若u、v之间当前有一条边相连，则断开这条边，

否则在u、v之间加一条边，使之相连

求使整张图联通的最小操作次数，如果需要操作，输出操作的点号

实际样例数t(t<=800)，sum n不超过4e3

思路来源

官方题解&他人代码

题解

一共五种情况，只找出四种，wa最后一种，最后补了其他人的代码

这种思维/性质题，还是要多结合图示手玩一下

1. 只有一个连通块，朴素解，答案为0

2. 图里存在一个孤立点，将这个孤立点连向其他所有点，答案为1，输出孤立点

3. 考虑一个连通块a，只要这个连通块不是一个团（两个点通过一条边相连也认为是朴素团），

则总能找出一个点x来，对x执行操作后，x一定还与连通块a联通，

并且，由于x之前和非a的联通块不通，现在连接后，就相通了

点x取这个连通块里度最小的点即可，答案为1，输出点x

4. 考虑有两个连通块，由于考虑了第三种情况，

只能这两个连通块都是团，此时一定需要将较小的那个连通块完整拆掉，

答案为较小连通块的点的个数，输出较小连通块内所有点

5. 考虑有三个及以上连通块，并且都是团的情况，

不妨恰有3个连通块，1 2 3两两不连通，

操作1上的某个点x后，x与1不连通，与2、3均直接联通

再操作2上的某个点y后，y与2不直接联通，与1、3均直接联通，

此时发现，所有点均与3连通块联通，答案为2，输出点x、y即可

心得

官方题解：读者自证不难

这里给出对于下划线部分，即第三种情况的一点解释，即：

引理：一个非团连通图内的最小度数的点，

将这个点连向的所有点反选（即之前连的断开，之前没连的连上）后，图仍然连通

证明：

1. 若最小度数点x不是割点，根据割点定义，一定成立

2. 若x是割点，考虑形如链x-y-z且xz之间没有边的部分，

断开xy后，xz就会相连，这部分仍然连通

所以，以x点为起点跑一个单源最短路后，得到其他点的dis数组，再割掉x这个点，

对于dis>=2的点所在的连通分量，操作前后都与x联通

3. 对于dis=1的联通分量内的点y来说，

则对于其他点z(z≠y,z≠x)来说，为了满足y的dis=1的条件，y和x要么同时直连z，要么同时没连

(1)x有连接dis>=2的连通分量，则y比x的度数小，与x是最小度数的点矛盾

（比较度数时，可以考虑抵消掉y和x同时直连的点）

(2)若x没有连接dis>=2的连通分量，

①若存在y，没有与连通分量内的其他所有点都相连，则y比x的度数小，与x是最小度数的点矛盾

(2)若任意y，都与连通分量内的其他所有点相连，则与这个图不是团矛盾

综上，引理得证

其实，直观感受一下也ok的

代码

/*#include
#include
#include
#include*/
#include
using namespace std;
typedef long long ll;
const int maxn=4e3+10,mod=1e9+7;
int t,n,u,v,par[maxn],sz[maxn],deg[maxn];
char s[maxn];
int find(int x){return par[x]==x?x:par[x]=find(par[x]);
}
void solve(){int ans=0,now=n,pos=-1;for(int i=0;isz[i]){now=sz[i];pos=i;}}}if(ans==1){puts("0");return;}for(int i=0;ideg[j]){mx=deg[j];id=j;}}}puts("1");printf("%d\n",id+1);return;}}if(ans==2){printf("%d\n",sz[pos]);for(int i=0;i