题意：给出一张有向图。如果一个节点在图中被删除后，就能使得从S->T不连通，则称这个点key vertex。问这张图中有多少个点是key vertex。
网上有两种说法，一种是网络流，就是拆点建图，求最小割，为了限制增广次数，把S、T拆点后的容量限制到2，这样一来跑最大流得到maxflow，如果maxflow=0，则说明全部的点都可以是key vertex，如果maxflow=2，则说明只有S、T是key vertex，如果maxflow=1的话，就需要到残量网络中去找了。怎么找呢？首先从S出发始寻找在残量网络中可以到达的所有的点，把它们保存在一个队列里，并记上vis标记，然后把这个队列里的点u，我们判断从u出发的所有已经满流的正向边指向的点是否在BFS的时候被访问过，如果没有被访问过，那这个点就是一个key vertex，找到一个key vertex以后就可以退出这轮循环了。然后以刚才找到的key vertex为src再做BFS，这样一直迭代下去，直到找到了一个为汇点T的key vertex。
另外一种说法比网络流好写多了，先找一条最短路，并记录路径。然后也是从S开始找，找一个距离S最远的且在最短路路径上的点K，这个K就是一个key vertex。然后继续，以K为src去找一个距离K最远的且在最短路路径上的点K'，直到找到T为止。
贴一下网络流写的代码：
1 #pragma comment(linker, "/STACK:1024000000,1024000000") 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 #define INF 1<<30 7 #define maxn 200010 8 #define maxm 1000000 9 using namespace std; 10 11 int v[maxm],next[maxm],w[maxm]; 12 int first[maxn],d[maxn],work[maxn],q[maxn],vis[maxn]; 13 int e,S,T,n,m,rear,cnt; 14 15 void init(){ 16 e = 0; 17 memset(first,-1,sizeof(first)); 18 } 19 20 void add_edge(int a,int b,int c){ 21 v[e] = b;next[e] = first[a];w[e] = c;first[a] = e++; 22 v[e] = a;next[e] = first[b];w[e] = 0;first[b] = e++; 23 } 24 25 int bfs(){ 26 rear = 0; 27 memset(d,-1,sizeof(d)); 28 d[S] = 0;q[rear++] = S; 29 for(int i = 0;i < rear;i++){ 30 for(int j = first[q[i]];j != -1;j = next[j]) 31 if(w[j] && d[v[j]] == -1){ 32 d[v[j]] = d[q[i]] + 1; 33 q[rear++] = v[j]; 34 if(v[j] == T) return 1; 35 } 36 } 37 return 0; 38 } 39 40 int dfs(int cur,int a){ 41 if(cur == T) return a; 42 for(int &i = work[cur];i != -1;i = next[i]){ 43 if(w[i] && d[v[i]] == d[cur] + 1) 44 if(int t = dfs(v[i],min(a,w[i]))){ 45 w[i] -= t;w[i^1] += t; 46 return t; 47 } 48 } 49 return 0; 50 } 51 52 int dinic(){ 53 int ans = 0; 54 while(bfs()){ 55 memcpy(work,first,sizeof(first)); 56 while(int t = dfs(S,INF)) ans += t; 57 } 58 return ans; 59 } 60 61 void bfs(int src){ 62 rear = 0; 63 vis[src] = 1,q[rear++] = src; 64 for(int i = 0;i < rear;i++){ 65 for(int j = first[q[i]];j != -1;j = next[j]) 66 if(w[j] && !vis[v[j]]){ 67 vis[v[j]] = 1; 68 q[rear++] = v[j]; 69 } 70 } 71 } 72 73 void solve(){ 74 memset(vis,0,sizeof(vis)); 75 w[first[S]] = 0,w[first[T-n]] = 0; 76 int src = S; 77 bool flag = 1; 78 while(1){ 79 bfs(src); 80 flag = 1; 81 for(int i = 0;i < rear;i++){ 82 if(!flag) break; 83 for(int j = first[q[i]];j != -1;j = next[j]){ 84 if((!(j&1)) && (!w[j]) && (!vis[v[j]])){ 85 cnt++; 86 src = v[j]; 87 flag = 0; 88 if(src == T) return; 89 } 90 } 91 } 92 } 93 } 94 int main() 95 { 96 while(scanf("%d%d",&n,&m) == 2){ 97 init(); 98 for(int i = 0;i < m;i++){ 99 int a,b; 100 scanf("%d%d",&a,&b); 101 add_edge(a+n,b,INF); 102 } 103 scanf("%d%d",&S,&T); 104 for(int i = 0;i < n;i++){ 105 if(i != S && i != T) add_edge(i,i+n,1); 106 else add_edge(i,i+n,2); 107 } 108 T += n; 109 int maxflow = dinic(); 110 if(maxflow == 2){ 111 printf("2 "); 112 }else if(maxflow == 0){ 113 printf("%d ",n); 114 }else{ 115 cnt = 0; 116 solve(); 117 printf("%d ",cnt); 118 } 119 } 120 return 0; 121 }