POJ 3694 Network

求橋，縮點，LCA，還有重邊，之後還要加Q條邊，每次加完後詢問一次橋的個數。。。個人感覺算是比較麻煩的題了。。。

給出N個點，M條邊，保證所有點連通，數據中有重邊，之後加入Q條邊，每次加完後，輸出一個整數代表圖中剩余的橋的數量。

首先找出所有的橋，將橋刪除，然後將雙連通分量進行縮點，用橋將這些點連接起來，然後用LCA處理。

對於每條新加入的邊，首先判斷其兩端點被縮進了哪個點，設其分別被縮進了 u, v。

則因這條邊而消除的橋，必為 [ LCA（u,v） , u ] 和 [ LCA(u,v) , v ]兩條路上的橋。

#include 
#include 
#include 
#include 
#include 
#include 
#include 

#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<