POJ 3694 Network

求桥，缩点，LCA，还有重边，之后还要加Q条边，每次加完后询问一次桥的个数。。。个人感觉算是比较麻烦的题了。。。

给出N个点，M条边，保证所有点连通，数据中有重边，之后加入Q条边，每次加完后，输出一个整数代表图中剩余的桥的数量。

首先找出所有的桥，将桥删除，然后将双连通分量进行缩点，用桥将这些点连接起来，然后用LCA处理。

对于每条新加入的边，首先判断其两端点被缩进了哪个点，设其分别被缩进了 u, v。

则因这条边而消除的桥，必为 [ LCA（u,v） , u ]  和 [ LCA(u,v) , v ]两条路上的桥。

桥与双连通分量的求法：

http://blog.csdn.net/zmx354/article/details/18503659

LCA：

http://blog.csdn.net/zmx354/article/details/18076975

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cmath>
#include <algorithm>

#define LL long long
#define PI (acos(-1.0))
#define EPS (1e-10)

using namespace std;

const int MAXN = 100010;

struct N
{
    int v,next;
}Edge[MAXN*4],Lca_Edge[MAXN*4];

struct E
{
    int u,v;
}Bridge[MAXN*2];

int Top_Edge,Top_Bridge,Lca_Top_Edge,Lca_Time;

int head[MAXN];
int Lca_Head[MAXN];
int mv[MAXN];
int depth[MAXN];
int Lca_Depth[MAXN];
int Lca_Vis[MAXN];
int Point[MAXN*2];
int st[MAXN*8];
int father[MAXN];
int root[MAXN];
bool Cut[MAXN];

void link(int u,int v)
{
    Edge[++Top_Edge].v = v;
    Edge[Top_Edge].next = head[u];
    head[u] = Top_Edge;
}

void Lca_Link(int u,int v)
{
    Lca_Edge[++Lca_Top_Edge].v = v;
    Lca_Edge[Lca_Top_Edge].next = Lca_Head[u];
    Lca_Head[u] = Lca_Top_Edge;
}

int Find(int x)
{
    while(x != father[x])
        x = father[x];
    return x;
}

void Merge(int u,int v)
{
    int fu = Find(u);
    int fv = Find(v);

    if(fu != fv)
    {
        father[fu] = fv;
    }
}

int Dfs(int s,int f,int h)
{
    mv[s] = 1;//表示灰色，即已开始DFS且正在等待回溯

    depth[s] = h;

    int p,Temp_Depth,Min_Depth = MAXN;
    bool Cover = false;

    for(p = head[s];p != -1;p = Edge[p].next)
    {
        if(Edge[p].v != f || Cover)
        {
            if(mv[Edge[p].v] == 0)
            {
                Temp_Depth = Dfs(Edge[p].v,s,h+1);

                if(Temp_Depth < Min_Depth)
                    Min_Depth = Temp_Depth;
            }
            else if(mv[Edge[p].v] == 1)
            {
                if(depth[Edge[p].v] < Min_Depth)
                    Min_Depth = depth[Edge[p].v];
            }
        }
        else
            Cover = true;
    }

    if(f != -1 && Min_Depth >= depth[s])
    {
        Bridge[Top_Bridge].u = f;
        Bridge[Top_Bridge].v = s;
        Top_Bridge++;
    }
    else if(f != -1)
    {
        Merge(f,s);
    }

    return Min_Depth;
}

void Lca_Dfs(int s,int h)
{
    Lca_Depth[s] =  h;
    Point[Lca_Time] = s;
    Lca_Vis[s] = Lca_Time++;

    for(int p = Lca_Head[s]; p != -1; p = Lca_Edge[p].next)
    {
        if(Lca_Vis[Lca_Edge[p].v] == -1)
        {
            root[Lca_Edge[p].v] = s;
            Cut[Lca_Edge[p].v] = false;
            Lca_Dfs(Lca_Edge[p].v,h+1);
            Point[Lca_Time++] = s;
        }
    }
}

void Init_St(int site,int l,int r)
{
    if(l == r)
    {
        st[site] = Lca_Depth[Point[l]];
        return ;
    }

    int mid = (l+r)>>1;

    Init_St(site<<1,l,mid);
    Init_St(site<<1|1,mid+1,r);

    if(st[site<<1] < st[site<<1|1])
        st[site] = st[site<<1];
    else
        st[site] = st[site<<1|1];
}

int Query_St(int site,int L,int R,int l,int r)
{
    if(l == L && R == r)
    {
        return st[site];
    }

    int mid = (L+R)>>1;

    if(mid < l)
    {
        return Query_St(site<<1|1,mid+1,R,l,r);
    }
    else if(r <= mid)
    {
        return Query_St(site<<1,L,mid,l,r);
    }

    int h1 = Query_St(site<<1,L,mid,l,mid);
    int h2 = Query_St(site<<1|1,mid+1,R,mid+1,r);

    return (h1 < h2 ? h1 : h2);
}

int Query(int u,int v)
{
    int h;

    if(Lca_Vis[u] < Lca_Vis[v])
        h = Query_St(1,0,Lca_Time-1,Lca_Vis[u],Lca_Vis[v]);
    else
        h = Query_St(1,0,Lca_Time-1,Lca_Vis[v],Lca_Vis[u]);



    int i,f,ans = 0;

    //cout<<"h = "<<h<<"  ans = "<<ans<<endl;

    for(i = h,f = u;i < Lca_Depth[u]; ++i)
    {
        if(Cut[f] == false)
        {
            ans++;
            Cut[f] = true;
            f = root[f];
        }
    }

    for(i = h,f = v;i < Lca_Depth[v]; ++i)
    {
        if(Cut[f] == false)
        {
            ans++;
            Cut[f] = true;
            f = root[f];
        }
    }
    //cout<<"ans = "<<ans<<endl;
    return ans;
}

int main()
{
    int n,m,i,u,v,fu,fv;
    int icase = 1;
    while(scanf("%d %d",&n,&m) != EOF && (n||m))
    {
        Top_Bridge = 0,Top_Edge = -1,Lca_Top_Edge = -1,Lca_Time = 0;

        memset(head,-1,sizeof(int)*(n+2));
        memset(mv,0,sizeof(int)*(n+2));//表示白色，即未进行DFS
        memset(Lca_Head,-1,sizeof(int)*(n+2));
        memset(Lca_Vis,-1,sizeof(int)*(n+2));

        for(i = 1;i <= n; ++i)
        {
            father[i] = i;
        }

        for(i = 0;i < m; ++i)
        {
            scanf("%d %d",&u,&v);
            link(u,v);
            link(v,u);
        }

        //计算双连通分量
        Dfs(1,-1,1);

        //cout<<"Top = "<<Top_Bridge<<endl;

        for(i = 0;i < Top_Bridge; ++i)
        {
            fu = Find(Bridge[i].u);
            fv = Find(Bridge[i].v);
            Lca_Link(fu,fv);
            Lca_Link(fv,fu);
        }

        //计算LCA
        Lca_Dfs(Find(1),1);

        //初始化线段书
        Init_St(1,0,Lca_Time-1);

        scanf("%d",&m);
        printf("Case %d:\n",icase++);
        while(m--)
        {
            scanf("%d %d",&u,&v);

            Top_Bridge = Top_Bridge - Query(Find(u),Find(v));

            printf("%d\n",Top_Bridge);
        }
        printf("\n");
    }
    return 0;
}