题目描述
给定一张 n 个点 m条边的无向图,求最少去掉多少个点,可以使图不连通。如果不管去掉多少个点,都无法使原图不连通,则直接返回 n。
样例
输入格式
输入包含多组测试数据。
每组数据占一行,首先包含两个整数 n和 m,接下来包含 m 对形如 (x,y) 的数对,形容点 x 与点 y之间有一条边。数对 (x,y)中间不会包含空格,其余地方用一个空格隔开。
输出格式
每组数据输出一个结果,每个结果占一行。
数据范围
0≤n≤50
输入样例:
0 0
1 0
3 3 (0,1) (0,2) (1,2)
2 0
5 7 (0,1) (0,2) (1,3) (1,2) (1,4) (2,3) (3,4)
输出样例:
0
1
3
0
2
算法1
手残了几次,但愿你能避免
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N=55, M=N*N;
int ver[M],nxt[M],f[M],head[N*2],tot=1;
int d[N*2],cur[N*2],fs[M];
int n,m,t,S,T,inf=0x3f3f3f3f;
bool g[N][N];
void add(int x,int y,int z){
ver[++tot]=y, f[tot]=z, nxt[tot]=head[x], head[x]=tot;
ver[++tot]=x, f[tot]=0, nxt[tot]=head[y], head[y]=tot;
}
bool bfs(){
queue<int>q;
memset(d,0,sizeof d);
q.push(S), d[S]=1, cur[S]=head[S];
while(q.size()){
int x=q.front(); q.pop();
for(int i=head[x], y; i ; i=nxt[i]){
if(!f[i] || d[ y=ver[i] ]) continue;
d[y]=d[x]+1, cur[y]=head[y];
if(y==T) return true;
q.push(y);
}
}
return false;
}
int find(int x,int limit){
if(x==T) return limit;
int flow=0;
for(int i=cur[x], y;i && flow<limit; i=nxt[i]){
cur[x]=i;
if(d[ y=ver[i] ]!=d[x]+1 || !f[i]) continue;
int k=find(y,min(f[i],limit-flow));
if(!k) d[y]=0;
f[i]-=k, f[i^1]+=k, flow+=k;
}
return flow;
}
int dinic(){
int ans=0,flow;
for(;bfs();)
while(flow=find(S,1<<30))ans+=flow;
return ans;
}
int main(){
while(cin>>n>>m){
memset(head,0,sizeof head);
memset(f,0,sizeof f);
memset(g,0,sizeof g);
tot=1; //忘了加这个,样例过没问题,提交会Segmentation Fault
for(int i=1,x,y;i<=m;i++){
char c;
cin>>c>>x>>c>>y>>c; //新学了这种输入方式
x++,y++; //变为从1编号
add(n+x,y,inf),add(n+y,x,inf); //n+出边点,其它入边点
g[x][y]=g[y][x]=true;
}
for(int i=1;i<=n;i++) add(i,n+i,1); //分裂时,n+是入边点,正常是出边点,这样才承前启后
memcpy(fs,f,sizeof f);
int ans=n;
for(S=n+1;S<=2*n;S++) //注意不要手残,加int,因为S/T是全局变量
for(T=S-n+1;T<=n;T++){
if(g[S-n][T])continue;
memcpy(f,fs,sizeof f);
ans=min(ans,dinic());
}
cout<<ans<<endl;
}
return 0;
}