HDU - 3313 Key Vertex(找关键点)

Key Vertex

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1651 Accepted Submission(s): 428

Problem Description
You need walking from vertex S to vertex T in a graph. If you remove one vertex which stops you from walking from S to T, that vertex we call as key vertex. Now you are given a directed graph, S and T, and you should tell us how many key vertexes are there in the graph.
Please notice that S and T are key vertexes and if S cannot walking to T by the directed edge in the initial graph then all vertexes becomes to key vertexes.

Input
The input consists of multiply test cases. The first line of each test case contains two integers, n(0 <= n <= 100000), m(0 <= m <= 300000), which are the number of vertexes and the number of edge. Each of the next m lines consists of two integers, u, v(0 <= u, v < n; u != v), indicating there exists an edge from vertex u to vertex v. There might be multiple edges but no loops. The last line of each test case contains two integers, S, T(0 <= S, T < n, S != T).

Output
Output the number of key vertexes in a single line for each test case.

Sample Input
6 6
0 1
1 2
1 3
2 4
3 4
4 5
0 5

Sample Output
4

Author
momodi

Source
HDOJ Monthly Contest – 2010.02.06

图论好题！！！！

题目大意：给出一个起点和一个终点，问我们从起点到终点的关键点有多少个，关键点就是去除之后不能从起点到终点了。

我们可以先bfs，随便找到一条路径，然后关键点必然在这条路径上。为什么呢？如果不在这条路径上，必然还有我们找到这条路径可以到达终点，反证！！

所以我们再bfs一次，我们从起点开始，找点，每次把非第一次找到的路径上的点加入到队列当中。如果找到了第一次找到的路径上的点，我们就记录最远的路径点。最后记录当前的点是什么。

最后bfs结束时，如果找到终点了就退出。

不然我们找到的当前路径上最远的点就是关键点。然后我们从这个点开始继续找，直到到终点。

修改：注意上面的关键点是错的！！！！！！

只有当我们找到最远的点前面的路径上的点也不能到达更远的点时，才能说明这个点是关键点，网上许多代码都是错的！！数据太水了，可以看下面这个数据：

原因很简单，我们找到的第一条路径可能把其他能够到达终点的路径切割了。

复杂度O(n+m)

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10,M=8e5+10;
int n,m,s,t,v[N],vis[N],d[N],flag,st;
int head[N],nex[M],to[M],tot;
inline void add(int a,int b){
	to[++tot]=b; nex[tot]=head[a]; head[a]=tot;
}
inline void init(){
	tot=flag=0;	memset(head,0,sizeof head);
	memset(vis,0,sizeof vis);	memset(d,0,sizeof d);
}
void bfs(){
	queue<int> q;	q.push(s);	flag=0;	d[s]=1;
	while(q.size()){
		int u=q.front();	q.pop();
		for(int i=head[u];i;i=nex[i]){
			if(!d[to[i]]){
				d[to[i]]=d[u]+1;	q.push(to[i]);	v[to[i]]=u;
				if(to[i]==t)	flag=1;
			}
			if(flag)	break;
		}
		if(flag)	break;
	}
}
int check(int ed,int mx){
	queue<int> q;	int dst=0,p=0;	
	for(int i=v[ed];i!=st;i=v[i])	q.push(i);	st=ed;
	while(q.size()){
		int u=q.front();	q.pop();
		for(int i=head[u];i;i=nex[i]){
			if(vis[to[i]]==-1&&dst<d[to[i]]){
				dst=d[to[i]];	p=to[i];
			}
			if(!vis[to[i]]){
				vis[to[i]]=1;	q.push(to[i]);
			}
		}
	}
	if(dst<=mx)	return -1;
	else return p;
}
int solve(){
	int p=s,dst=0,res=2;
	while(1){
		queue<int> q;	q.push(p);
		while(q.size()){
			int u=q.front();	q.pop();
			for(int i=head[u];i;i=nex[i]){
				if(vis[to[i]]==-1&&dst<d[to[i]]){
					p=to[i];	dst=d[to[i]];
				}
				if(!vis[to[i]]){
					vis[to[i]]=1;	q.push(to[i]);
				}
			}
		}
		if(p==t)	return res;
		int ok=check(p,dst);
		if(ok==-1)	res++;
		else	p=ok;
		dst=d[p];
	}
}
signed main(){
	while(~scanf("%d %d",&n,&m)){
		init();
		for(int i=1;i<=m;i++){
			int a,b;	scanf("%d %d",&a,&b);	add(a+1,b+1);
		}
		scanf("%d %d",&s,&t);	++s; ++t;	st=s;
		bfs();
		if(!flag){
			printf("%d\n",n);	continue;
		}
		for(int i=t;i!=s;i=v[i])	vis[i]=-1;	vis[s]=-1;
		printf("%d\n",solve());
	}
	return 0;
}