求的是无向图的点连通度。开始便想到网络流，既然选的是点，当然就要拆点加边了。但无论如何也不敢往枚举源汇点的方向想，因为网络流复习度很高。看看网上大牛的，都是枚举，再看数据，原来N才50个点，枚举无压力啊。看来自己以后要注意分析一下复杂度了。
总结：
1）无向图点连通度
看来没有什么好的算法。网络流。把点i拆成i->i‘容量自然是1，把无向图的边也拆成两条有向边i'->j,j'->i，容量为无穷。然后，枚举求s'->t的最小割就可了。
2）有向图点连通度
这个更简单了，单纯拆点建图就可以了。
3）无向图边连通度。
可以用store-wanger求最小割。边权为1
4）有向图边连通度
就是网络流求最小割
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int INF=0x3f3f3f3;
const int MAXN= ;
const int MAXM=; struct Node{
int from,to,next;
int cap;
}edge[MAXM];
int tol; int dep[MAXN];
int head[MAXN];
bool maze[MAXN][MAXN];
int n,m;
void init(){
tol=;
memset(head,-,sizeof(head));
}
void addedge(int u,int v,int w){
edge[tol].from=u;
edge[tol].to=v; edge[tol].cap=w; edge[tol].next=head[u];
head[u]=tol++;
edge[tol].from=v;
edge[tol].to=u;
edge[tol].cap=;
edge[tol].next=head[v];
head[v]=tol++;
} int BFS(int start,int end){
int que[MAXN];
int front,rear; front=rear=;
memset(dep,-,sizeof(dep));
que[rear++]=start;
dep[start]=;
while(front!=rear){
int u=que[front++];
if(front==MAXN)front=;
for(int i= head[u];i!=-; i=edge[i].next){
int v=edge[i].to;
if(edge[i].cap>&& dep[v]==-){
dep[v]=dep[u]+;
que[rear++]=v;
if(rear>=MAXN) rear=;
if(v==end)return ;
}
}
}
return ;
}
int dinic(int start,int end){
int res=;
int top;
int stack[MAXN];
int cur[MAXN];
while(BFS(start,end)){
memcpy(cur,head, sizeof(head));
int u=start;
top=;
while(){
if(u==end){
int min=INF;
int loc;
for(int i=;i<top;i++)
if(min>edge [stack[i]].cap) {
min=edge [stack[i]].cap;
loc=i;
}
for(int i=;i<top;i++){
edge[stack[i]].cap-=min;
edge[stack[i]^].cap+=min;
}
res+=min;
top=loc;
u=edge[stack[top]].from;
}
for(int i=cur[u]; i!=-; cur[u]=i=edge[i].next)
if(edge[i].cap!= && dep[u]+==dep[edge[i].to])
break;
if(cur[u] !=-){
stack [top++]= cur[u];
u=edge[cur[u]].to;
}
else{
if(top==) break;
dep[u]=-;
u= edge[stack [--top] ].from;
}
}
}
return res;
} void build(){
init();
for(int i=;i<n;i++){
for(int j=;j<n;j++){
if(i==j)
addedge(i*,i*+,);
else if(maze[i][j]){
addedge(i*+,j*,INF);
}
}
} } int main(){
int u,v;
while(scanf("%d%d",&n,&m)!=EOF){
memset(maze,false,sizeof(maze));
for(int i=;i<m;i++){
scanf(" (%d,%d)",&u,&v);
maze[u][v]=maze[v][u]=true;
}
int ans=INF;
for(int i=;i<n;i++){
for(int j=i+;j<n;j++){
build();
if(!maze[i][j]){
int res=dinic(i*+,j*);
if(res<ans) ans=res;
if(ans==) break;
}
}
if(ans==) break;
}
if(ans>=n){ printf("%d\n",n); continue; }
printf("%d\n",ans);
}
return ;
}