Key Vertex

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

题意：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\n")

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",n);

            continue;

        }

        int ans=0;

        mem(vis,false);

        while (start!=End)

        {

//            printf("++%d\n",start);

            dfs(start);

//            printf("--%d\n",start);

            ans++;

        }

        printf("%d\n",ans+1);

    }

    return 0;

}