题面

给定一张N个点M条边的无向连通图，然后执行Q次操作，每次向图中添加一条边，并且询问当前无向图中“桥”的数量。

输入格式

输入包含多组测试数据。

每组测试数据，第一行包含两个整数N和M。

接下来M行，每行包含两个整数A和B，表示点A和点B之间有一条边，点的编号为1~N。

接下来一行，包含整数Q。

在接下来Q行，每行包含两个整数A和B，表示在A和B之间加一条边。

当输入0 0时表示输入终止。

输出格式

每组数据第一行输出“Case x:”，其中x为组别编号，从1开始。

接下来Q行，每行输出一个整数，表示一次询问的结果。

每组数据输出完毕后，输出一个空行。

数据范围

1≤N≤100000
N−1≤M≤200000,
1≤A≠B≤N,
1≤Q≤1000

输入样例：

3 2
1 2
2 3
2
1 2
1 3
4 4
1 2
2 1
2 3
1 4
2
1 2
3 4
0 0

输出样例：

Case 1:
1
0

Case 2:
2
0

题解

就是套板子题, e-DCC缩点, 重建图, 在跑树上LCA, 运用并查集解体, 主要是细节

其他细节其他大佬的题解写的够清楚了, 主要是没找到 栈缩点的代码, 放出来给大家对拍

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;

template<class T1, class T2> bool umin(T1& a, T2 b) { return a > b ? (a = b, true) : false; }
template<class T1, class T2> bool umax(T1& a, T2 b) { return a < b ? (a = b, true) : false; }

const int N = 1e5 + 5, M = 4e5 + 5;

struct STFrom {
    int f[N][20], dep[N], lg[N], t;//N为节点的数量
    int *h, *ne, *to;
    void init(int n, int* H, int* Ne, int* To) {
        t = log2(n - 1) + 1; h = H, ne = Ne, to = To; lg[0] = -1;
        rep(i, 1, n) dep[i] = 0, lg[i] = lg[i >> 1] + 1;
    }
    void bfs(int s) {
        queue<int> q; q.push(s); dep[s] = 1;
        rep(i, 0, t) f[s][i] = 0;
        while (!q.empty()) {
            int x = q.front(); q.pop();
            for (int i = h[x], y = to[i]; i; y = to[i = ne[i]]) {
                if (dep[y]) continue;
                dep[y] = dep[x] + 1; f[y][0] = x; q.push(y);
                for (int j = 1; j <= t; ++j) f[y][j] = f[f[y][j - 1]][j - 1];
            }
        }
    }
    int lca(int x, int y) {
        if (dep[x] > dep[y]) swap(x, y);
        for(int k = dep[y] - dep[x], i = lg[k]; ~i; --i) if (k >> i & 1) y = f[y][i];
        if (x == y) return x;
        per(i, lg[dep[y]], 0) if (f[x][i] ^ f[y][i]) x = f[x][i], y = f[y][i];
        return f[x][0];
    }
    int dist(int x, int y) { return dep[x] + dep[y] - (dep[lca(x, y)]<<1); }
} ST;

int n, m, ecnt, c[N], f[N];
int h[N], to[M], ne[M], tot;
int nh[N], nto[M], nne[M], ntot;
int dfn[N], low[N], df, st[N], top;

void add(int u, int v, int* h, int* ne, int* to, int& tot) {
    ne[++tot] = h[u]; to[h[u] = tot] = v;
}

void tarjan(int x, int bian) {
    dfn[st[++top] = x] = low[x] = ++df;
    for (int i = h[x], y = to[i]; i; y = to[i = ne[i]])
        if (!dfn[y]) tarjan(y, i), umin(low[x], low[y]);
        else if (i != (bian ^ 1)) low[x] = min(low[x], dfn[y]);
    if (low[x] == dfn[x]) {
        ++ecnt; int y;
        do c[y = st[top--]] = ecnt; while (y != x);
    }
}

int ff(int x) { return x == f[x] ? x : f[x] = ff(f[x]); }

int main() {
    IOS; int cas = 0;
    while (cin >> n >> m, n || m) {
        ecnt = ntot = df = 0; tot = 1;
        rep (i, 1, n) h[i] = nh[i] = dfn[i] = low[i] = 0;
        rep (i, 1, m) {
            int u, v; cin >> u >> v;
            if (u == v) continue;
            add(u, v, h, ne, to, tot); add(v, u, h, ne, to, tot);
        }
        tarjan(1, 0);
        rep (i, 2, tot) {
            int x = to[i ^ 1], y = to[i];
            if (c[x] ^ c[y]) add(c[x], c[y], nh, nne, nto, ntot);
        }
        ST.init(n, nh, nne, nto); ST.bfs(1);
        rep (i, 1, ecnt) f[i] = i;
        cout << "Case " << ++cas << ":\n";
        for (cin >> m; m; --m) {
            int u, v, z; cin >> u >> v; u = ff(c[u]), v = ff(c[v]); z = ST.lca(u, v);
            while (u ^ z) f[u] = ST.f[u][0], --ecnt, u = ff(u);
            while (v ^ z) f[v] = ST.f[v][0], --ecnt, v = ff(v);
            cout << ecnt - 1 << '\n';
        }
        cout << '\n';
    }
    return 0;
}