题目描述

中文题
太痛苦了
原谅我开头就宣泄负能量，但是一个极low的模板题式的题目花了我两天时间调bug，调的真的是昏天黑地啊。既然这么痛苦就好好写写这个博客吧。

题解：
point1 ：求出边双连通分量，并缩点得到一棵树
point2：对于每一条加入的边在缩点后的树上，他的两个节点对应树中节点，树上两个节点路径上的桥全部标记并在答案中减掉（在之前已经标记过的桥不用减）这个在之前写的时候真没想通如何标记，翻阅了别人的代码后，发现是与lca比较深度来向上走，妙啊。
point3：向上走的过程可以使用并查集优化，很棒。
本题曾经写出的bug：
1.lca中的边界未准确判断
2.初始化并查集fa初始化成0
3.清空时少清空了数组
4.i!=(in_edge^1)忘加了括号
加油。

#include<stdio.h>
#include<cstring>
#include<math.h>
#include<queue>
using namespace std;
typedef long long ll;
const int INF=1e9+7;
const int N=1e5+5;
const int M=4e5+5;
int ver[M] , Next[M] , head[N] ,ans , t,tot;
int dfn[N], low[N] ,num , n , m;
bool brige[M];

void add(int x,int y){
    ver[++tot] = y , Next[tot] = head[x] , head[x] = tot;
}
void tarjan(int x, int in_edge = 0){
    dfn[x] = low[x] = ++num;
    for(int i = head[x] ; i ; i = Next[i]){
        int y = ver[i];
        if(!dfn[y]){
            tarjan(y , i);
            low[x] = min(low[y] , low[x]);
            if(low[y] > dfn[x]){
                brige[i] = brige[i^1] = true;
            }
        }
        else if(i != (in_edge^1))
            low[x] = min(low[x] , low[y]);
    }
}
int dcc , c[M];
void dfs(int x){
    c[x] = dcc;
    for(int i = head[x] ; i ; i = Next[i]){
        int y = ver[i];
        if(c[y] || brige[i]) continue;
        dfs(y);
    }
}
int fa[N] ,d[N] , f[N][20];

int get(int x){
    return fa[x] == x ? x : fa[x]=get(fa[x]);
}
int hc[N] , vc[M] , nc[M] , tc;
void add_c(int x,int y){
    vc[++tc] = y , nc[tc] = hc[x] , hc[x] = tc;
}
void bfs(){
    queue<int>q;
    q.push(1);
    d[1] = 1;
    while(q.size()){
        int x = q.front();
        q.pop();
        for(int i = hc[x] ;i;i = nc[i]){
            int y = vc[i];
            if(d[y])continue;
            d[y] = d[x] + 1;
            f[y][0] = x;
            for(int j = 1;j <= 17; j ++){
                f[y][j] = f[f[y][j-1]][j-1];
            }
            q.push(y);
        }
    }
}


int lca(int x, int y){
    if(d[x] > d[y])swap(x, y);
    for(int i = 17; i >= 0 ;i --){
        if(d[f[y][i]] >= d[x])y = f[y][i];
    }
    if(x == y)return x;
    for(int i = 17 ;i >=0 ; i --){
        if(f[x][i]!=f[y][i])x = f[x][i] , y = f[y][i];
    }
    return f[x][0];
}
void clr(){
    tot = 1 , num = 0 ;
    memset(head , 0 , sizeof head);
    memset(hc,0,sizeof hc);
    memset(brige , 0 , sizeof brige);
    memset(dfn,0,sizeof dfn);
    memset(c,0,sizeof c);
    memset(d,0,sizeof d);
    memset(f, 0 , sizeof f);
    for(int i = 1;i <= n ;i ++){
        fa[i]  = i;
    }

}



int main() {
    int T = 0;
    while(~scanf("%d %d" , &n , &m)){
        clr();
        if(n == 0 && m == 0)break;
        for(int i = 1;i <= m ;i ++){
            int x, y ;
            scanf("%d %d" , &x ,&y);
            add(x,y);add(y,x);
        }
        for(int i = 1;i <= n ;i ++){
            if(!dfn[i]){
                tarjan(i);
            }
        }
        dcc = 0;
        for(int i = 1;i <= n; i ++){
            if(!c[i]){
                ++ dcc;
                dfs(i);
            }
        }
        /**
            1 ~ dcc 为缩点后的点
        ***/
        ans = dcc - 1;
        tc = 1;
//        printf("%d\n",ans);
        for(int i = 2;i <= tot ;i ++){
            int x = ver[i^1] , y = ver[i];
//            printf("%d %d\n",c[x] , c[y]);
            if(c[x] == c[y])continue;
            add_c(c[x] , c[y]);

        }
        /**
        for(int i = 1;i <= n;i ++)
            printf("%d " , c[i]);
        puts("");
        ***/
        bfs();
//        for(int i = 1;i <= n ;i ++){
//            for(int j = 0; j < 2 ; j ++)
//                printf("%d " ,f[i][j] );
//            puts("");
//        }
        int Q;scanf("%d" , &Q);
        printf("Case %d:\n",++T);

        while(Q --){
            int x, y ;
            scanf("%d %d" , &x, &y);
            x = c[x] , y = c[y];
//            printf("%d %d\n" ,x,y );
            x = get(x) , y = get(y);
            int z = lca(x, y);
//            printf("%d\n",z);
            while(d[x] > d[z]){fa[x] =  f[x][0] , -- ans  , x = get(x); }
            while(d[y] > d[z]){fa[y] =  f[y][0] , -- ans  , y = get(y); }
            printf("%d\n",ans);

        }
        putchar('\n');
    }
}