题目描述我就不说了，我先来吐槽一下评测机，尼玛段错误给报内存超限，改了一天你知道我有多绝望
后来发现是数组开小了，然后把几个小时之前的代码数组开大点儿直接秒过
真的使太搞人心态了

算法1

不加并查集优化的版本
数据太水了，不优化其实应该过不了，但是比较好理解
算法竞赛进阶指南上写的很清楚了，这里就不多赘述
第一次写，代码很丑见谅

我喜欢把原图叫作初始图，缩点之后的图叫作缩点图哈哈

时间复杂度

m+q*n
实际提交时实际和并查集优化版本跑时间的实际差不多，难道是因为数据太水了？

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int siz = 1e5 + 10;
int head[siz], head_c[siz];
struct node_c{
    int to, nxt;
}e_c[siz * 4];//乘以4是因为双向边，m<=2e5
struct node{
    int to, nxt;
}e[siz * 4];
int tot = 1, tot_c = 1;
void add(int x, int y){
    e[++tot].to = y;
    e[tot].nxt = head[x];
    head[x] = tot;
}int bri[siz*4];
void add_c(int x, int y){
    e_c[++tot_c].to = y;
    e_c[tot_c].nxt = head_c[x];
    head_c[x] = tot_c;
    bri[tot_c] = 1;//我们需要的桥的编号是缩点之后的编号，这里求的桥才是后面需要用到的
    //就是这个数组开小了一直给我报内存超限！！！！！！**
}
int dfn[siz], low[siz], num;

void tarjan(int x, int in){
    dfn[x] = low[x] = ++num;
    for (int i = head[x]; i; i = e[i].nxt){
        int to = e[i].to;
        if (!dfn[to]){
            tarjan(to, i);
            low[x] = min(low[x], low[to]);
            if (dfn[x] < low[to]){
                bri[i] = bri[i ^ 1] = 1;
            }
        }
        else if (i != (in ^ 1)){
            low[x] = min(low[x], dfn[to]);
        }
    }
}
int c[siz];
int cnt = 0;
void dfs(int x){//编号，和书上一样，就是不遍历有桥的那条边，这里要用初始图上的桥
    c[x] = cnt;
    for (int i = head[x]; i; i = e[i].nxt){
        int to = e[i].to;
        if (bri[i] || c[to])continue;
        dfs(to);
    }
}
//LCA被我写成了结构体，拆开写一样的

