hdu 3313 Key Vertex

一个有向图，给定起点和终点，问他的割点数，割点是指去掉这个点能使得s和t不通。s和t也是割点。

先找一条从s到t的任意路径，假如没有路的话，那么割点数为n，如果找到了一条路径的话，将这条路径上的点标记出来，首先明确一点，割点肯定不会再路径外的点上，因为去掉外面的点后，还是有刚刚那条路径的。所以现在就要看路径上的每个点是不是割点。只要把路径上的点去掉，然后从s进行bfs，路径上的点不能走，这样进行bfs的记录能探访到最远的在路径上的点为ans，假如ans等于t，那么只有两个割点s和t，如果bfs结束后ans不等于t，那么ans就是一个割点。因为去掉该点之后，无法走到之后的点了。然后从ans开始继续进行bfs直到访问到t为止。

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
#define maxn 100000+10
#define maxm 300000+100
#define inf 1000000000
struct Edge
{
    int u,v,next;
}e[maxm];
int head[maxn],cnt;
int dis[maxn],mk[maxn];
int pre[maxn];
int in[maxn];
int n,m;
int s,t;
void add(int u,int v)
{
    e[cnt].u=u;
    e[cnt].v=v;
    e[cnt].next=head[u];
    head[u]=cnt++;
}

int solve()
{
    int u,v,i;
    memset(pre,-1,sizeof(pre));
    memset(in,0,sizeof(in));
    for(i=0;i<n;i++) dis[i]=-1;
    dis[s]=0;
    queue <int> Q;
    Q.push(s);
    while(!Q.empty())
    {
        u=Q.front();Q.pop();
        for(i=head[u];i!=-1;i=e[i].next)
        {
            v=e[i].v;
            if(dis[v]==-1)
            {
                dis[v]=dis[u]+1;
                pre[v]=u;
                Q.push(v);
            }
        }
    }
    if(dis[t]==-1) return n;
    for(i=t;i!=s;i=pre[i]) in[i]=-1;
    in[s]=-1;
    int sum=1;
    while(1)
    {
        int ans=-1,maxdis=-1;
        Q.push(s);
        while(!Q.empty())
        {
            u=Q.front();Q.pop();
            for(i=head[u];i!=-1;i=e[i].next)
            {
                v=e[i].v;
                if(in[v]==-1&&dis[v]>maxdis)
                {
                    ans=v;
                    maxdis=dis[v];
                }
                else if(in[v]==0)
                {
                    Q.push(v);
                    in[v]=1;
                }
            }
        }
        sum++;
        if(ans==t) return sum;
        s=ans;
    }
}

int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        int i,j;
        int u,v;
        for(i=0;i<n;i++) head[i]=-1;
        cnt=0;
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&u,&v);
            add(u,v);
        }
        scanf("%d%d",&s,&t);
        printf("%d
",solve());
    }
    return 0;
}