题目要求 任意两个点不连通 这句话怎么有点熟悉？
然后联想到最小割的定义:一个边集被删除以后S,T不再联通，则称该边集为网络的割。边的容量之和最小的割成为网络的最小割。
emmm S,T 不再联通 确实有点像
于是这道题就可以用网络流最大流来做！
将一个点(x) 拆成 (x)和(x+n) 在这之间连有向边流量为1
对于原图中的无向边((x,y)),在网络中连接有向边((x',y),(y',x))，流量为inf
这样我们就可以从原图点的集合中 枚举任意两个点作为S,T 然后跑网络流最大流即可 注意源点和汇点 他们的出点和入点的流量为inf 即((s,s+n),(t,t+n)) 这两条边的流量为inf
细节详见代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
const int maxn=1000;
const int inf=1e9;
int fir[maxn<<1],nxt[maxn<<1],to[maxn<<1],val[maxn<<1],mf,ans;
int n,m,t,a[maxn],b[maxn],S,T,tot=1,dep[maxn],cnt[maxn],flag;
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
void add(int x,int y,int z){
nxt[++tot]=fir[x];fir[x]=tot;to[tot]=y;val[tot]=z;
nxt[++tot]=fir[y];fir[y]=tot;to[tot]=x;val[tot]=0;
}
void build_map(){
memset(fir,0,sizeof(fir));tot=1;
for(int i=1;i<=n;i++){
if(i==S || i==T) add(i,i+n,inf);
else add(i,i+n,1);
}
for(int i=1;i<=m;i++)
add(a[i]+n,b[i],inf),add(b[i]+n,a[i],inf);
}
void bfs(){
memset(cnt,0,sizeof(cnt));
memset(dep,0xff,sizeof(dep));
queue<int> q;
q.push(T);dep[T]=0;cnt[dep[T]]++;
while(!q.empty()){
int x=q.front();q.pop();
for(int i=fir[x];i;i=nxt[i]){
int y=to[i];
if(dep[y]==-1){
dep[y]=dep[x]+1;
cnt[dep[y]]++;
q.push(y);
}
}
}
}
int dfs(int x,int flow){
if(x==T){
mf+=flow;return flow;
}
int f=0;
for(int i=fir[x];i;i=nxt[i]){
int y=to[i];
if(dep[y]==dep[x]-1 && val[i]){
int ff=dfs(y,min(flow-f,val[i]));
if(ff){
f+=ff;val[i]-=ff;val[i^1]+=ff;
}
if(f==flow) return f;
}
}
if(!--cnt[dep[x]]) flag=1;
cnt[++dep[x]]++;
return f;
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d %d",&n,&m);ans=inf;
for(int i=1,x,y;i<=m;i++)
a[i]=read()+1,b[i]=read()+1;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j) continue;
S=i;T=j;mf=0;
build_map();
bfs();flag=0;
while(!flag)
dfs(S,inf);
ans=min(ans,mf);
}
}
if(n<=1 || ans==inf) printf("%d
",n);
else printf("%d
",ans);
}
}