Network（poj 3694）

题意：一个无向图可以有重边，下面q个操作，每次在两个点间连接一条有向边，每次连接后整个无向图还剩下多少桥（注意是要考虑之前连了的边，每次回答是在上一次的基础之上）

/*

  tarjan+LCA

  先用tarjan缩点，那么这个图就会变成一棵树，当我们连起不在同一节点时，就相当于

  把树上的两个节点连了起来，这两个节点同他们的公共祖先会形成一个新的缩点，每次统计

  桥的个数。

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#define M 200010

using namespace std;

int n,m,num,head[M],low[M],dfn[M],topt;

int s[M],top,f[M],sum,belong[M],cnt,cas;

int Num,Head[M],fa[M],c[M],vis[M];

struct node{int v,pre;}e[M*];

struct Node{int v,pre;}E[M*];

void Add(int from,int to)

{

    e[num].v=to;

    e[num].pre=head[from];

    head[from]=num++;

}

void add(int from,int to)

{

    E[Num].v=to;

    E[Num].pre=Head[from];

    Head[from]=Num++;

}

void Tarjan(int x,int fa)

{

    low[x]=dfn[x]=++topt;

    s[++top]=x;f[x]=;

    for(int i=head[x];i!=-;i=e[i].pre)

    {

        int v=e[i].v;

        if(i==(fa^))continue;

        if(dfn[v]==)

        {

            Tarjan(v,i);low[x]=min(low[x],low[v]);

        }

        else if(f[v])low[x]=min(low[x],dfn[v]);

    }

    if(low[x]==dfn[x])

    {

        sum++;

        while(x!=s[top])

        {

            f[s[top]]=;belong[s[top]]=sum;top--;

        }

        f[s[top]]=;belong[s[top]]=sum;top--;

    }

}

void Dfs(int now,int from,int dep)

{

    fa[now]=from;c[now]=dep;

    for(int i=Head[now];i!=-;i=E[i].pre)

      if(E[i].v!=from)

        Dfs(E[i].v,now,dep+);

}

void LCA(int a,int b)

{

    if(c[a]<c[b])swap(a,b);

    int t=c[a]-c[b];

    for(int i=;i<=t;i++)

    {

        if(vis[a]==)cnt--;

        vis[a]=;a=fa[a];

    }

    while(a!=b)

    {

        if(vis[a]==)cnt--;

        vis[a]=;a=fa[a];

        if(vis[b]==)cnt--;

        vis[b]=;b=fa[b];

    }

}

int main()

{

    while()

    {

        scanf("%d%d",&n,&m);

        if(n==&&m==)break;

        memset(head,-,sizeof(head));

        memset(Head,-,sizeof(Head));

        memset(low,,sizeof(low));

        memset(dfn,,sizeof(dfn));

        memset(f,,sizeof(f));

        memset(belong,,sizeof(belong));

        memset(vis,,sizeof(vis));

        memset(c,,sizeof(c));

        memset(fa,,sizeof(fa));

        memset(s,,sizeof(s));

        Num=num=topt=sum=;

        int u,v;

        for(int i=;i<=m;i++)

        {

            scanf("%d%d",&u,&v);

            Add(u,v);Add(v,u);

        }

        for(int i=;i<=n;i++)

          if(dfn[i]==)

            Tarjan(i,-);

        for(int u=;u<=n;u++)

          for(int i=head[u];i!=-;i=e[i].pre)

            if(belong[u]!=belong[e[i].v])

              add(belong[u],belong[e[i].v]);

        Dfs(,,);cnt=sum-;

        scanf("%d",&m);

        printf("Case %d:\n",++cas);

        for(int i=;i<=m;i++)

        {

            scanf("%d%d",&u,&v);

            int U=belong[u];

            int V=belong[v];

            if(U==V)

            {

                printf("%d\n",cnt);continue;

            }

            LCA(U,V);

            printf("%d\n",cnt);

        }

    }

    return ;

}