POJ 3694 Network（雙連通分量縮點 + 路徑壓縮）

題目連結：Click here~~

題意：

n 個點 m 條邊的無向圖，之後有若幹次操作，問每次添加一條邊後，圖上還剩多少個橋邊（操作是累積的）。

解題思路：

先将無向圖的 邊-雙連通分量 縮點，縮點後重建立圖，則變為一顆樹，樹的每條邊就可以看做橋邊。不妨設每次添加的邊為 <u,v> 。

1> 如果之前 u,v 在同一個雙連通分量裡，則顯然不會對結果産生影響。

2> 如果不在，相當于在樹中選取兩點，連了一條邊，進而形成一個環，環中的點會變成一個雙連通分量。對結果産生的影響取決于環上的邊數。

不難發現，這個環的路徑就是： u -> LCA(u,v) -> v 。

如果操作不累積，容易想到重建立圖後先轉化成一棵樹，然後預處理出每個點的深度，離線預處理出兩兩的 LCA，影響就是2*dep[lca] - dep[u] - dep[v]。

但此題是操作累積的，就不能這樣做了。搜了題解，大概懂别人的思路了。

首先，找 LCA(u,v) 相當于 u,v 兩個點一起向上爬，直到爬到同一個點 w 即為這兩點的 LCA，統計共爬了多少邊。我們把這種做法叫做 climb 吧。

我們來考慮兩個點爬到 LCA 後，會對之後的操作産生什麼影響。

之後的點如果再次爬之前爬過的路徑，不會再對結果産生影響了。

既然爬之前爬過的路徑這麼費力不讨好，是不是能夠想到一個好的方法，讓它一次登頂？

于是這點就可以很巧妙的和并查集的路徑壓縮聯系到一起。大家看代碼體會吧。

#include <stack>
#include <vector>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

template<int N,int M>
struct Graph{
    int top;
    struct Vertex{
        int head;
    }V[N];
    struct Edge{
        int v,next;
    }E[M];
    void init(){
        memset(V,-1,sizeof(V));
        top = 0;
    }
    void add_edge(int u,int v){
        E[top].v = v;
        E[top].next = V[u].head;
        V[u].head = top++;
    }
};

const int N = 1e5 + 5;

Graph<N,N*4> g,gg;

int dfn[N],low[N],belong[N];
int bccId,dfsId;

bool cutP[N],cutE[N*4];

vector<int> bcc[N];

void dfs(int pre,int u)
{
    dfn[u] = low[u] = ++dfsId;
    int child = 0;
    for(int i=g.V[u].head;~i;i=g.E[i].next){
        int v = g.E[i].v;
        if(v == pre || dfn[v] > dfn[u])
            continue;
        if(!dfn[v]){
            child++;
            dfs(u,v);
            low[u] = min(low[u],low[v]);
            if(pre != -1 && low[v] >= dfn[u] || pre == -1 && child > 1)
                cutP[u] = true;
        }
        else
            low[u] = min(low[u],dfn[v]);
        if(low[v] > dfn[u]){
            cutE[i] = true;
        }
    }
}

void get_bcc_p(int n)
{
    dfsId = bccId = 0;
    memset(dfn,0,sizeof(dfn));
    memset(cutP,false,sizeof(cutP));
    memset(cutE,false,sizeof(cutE));
    memset(belong,-1,sizeof(belong));
    for(int i=1;i<=n;i++)
        if(!dfn[i])
            dfs(-1,i);
}

bool vis[N];

void dfs2(int u)
{
    vis[u] = true;
    belong[u] = bccId;
    bcc[bccId].push_back(u);
    for(int i=g.V[u].head;~i;i=g.E[i].next){
        int v = g.E[i].v;
        if(!vis[v] && !cutE[i] && !cutE[i^1])
            dfs2(v);
    }
}

void get_bcc_e(int n)
{
    bccId = 0;
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=n;i++){
        if(vis[i])
            continue;
        bcc[++bccId].clear();
        dfs2(i);
    }
}

int father[N],dep[N];

void dfss(int u,int depth)
{
    vis[u] = true;
    dep[u] = depth;
    for(int i=gg.V[u].head;~i;i=gg.E[i].next)
    {
        int v = gg.E[i].v;
        if(!vis[v]){
            father[v] = u;
            dfss(v,depth+1);
        }
    }
}

void rebuild(int n)
{
    for(int u=1;u<=n;u++)
        for(int i=g.V[u].head;~i;i=g.E[i].next){
            int v = g.E[i].v;
            if(belong[u] != belong[v])
                gg.add_edge(belong[u],belong[v]),
                gg.add_edge(belong[v],belong[u]);
        }
    memset(vis,false,sizeof(vis));
    father[1] = 0;
    dfss(1,0);
}

namespace ufSet
{
    //const int N = 1e5 + 5;
    int pre[N];
    void init(){
        memset(pre,-1,sizeof(pre));
    }
    int root(int x){
        return pre[x] == -1 ? x : pre[x] = root(pre[x]);
    }
    bool gather(int a,int b){
        int r1 = root(a);
        int r2 = root(b);
        if(r1 == r2)
            return false;
        else
            pre[r1] = r2;
            return true;
    }
}

using namespace ufSet;

 int climb(int a,int b){
    int ret = 0;
    while(1){
        a = root(a);
        b = root(b);
        if(a == b)
            break;
        if(dep[a] > dep[b])
            gather(a,father[a]);
        else
            gather(b,father[b]);
        ++ret;
    }
    return ret;
}

void debug()
{
    for(int i=1;i<=bccId;i++)
        for(int j=0;j<(int)bcc[bccId].size();j++)
            printf("%d->%d%c",bcc[i][j],i,j==(int)bcc[bccId].size()-1?'\n':' ');
}

int main()
{
    int n,m,Q,ncase = 0;
    while(scanf("%d%d",&n,&m),n||m)
    {
        g.init();
        gg.init();
        ufSet::init();
        while(m--)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            g.add_edge(u,v);
            g.add_edge(v,u);
        }
        get_bcc_p(n);
        get_bcc_e(n);
        rebuild(n);
        scanf("%d",&Q);
        int ans = bccId - 1;
        printf("Case %d:\n",++ncase);
        while(Q--)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            ans -= climb(belong[u],belong[v]);
            printf("%d\n",ans);
        }
        puts("");
    }
    return 0;
}