Key Vertex
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 1347 Accepted Submission(s): 305
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.
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
Recommend
题意：n个点m条边的有向图，问存在多少个点使得去掉这个点及相连的边后起点和终点不再联通。
思路：非常easy想到Tarjan算法求割点，可是略微一想就会知道不正确，由于Tarjan算法求的是整个图的割点，而这里题目仅仅要求能使起点和终点不连通的点。
然后我们先用SPFA求出一条最短路径，那么要求的“割点”一定都在这条路径上，细致想想就会知道。求出最短路径后从起点dfs。直到找到距离start最远的且在最短路径上的点v。那么v就是一个割点，这时更新start。令start=v，反复上面的dfs直到终点。
为什么这么做呢？你能够在纸上画绘图就会非常快明确了。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#pragma comment (linker,"/STACK:102400000,102400000")
#define pi acos(-1.0)
#define eps 1e-6
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define FRE(i,a,b) for(i = a; i <= b; i++)
#define FREE(i,a,b) for(i = a; i >= b; i--)
#define FRL(i,a,b) for(i = a; i < b; i++)
#define FRLL(i,a,b) for(i = a; i > b; i--)
#define mem(t, v) memset ((t) , v, sizeof(t))
#define sf(n) scanf("%d", &n)
#define sff(a,b) scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define pf printf
#define DBG pf("Hi
")
typedef long long ll;
using namespace std;
#define INF 0x3f3f3f3f
#define mod 1000000009
const int maxn = 1005;
const int MAXN = 100010;
const int MAXM = 300010;
const int N = 1005;
int n,m;
struct Edge
{
int u,v,next;
}edge[MAXM];
int head[MAXN],dist[MAXN],pre[MAXN];
bool inq[MAXN],mark[MAXN],vis[MAXN];
int num,start,End;
void init()
{
num=0;
mem(head,-1);
}
void addedge(int u,int v)
{
edge[num].u=u;
edge[num].v=v;
edge[num].next=head[u];
head[u]=num++;
}
bool SPFA(int s,int t)
{
mem(inq,false);
mem(mark,false);
mem(dist,INF);
mem(pre,-1);
dist[s]=0;
inq[s]=true;
queue<int>Q;
Q.push(s);
while(!Q.empty())
{
int u=Q.front();
Q.pop();
inq[u]=false;
for (int i=head[u];~i;i=edge[i].next)
{
int v=edge[i].v;
if (dist[v]>dist[u]+1)
{
dist[v]=dist[u]+1;
pre[v]=u;
if (!inq[v])
{
inq[v]=true;
Q.push(v);
}
}
}
}
if (dist[t]>=INF) return false;
int x=t;
mem(mark,false);
while (x!=-1)
{
mark[x]=true;
x=pre[x];
}
return true;
}
void dfs(int u)
{
if (vis[u]) return ;
vis[u]=true;
for (int i=head[u];~i;i=edge[i].next)
{
int v=edge[i].v;
if (mark[v]&&dist[v]>=dist[start]) //由于有重边，所以一定要加等号，坑了我好久=-=
{
start=v;
continue;
}
dfs(v);
}
return ;
}
//void dfs(int u) //第二种写法
//{
// for (int i=head[u];~i;i=edge[i].next)
// {
// int v=edge[i].v;
// if (vis[v]) continue;
// vis[v]=true;
// if (mark[v]&&dist[v]>dist[start])
// {
// start=v;
// continue;
// }
// dfs(v);
// }
// return ;
//}
int main()
{
#ifndef ONLINE_JUDGE
freopen("C:/Users/lyf/Desktop/IN.txt","r",stdin);
#endif
int i,j,u,v;
while (~sff(n,m))
{
init();
for (i=0;i<m;i++)
{
sff(u,v);
addedge(u,v);
}
sff(start,End);
if (!SPFA(start,End))
{
pf("%d
",n);
continue;
}
int ans=0;
mem(vis,false);
while (start!=End)
{
// printf("++%d
",start);
dfs(start);
// printf("--%d
",start);
ans++;
}
printf("%d
",ans+1);
}
return 0;
}