POJ3694(tarjan缩点+并查集+LCA)

题目大意：在之前的图上面加一条边后剩下桥的数目。

题解思路：在缩点后一条边加完之后，那么两点和它们的最近公共祖先的点形成一个圈就是减少桥的数目，然后通过并查集里的路径压缩把这两个点的到他们的最近公共祖先之间的点的父节点都压缩到最近公共祖先的点。

注意不要用vector容器保存否则会超时用邻接表

题目链接

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<stack>
using namespace std;
const int mx = +;
struct node{
    int v;
    int next;
}E1[mx<<],E2[mx<<];
stack<int>s;
int head1[mx],head2[mx];
int DFN[mx],pre[mx],father[mx],low[mx],sccno[mx],deep[mx];
bool vis[mx];
int tot1,tot2,dfn,cnt,bri;
int n,m;
void init(){
    memset(head1,-,sizeof(head1));
    memset(head2,-,sizeof(head2));
    memset(vis,,sizeof(vis));
    memset(DFN,,sizeof(DFN));
    bri = tot1 = tot2 = dfn = cnt = ;
}
void add1(int u,int v){
    E1[++tot1].v = v;
    E1[tot1].next = head1[u];
    head1[u] = tot1;
}
void add2(int u,int v){
    E2[++tot2].v = v;
    E2[tot2].next = head2[u];
    head2[u] = tot2;
}
void tarjan(int u,int fa){
    DFN[u] = low[u] = ++dfn;
    s.push(u);
    for(int i = head1[u]; i != -; i = E1[i].next){
        int v = E1[i].v;
        if(!DFN[v]){
            tarjan(v,u);
            low[u] = min(low[u],low[v]);
            if(DFN[u] < low[v])
                bri++;
        }
        else if(v != fa)
            low[u] = min(low[u],low[v]);
    }
    if(DFN[u] == low[u]){
        cnt++;
        while(){
            int v = s.top();
            s.pop();
            sccno[v] = cnt;
            if(v == u)  break;
        }
    }
}
void dfs(int u,int d){ //建树
    vis[u] = ;
    deep[u] = d;
    for(int i = head2[u]; i != -; i = E2[i].next){
        int v = E2[i].v;
        if(!vis[v]){
            pre[v] = u;
            dfs(v,d+);
        }
    }
}
int find(int x){
    return father[x] == x?x:father[x] = find(father[x]);
}
void search(int a,int b){
    while(a!=b){
        if(deep[a] > deep[b]){
            bri--;                   //不管a还是b向上走一个点那桥就少一个
            father[a] = find(pre[a]);
            a = father[a];
        }
        else if(deep[b] > deep[a]){
            bri--;
            father[b] = find(pre[b]);
            b = father[b];
        }
        else{
            bri--;
            bri--;
            father[a] = find(pre[a]);
            father[b] = find(pre[b]);
            a = father[a];
            b = father[b];
        }
    }
}
void solve(){
    tarjan(,-);
    for(int u = ; u <= n; u++){
        int v;
        for(int i = head1[u]; i != -; i = E1[i].next){
            v = E1[i].v;
            if(sccno[u] != sccno[v])
                add2(sccno[u],sccno[v]);
        }
    }
    for(int i = ; i <= cnt; i++)
        father[i] = i;
    dfs(,); //建树
    int q;
    scanf("%d",&q);
    while(q--){
        int l,r;
        scanf("%d%d",&l,&r);
        l = find(sccno[l]);
        r = find(sccno[r]);
        if(!bri){
            puts("0");
            continue;
        }
        search(l,r);
        printf("%d\n",max(,bri));
    }
}
int main(){
    int casei = ;
    while(scanf("%d%d",&n,&m),n||m){
        init();
        for(int i = ; i <= m; i++){
            int u,v;
            scanf("%d%d",&u,&v);
            add1(u,v);
            add1(v,u);
        }
        printf("Case %d:\n",casei++);
        solve();
        puts("");

    }
    return ;
}