有向圖G中求頂點(diǎn)連通度：
1、獨(dú)立軌P(A,B)
2、Menger定理：無向圖G的頂點(diǎn)連通度
k(G)=V|G|-1 G是完全圖，min <A,B>! in E（P（A，B））else
3、用最大流法求P（A，B）。
4、建圖：e=(u,v)分成e'=(u'',v')和e''=(u',v'');e'=e''=inf。
得好好研究研究這些圖論的原理，搞明白。《圖論》這本書，講得不行啊！！！！還是得好好學(xué)習(xí)《算法導(dǎo)論》
最大流，好要好好學(xué)！
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define maxn 105
#define inf 105
#define min(x,y) (x<y?x:y)
#define max(x,y) (x>y?x:y)
using namespace std;
int map[maxn][maxn];
int N,M;
int max_flow(int num,int map[][maxn],int source,int sink)
{
int que[maxn],head,tail;
int pre[maxn],min_flow[maxn];
int flow[maxn][maxn];
int ans=0;
memset(flow,0,sizeof(flow));
while (1)
{
head=0;tail=1;
que[1]=source;
memset(pre,-1,sizeof(pre));
min_flow[source]=inf;
pre[source]=-2;
while (head<tail)
{
int temp=que[++head];
for (int i=0;i<num;i++)
{
if (pre[i]==-1 && flow[temp][i]<map[temp][i])
{
que[++tail]=i;
pre[i]=temp;
min_flow[i]=min(min_flow[temp],(map[temp][i]-flow[temp][i]));
}
}
if (pre[sink]!=-1)
{
int k=sink;
while (pre[k]>=0)
{
flow[pre[k]][k]+=min_flow[sink];
flow[k][pre[k]]=-flow[pre[k]][k];
k=pre[k];
}
break;
}
}
if (pre[sink]==-1)
return ans;
else
ans+=min_flow[sink];
}
}
int main()
{
while (scanf("%d%d",&N,&M)==2)
{
int u,v,ans;
int i;
memset(map,0,sizeof(map));
for (i=0;i<N;i++)
map[i][i+N]=1;
for (i=0;i<M;i++)
{
scanf(" (%d,%d)",&u,&v);
map[u+N][v]=map[v+N][u]=inf;
}
ans=inf;
for (i=1;i<N;i++)
{
ans=min(ans,max_flow(N*2,map,0+N,i)); //這里沒有搞明白怎么是<N , i>呢？？？
}
if (ans==inf)
ans=N;
printf("%d\n",ans);
}
return 0;
}
圖論。