struct LCA{  //LCA要是还不会就先去补补课吧
    int f[siz][26]; int dep[siz];
    void dfs(int deep, int pre, int x){
        dep[x] = deep; f[x][0] = pre;
        for (int i = 1; i <= 25; i++){
            if (f[x][i - 1] != -1){
                f[x][i] = f[f[x][i - 1]][i - 1];
            }
            else break;
        }
        for (int i = head_c[x]; i; i = e_c[i].nxt){
            int to = e_c[i].to;
            if (to == pre)continue;
            dfs(deep + 1, x, to);
        }
    }
    int lca(int x, int y){
        if (dep[x] < dep[y])swap(x, y);
        int dis = dep[x] - dep[y];
        for (int i = 0; i <= 25; i++){
            if ((1 << i)&dis){
                x = f[x][i];
            }
        }
        for (int i = 25; i >= 0; i--){
            if (f[x][i] != f[y][i]){
                x = f[x][i];
                y = f[y][i];
            }
        }
        return f[x][0] == -1 ? x : f[x][0];
    }
    void init(){
        memset(f, -1, sizeof f);
        memset(dep, 0, sizeof dep);
        dfs(1, -1, 1);
    }
};
int k = 0;
void init(){//多样例输入初始化就是很麻烦
    tot = 1;
    tot_c = 1;
    cnt = 0;
    num = 0;
    memset(low, 0, sizeof low);
    memset(dfn, 0, sizeof dfn);
    memset(bri, 0, sizeof bri);
    memset(c, 0, sizeof c);
    memset(head, 0, sizeof head);
    memset(head_c, 0, sizeof head_c);
    for (int i = 0; i <siz * 2; i++){//下次再也不用结构体了，memset没法用，只能for循环
        e[i].nxt = 0;
        e[i].to = 0;
        e_c[i].nxt = 0;
        e_c[i].to = 0;
    }
}
LCA p;
int cntt = 0;;
void dfs1(int x, int lca){
    if (x == lca)return;
    for (int i = head_c[x]; i; i = e_c[i].nxt){
        int to = e_c[i].to;
        if (to == p.f[x][0]){
            if (bri[i]){
                bri[i] = 0;
                bri[i ^ 1] = 0;
                cntt++;
            }
            dfs1(to, lca);
        }
    }
}
int main(){
    int n, m;
    while (cin >> n >> m){
        init();
        int x, y; int u, v;
        if (n == 0 && m == 0)break;
        for (int i = 0; i < m; i++){//和书上一样不多讲
            scanf("%d%d", &u, &v);
            if (u == v)continue;
            add(u, v), add(v, u);
        }
        tarjan(1, 0);//题上说了连通图，跑一次就能遍历所有点了，没必要非和书上写的一样
        for (int i = 1; i <= n; i++){//给与桥相连的每个连通块儿编号，就不多说了
            if (!c[i]){
                cnt++;
                dfs(i);
            }
        }
        memset(bri, 0, sizeof bri);//将已经在初始图里求过的桥初始化，
                                   //因为我们实际上不会使用初始图上的桥
                                   //而是使用缩点图里的桥
        for (int i = 2; i <= tot; i++){
            int x = e[i].to, y = e[i ^ 1].to;
            if (c[x] == c[y])continue;
            add_c(c[x], c[y]);//这里因为遍历了所有边，包括双向边，所以只加一次就行
            //同时这里求了缩点图里的桥，其实每条边都是桥，所以直接写在加边里面了 哈哈
        }
        p.init();//这里是初始化连带求dep数组
        int ans = 0;
        for (int i = 2; i < tot; i += 2){
            if (bri[i])ans++;//寻找桥的数量，其实可以直接等于cnt-1，因为cnt是缩点之后点的数量，
                             //那么缩点之后桥的数量一定是点的数量-1，
        }
        int q;
        cin >> q; 
        printf("Case %d:\n", ++k);
        int h = ans;//这里用h接收ans其实并没有什么卵用
        for (int i = 1; i <= q; i++){
            scanf("%d%d", &x, &y);

            if (c[x] == c[y]){
                printf("%d\n", h);
            }
            else{
                int lca = p.lca(c[x], c[y]);
                //在缩点图上跑lca，至于为什么一定要缩点，
                //是因为lca只能在树上跑，图因为有环，
                //存在祖先是自己的儿子的情况，所以没法跑
                //缩点之后所有的环会变成点，缩点图就成了一颗树

                cntt = 0;dfs1(c[x], lca);h -= cntt;//往lca的方向跑，中途记录桥的数量
                cntt = 0;dfs1(c[y], lca);h -= cntt;//同上
                cout << h << endl;
            }
        }
        cout << endl;
    }
}

算法2

并查集优化版本

仍然写的又臭又长，代码能力太菜了，没办法

时间复杂度

m+q*logn

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int siz = 1e5 + 2;
int head[siz], head_c[siz];
int to[siz * 4], nxt[siz * 4],to_c[siz * 4], nxt_c[siz * 4];
bool bri[siz*4];int dfn[siz], low[siz], num;int c[siz];int cnt = 0;
int n, m;int k = 0;int pre[siz];

int tot = 1, tot_c = 1;
void add(int x, int y){
    to[++tot] = y;
    nxt[tot] = head[x];
    head[x] = tot;
}
void add_c(int x, int y){
    to_c[++tot_c] = y;
    nxt_c[tot_c] = head_c[x];
    head_c[x] = tot_c;
    bri[tot_c] = 1;
}


