算法

(Tarjan) $O(m + nlogn)$

利用Tarjan求边双缩点，然后在树上操作，使用并查集优化。

参考文献

C++ 代码

// Program written by Liu Zhaozhou ~~~
const int Maxn = 1e5 + 5, Maxm = 4e5 + 5;
int n, m, q, cnt, head[Maxn], ver[Maxm], nxt[Maxm];
inline void AddEdge(int u, int v) {
    ver[++cnt] = v, nxt[cnt] = head[u], head[u] = cnt;
}

vector <int> vec[Maxn]; bool bridge[Maxm];
int dfn[Maxn], low[Maxn], col[Maxn], timer, dcc;
inline void Tarjan(int u, int e) {
    dfn[u] = low[u] = ++timer;
    for (int i = head[u]; i; i = nxt[i])
        if (!dfn[ver[i]]) {
            Tarjan(ver[i], i); chkmin(low[u], low[ver[i]]);
            if (low[ver[i]] > dfn[u]) bridge[i] = bridge[i ^ 1] = true;
        } else if (e != (i ^ 1)) chkmin(low[u], dfn[ver[i]]);
}

inline void Clear(void) {
    cnt = 1; timer = dcc = 0, Ms(head, 0);
    Ms(col, 0), Ms(dfn, 0), Ms(low, 0), Ms(bridge, false);
}

inline void Col(int u, int c) {
    col[u] = c;
    for (int i = head[u]; i; i = nxt[i])
        if (!col[ver[i]] && !bridge[i]) Col(ver[i], c);
}

int dep[Maxn], F[Maxn][21];

inline void Prework(int u, int fa) {
    dep[u] = dep[fa] + 1; F[u][0] = fa;
    for (int i = 1; i <= 20; i++) F[u][i] = F[F[u][i - 1]][i - 1];
    for (int i = 0; i < (int) vec[u].size(); i++)
        if (vec[u][i] != fa) Prework(vec[u][i], u);
}

inline int Lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = 20; i >= 0; i--)
        if (dep[F[u][i]] >= dep[v]) u = F[u][i];
    if (u == v) return u;
    for (int i = 20; i >= 0; i--)
        if (F[u][i] != F[v][i]) u = F[u][i], v = F[v][i];
    return F[u][0];
}

int T, f[Maxn], ans;
inline int getf(int x) { return f[x] == x ? x : f[x] = getf(f[x]); }
inline void unionf(int x, int y) { f[getf(x)] = getf(y); }

inline void Modify(int u, int v) {
    int lca = Lca(u, v); lca = getf(lca);
    while (getf(u) != lca) {
        --ans; int x = getf(u);
        unionf(x, F[x][0]);
        u = F[x][0];
    }

    while (getf(v) != lca) {
        --ans; int y = getf(v);
        unionf(y, F[y][0]);
        v = F[y][0];
    } writeln(ans);
}

inline void solve(void) {
    Clear();
    for (int i = 1, u, v; i <= m; i++)
        read(u), read(v), AddEdge(u, v), AddEdge(v, u);

    Tarjan(1, 0);
    for (int i = 1; i <= n; i++) if (!col[i]) Col(i, ++dcc);
    for (int i = 1; i <= dcc; i++) f[i] = i, vec[i].clear();

    ans = 0;
    for (int i = 2; i <= cnt; i += 2) {
        if (bridge[i]) ++ans;
        int u = ver[i], v = ver[i + 1];
        if (col[u] == col[v]) continue;
        vec[col[u]].push_back(col[v]);
        vec[col[v]].push_back(col[u]);
    }

    Prework(1, 0); read(q);
    printf ("Case %d:\n", ++T);
    for (int i = 1, u, v; i <= q; i++) {
        read(u), read(v);
        if (col[u] != col[v]) Modify(col[u], col[v]);
        else writeln(ans);
    }
}

signed main(void) {
    for (read(n), read(m); n && m; read(n), read(m)) solve(), puts("");
    return 0;
}

/**/