题意：给出一个n个节点和m条边的图，求该图的顶点连通度。
分析： 顶点连通度的求解可以转换为网络最大流问题。
（1）原图G中的每个顶点v变成网络中的两个顶点v‘和v’‘，顶点v’至v''有一个条弧（有向边）连接，弧容量为1；
（2）原图G中的每条边e=uv，在网络中有两条弧e'=u''v',e''=v''u'与之对应，e'弧容量为oo（无穷） ，e''弧容量为oo(无穷)
（3）A''为源点，B'为汇点，枚举所有汇点，求最小割最小的那个
AC代码如下：
1 #include<cstdio> 2 #include<cstring> 3 const int N=100+5; 4 const int INF=0x3f3f3f3f; 5 struct EDGE{ 6 int v,w,next; 7 }edge[N*N],edge2[N*N]; 8 int g; 9 int first[N],numh[N],h[N],curedge[N],pre[N]; 10 //int first[N],gap[N],pre[N],dis[N],cur[N]; 11 int min(int a,int b) 12 { 13 return a<b?a:b; 14 } 15 void AddEdge(int u,int v,int w) 16 { 17 edge[g].v=v; 18 edge[g].w=w; 19 edge[g].next=first[u]; 20 first[u]=g++; 21 edge[g].v=u; //反向边 22 edge[g].w=0; 23 edge[g].next=first[v]; 24 first[v]=g++; 25 } 26 int sap(int s,int t,int n,EDGE edge[]) 27 { 28 int cur_flow,u,tmp,neck,i; 29 int flow_ans=0; 30 memset(h,0,sizeof(h)); 31 memset(numh,0,sizeof(numh)); 32 memset(pre,-1,sizeof(pre)); 33 for(i=0;i<n;i++) 34 curedge[i]=first[i]; 35 numh[0]=n; 36 u=s; 37 while(h[s]<n) 38 { 39 if(u==t) 40 { 41 cur_flow=INF+1; //注意：要+1 42 for(i=s;i!=t;i=edge[curedge[i]].v) 43 { 44 if(cur_flow>edge[curedge[i]].w) 45 { 46 neck=i; 47 cur_flow=edge[curedge[i]].w; 48 } 49 } 50 for(i=s;i!=t;i=edge[curedge[i]].v) 51 { 52 tmp=curedge[i]; 53 edge[tmp].w-=cur_flow; 54 edge[tmp^1].w+=cur_flow; 55 } 56 flow_ans+=cur_flow; 57 u=neck; 58 } 59 for(i=curedge[u];i!=-1;i=edge[i].next) 60 { 61 if(edge[i].w&&h[u]==h[edge[i].v]+1) 62 break; 63 } 64 if(i!=-1) 65 { 66 curedge[u]=i; 67 pre[edge[i].v]=u; 68 u=edge[i].v; 69 } 70 else 71 { 72 if(0==--numh[h[u]]) 73 break; 74 curedge[u]=first[u]; 75 for(tmp=n,i=first[u];i!=-1;i=edge[i].next) 76 { 77 if(edge[i].w) 78 tmp=min(tmp,h[edge[i].v]); 79 } 80 h[u]=tmp+1; 81 numh[h[u]]++; 82 if(u!=s) 83 u=pre[u]; 84 } 85 } 86 return flow_ans; 87 } 88 /*int cou; 89 int sap(int s,int t,int n,EDGE edge[]) 90 { 91 memset(cur,0,sizeof(cur)); 92 memset(pre,0,sizeof(pre)); 93 int flow=0,i; 94 int u=pre[s]=s; 95 cou=n; 96 for(i=0;i<cou;i++) 97 { 98 cur[i]=first[i]; 99 dis[i]=gap[i]=0; 100 } 101 gap[0]=cou; 102 int aug=INF; 103 while(dis[s]<cou) 104 { 105 bool flag=true; 106 for(int j=cur[u];j!=-1;j=cur[u]=edge[j].next){ 107 int v=edge[j].v; 108 if(edge[j].w>0&&dis[u]==dis[v]+1) 109 { 110 flag=false; 111 pre[v]=u; 112 u=v; 113 if(aug>edge[j].w) 114 aug=edge[j].w; 115 if(u==t) 116 { 117 flow+=aug; 118 while(u!=s){ 119 u=pre[u]; 120 edge[cur[u]].w-=aug; 121 edge[cur[u]^1].w+=aug; 122 } 123 aug=INF; 124 } 125 break; 126 } 127 } 128 if(!flag) 129 continue; 130 int minh=cou; 131 for(int k=first[u];k!=-1;k=edge[k].next) 132 { 133 int v=edge[k].v; 134 if(edge[k].w>0&&minh>dis[v]){ 135 minh=dis[v]; 136 cur[u]=k; 137 } 138 } 139 if((--gap[dis[u]])==0) 140 break; 141 gap[dis[u]=minh+1]++; 142 u=pre[u]; 143 } 144 return flow; 145 }*/ 146 int main() 147 { 148 // printf("%d ",INF); 149 int i,n,m,u,v,k; 150 while(scanf("%d%d",&n,&m)!=EOF) 151 { 152 if(m==0) 153 { 154 if(n==1) 155 printf("1 "); 156 else 157 printf("0 "); 158 continue; 159 } 160 g=0; 161 memset(first,-1,sizeof(first)); 162 for(i=0;i<n;i++) 163 AddEdge(i,i+n,1); 164 for(i=0;i<m;i++) 165 { 166 scanf(" (%d,%d)",&u,&v); 167 AddEdge(u+n,v,INF); 168 AddEdge(v+n,u,INF); 169 } 170 int ans=INF; 171 for(i=1;i<n;i++) 172 { 173 for(k=0;k<g;k++) 174 edge2[k]=edge[k]; 175 ans=min(ans,sap(0+n,i,n*2,edge2)); 176 } 177 if(ans==INF) 178 ans=n; 179 printf("%d ",ans); 180 } 181 return 0; 182 }