void tarjan(int x, int in){
    dfn[x] = low[x] = ++num;
    for (int i = head[x]; i; i = nxt[i]){
        int to1 = to[i];
        if (!dfn[to1]){
            tarjan(to1, i);
            low[x] = min(low[x], low[to1]);
            if (dfn[x] < low[to1]){
                bri[i] = bri[i ^ 1] = 1;
            }
        }
        else if (i != (in ^ 1)){
            low[x] = min(low[x], dfn[to1]);
        }
    }
}

void dfs(int x){
    c[x] = cnt;
    for (int i = head[x]; i; i = nxt[i]){
        int to1 = to[i];
        if (bri[i] || c[to1])continue;
        dfs(to1);
    }
}
        //LCA拆开写了
int f[siz][16]; int dep[siz];
bool vis[siz];
void dfs2(int deep, int pre, int x){
        dep[x] = deep; f[x][0] = pre;
        for (int i = 1; i <= 15; i++){
            if (f[x][i - 1] != -1){
                f[x][i] = f[f[x][i - 1]][i - 1];
            }
            else break;
        }
        for (int i = head_c[x]; i; i = nxt_c[i]){
            int to = to_c[i];
            if (to == pre)continue;
            dfs2(deep + 1, x, to);
        }
}
int lca(int x, int y){
    if (dep[x] < dep[y])swap(x, y);
    int dis = dep[x] - dep[y];
    for (int i = 0; i <= 15; i++){
        if ((1 << i)&dis){
            x = f[x][i];
        }
    }
    for (int i = 15; i >= 0; i--){
        if (f[x][i] != f[y][i]){
            x = f[x][i];
            y = f[y][i];
        }
    }
    return f[x][0] == -1 ? x : f[x][0];
}
void init(){
    tot = 1;
    tot_c = 1;
    cnt = 0;
    num = 0;
    memset(dfn, 0, sizeof dfn);
    memset(bri, 0, sizeof bri);
    memset(c, 0, sizeof c);
    memset(head, 0, sizeof head);
    memset(head_c, 0, sizeof head_c);
    memset(f, 0, sizeof f);
    memset(dep, 0, sizeof dep);
    for (int i = 1; i <= n; i++){
        pre[i] = i;
    }
}
int cntt = 0;
//并查集真好用
int find(int x){
    return pre[x] == x ? x : pre[x] = find(pre[x]);
}
int main(){

    while (~scanf("%d%d",&n,&m)){
        init();
        int x, y; int u, v;
        if (n == 0 && m == 0)break;
        for (int i = 0; i < m; i++){
            scanf("%d%d", &u, &v);
            if (u == v)continue;
            add(u, v), add(v, u);
        }
        tarjan(1, 0);
        for (int i = 1; i <= n; i++){
            if (!c[i]){
                cnt++;
                dfs(i);
            }
        }
        memset(bri, 0, sizeof bri);
        for (int i = 2; i <= tot; i++){
            int x = to[i], y = to[i^1];
            if (c[x] == c[y])continue;
            add_c(c[x], c[y]);
        }
        int ans = 0;
        for (int i = 2; i < tot; i += 2){
            if (bri[i])ans++;
        }
        int q;
        cin >> q; printf("Case %d:\n", ++k);
        dfs2(1, -1, 1);//求dep数组和f数组
        int h = ans;//h仍然没什么卵用
        for (int i = 1; i <= q; i++){
            scanf("%d%d", &x, &y);
                int lc = lca(c[x], c[y]);
                x = c[x], y = c[y];
                //这里使用并查集，将x走过的路径压缩，使x可以直接定位到没走过的地方
                x = find(x);
                y = find(y);
                //因为对于一颗树来说，一个节点的父节点一定只有一个
                //所以f[x][0]一定就是x的父节点，其实完全可以在tarjan里加一个
                //fa数组来记录父节点，因为只有一个
                while (dep[x]>dep[lc]){
                    pre[x] = f[x][0];
                    h--;
                    x = find(x);
                }
                while (dep[y] > dep[lc]){
                    pre[y] = f[y][0];
                    h--;
                    y = find(y);
                }
                printf("%d\n", h);
            }puts("");
        }
    return 0;
}