定义

割点

在一个 无向图 中,如果删掉节点 $u$ 使得整个图的连通分量增加,那么 $u$ 是一个割点。

在一个 无向图 中,如果删掉一条边 $(u,v)$ 使得整个图的连通分量增加,那么 $(u,v)$ 是一个桥。


点双连通

一个 无向图点双连通 的,当且仅当(以下表达是 equivalent 的):

  1. 如果删去任意一个节点,其他节点仍然互相连通。
  2. 不包含割点(注意,这个割点是对于 这个子图 而言)。
  3. 任取两个点 $u,v$,$u,v$ 之间都存在两条 点不重复 路径。
  4. 任取 $2$ 条边,都存在一个简单环(环内不包含其他环),使得这 $2$ 条边在这个简单环内。

• 注意,如果图内只有 $2$ 个连起来的节点,它们仍然点双连通。

• 点双连通 不具有传递性

img

如上图,$a,b$ 点双连通,$b,c$ 点双连通,但是 $a,c$ 并不点双连通($a,c$ 不在同一个点双分量内)。


边双连通

一个 无向图边双连通 的,当且仅当(以下表达是 equivalent 的):

  1. 一个 无向图 中,如果删去任意一条,其他节点仍然互相连通。
  2. 一个 无向图 中,不包含桥(注意,这个桥是对于 整个图 而言)。
  3. 一个 无向图 中,任取两个点 $u,v$,$u,v$ 之间都存在两条 边不重复 路径。
  4. 一个 无向图 中,任取 $1$ 条边,都存在一个简单环(环内不包含其他环),使得这条边在这个简单环内。

• 点双连通 具有传递性

如果 $a,b$ 边双连通,$b,c$ 边双连通,则 $a,c$ 边双连通。

证明:$a,b$ 边双连通说明 删去图中任意一条边,$a,b$ 仍连通。同理,删去图中任意一条边,$b,c$ 仍连通。所以删去任意一条边,$a,c$ 仍连通。


点双连通分量

点双连通分量:一个极大的点双连通的子图。

  1. 如果把这个子图 单独拿出来,它不存在割点,但是它在原图中,如果它与其他点双分量相连,那么它一定包含 至少一个原图中的割点。
  2. 原图中,每个割点 存在于至少 $2$ 个点双分量中。
  3. 任意一个 非割点 只存在于一个点双分量中。

点双缩点

利用点双缩点后,得到的新图有以下性质:

  1. 新图 是一棵树,每个节点要么是一个点双,要么是一个割点
  2. 所有 割点 单独成为一个节点。
  3. 点双之间以 割点 相连,并且所有割点的 degree 至少为 $2$。(任意两个点双之间,有且仅有一个公共点,且这个公共点是 割点)。

例1:

图中的所有点双分量为:$\{1,2,3\}, \{3,4,5\}$

图中所有割点为:$3$

img

例2:

图中的所有点双分量为:$\{1,2\}, \{1,3\}, \{2,4\}, \{2,5\}, \{3,6\}, \{3,7\}$

图中所有割点为:$1,2,3$

img


边双连通分量

边双连通分量:一个极大的边双连通子图。

相比点双分量来说,边双分量的定义简单很多,因为它 不需要区分 原图和子图!

  1. 将原图中的所有桥删掉,剩下的分量就是边双连通分量。
  2. 桥不属于任何一个边双分量,边双分量之间以桥连接。

例1:

图中的所有边双分量为:$\{1,2,7\}, \{4,5,6\}, \{3\}$

图中所有桥为:$(2,3), (2,4)$

img

边双缩点

利用边双缩点后,得到的新图有以下性质:

  1. 新图是 一棵树,每个节点都是一个边双
  2. 原图中 所有的桥,在新图中仍然是桥。

算法

我们利用 tarjan 算法求 割点,桥,点双,边双

这里的 tarjan 和 有向图求SCC 的tarjan略有不同,主要体现在:

  1. 有向图tarjan求SCC:需要记录当前在 栈内 的有哪些元素,更新 low[] 时,需要 to 在栈内才更新
  2. 无向图求割点/桥/点双/边双:需要检查 to 是不是 u 的直接 parent p。(这里指的是 dfs树 内的parent关系),不需要考虑是否在栈内。

另外,求 割点 和 桥 时,也略有不同,主要体现在:

  1. 求割点时,需要讨论当前节点是否为DFS树的根。但是求桥时,不需要。
  2. 求割点时,条件是 $low[to] \geq dfn[u]$。求桥时,条件是 $low[to] > dfn[u]$。

以下的算法,都要检查 to 是不是 u 的直接 parent p

割点

对于一个节点 $u$,在DFS树中,如果:

  1. DFS树的 根节点:如果 $u$ 拥有 $\geq 2$ 个子树,那么 $u$ 就是一个割点。
  2. 不是DFS树的 根节点:如果 $u$ 存在一个 direct child $~to$,使得 $low[to] \geq dfn[u]$。那么 $u$ 就是一个割点。(因为这说明 $to$ 无法到达 $u$ 的上方)

模版题

题意

给定一个无向图,求图的所有割点。

代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e4+5;
const int maxm = 1e5+10;

struct Edge {
    int to, nxt;
} edges[maxm<<1];

int dfn[maxn], low[maxn], head[maxn], ecnt = 1, n, m, id;
void addEdge(int u, int v) {
    Edge e = {v, head[u]};
    edges[ecnt] = e;
    head[u] = ecnt++;
}
vector<int> ans;

void dfs(int u, int p) {
    dfn[u] = ++id;
    low[u] = id;
    int child = 0;  // 子树数量
    bool cut = 0;  // 是否为割点
    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == p) continue;  // 不能直接用parent

        if (dfn[to]) {
            low[u] = min(low[u], dfn[to]);
            continue;
        }

        dfs(to, u);
        child++;
        low[u] = min(low[u], low[to]);
        if (p && low[to] >= dfn[u]) cut = 1;  
        // 如果u不是根节点,且存在 direct child使得 low[to] >= dfn[u],则u是割点
    }
    if (!p && child >= 2) cut = 1;  // 如果为根节点,且有 >= 2个子树
    if (cut) ans.push_back(u);
}

void tarjan() {
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) dfs(i, 0);
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u,v; cin >> u >> v;
        addEdge(u,v); addEdge(v,u);
    }
    tarjan();

    sort(ans.begin(), ans.end());
    cout << ans.size() << endl;
    for (int a : ans) cout << a << " ";
    cout << endl;
}

判断一个边 $(u,to)$ 是不是桥,我们设 $u$ 在DFS树中,是 $to$ 的parent。

如果 $low[to] > dfn[u]$,则 $(u,to)$ 是一个桥。(因为这说明 $to$ 无法到达 $u$ 和 $u$ 的上方)。


实现过程中,需要注意以下几点:

  1. 边的编号从 $0$ 开始(记得将 head[] 初始化为 -1),这样保证了 ee^1 刚好为 $(u,v)$ 和 $(v,u)$。
  2. 标记桥的时候,一次标记两个边 ee^1
代码
void tarjan(int u, int p) {
    dfn[u] = low[u] = ++id;
    for (int e = head[u]; ~e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == p) continue;  // 注意不能用parent
        if (dfn[to]) low[u] = min(low[u], dfn[to]);
        else {
            tarjan(to, u);
            low[u] = min(low[u], low[to]);
            if (low[to] > dfn[u]) {  // 注意这里的条件
                bridge[e] = bridge[e^1] = 1;
            }
        }
    }
}

点双连通分量(dcc)

求点双分量,可以在求割点的时候顺便求出来

当我们发现 $low[to] \geq dfn[u]$ 时,就说明 $to$ 及其子树(加上 $u$)一起形成了一个点双。

此时,我们将 栈内的点一直pop,popto 为止(包括 to),但是 不包括 u。这是因为 u 作为割点,可能还属于别的点双分量,之后还要用到。

• 求点双时,我们并不关心 $u$ 本身是否为割点,只要出现了 $low[to] \geq dfn[u]$,就说明出现了一个新点双。(例如,在只有 $1,2$ 这两个点的情况下,不存在割点,但是 $1,2$ 仍然是一个点双)。

代码
bool cut[maxn];
vector<int> dcc_list[maxn];
void dfs(int u, int p) {
    dfn[u] = low[u] = ++id;
    st[++tail] = u;
    int child = 0;

    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == p) continue;
        if (dfn[to]) {
            low[u] = min(low[u], dfn[to]);
        } else {
            child++;
            dfs(to, u);
            low[u] = min(low[u], low[to]);
            if (low[to] >= dfn[u]) {  // 不关心 u 是否为割点,直接开始pop
                from[to] = ++dcc;
                while (st[tail] != to) {  // 注意是 pop 到 to 为止(包括to)
                    int cur = st[tail--];
                    from[cur] = from[to];
                    dcc_list[dcc].push_back(cur);
                }
                tail--;  // tail--后,指向的是 u
                dcc_list[dcc].push_back(to);
                dcc_list[dcc].push_back(u);  // 注意 u是割点,也要进入该分量
                // from[u] = dcc;  // from[u] 实际上没有意义
            }
            if (low[to] >= dfn[u] && p) cut[u] = 1;  // 割点(非根节点)
        }
    }
    if (!p && child >= 2) cut[u] = 1;  // 割点(根节点)
}

边双连通分量(ecc)

求边双分量,可以根据定义:删去所有的桥,剩下的连通分量,就是边双分量。

所以求边双分量,分以下两步:

  1. tarjan 求出所有的桥。
  2. 进行一次 dfs(),如果 $(u,to)$ 是桥,则不经过这条边。以此求出所有的连通分量。
代码
int from[maxn];
bool bridge[maxm<<1];

void tarjan(int u, int p) {
    dfn[u] = low[u] = ++id;
    for (int e = head[u]; ~e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == p) continue;
        if (dfn[to]) low[u] = min(low[u], dfn[to]);
        else {
            tarjan(to, u);
            low[u] = min(low[u], low[to]);
            if (low[to] > dfn[u]) {
                bridge[e] = bridge[e^1] = 1;
            }
        }
    }
}

// dfs求出所有的边双
// f 代表 from (ecc编号)
void dfs(int u, int f) {
    from[u] = f;
    for (int e = head[u]; ~e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (from[to] || bridge[e]) continue;  // to已访问,或者该边是桥
        dfs(to, f);
    }
}

int main() {
    // ...
    for (int i = 1; i <= n; i++) 
        if (!from[i]) 
            dfs(i, ++ecc);
    // ...
}

例题

例1 洛谷P3225 [HNOI2012]矿场搭建

题意

给定 $M$ 条边的无向图。初始状态下,每个节点没有标记。

我们需要给节点打上标记,使得:

删去图中的任意一个节点,其他的所有节点均可到达一个有标记的节点。

求:标记节点的最少数量,最少标记数量的方案总数。

其中,$M \leq 500$,数据保证不存在单个独立点。

题解

首先根据 点双连通 进行缩点。缩点以后,整个图会变成一个由 割点点双分量 组成的

由于点双的性质,我们知道,如果删去点双分量中的任意一个点(除割点以外),该分量仍然和其他的分量连通。

所以我们不需要考虑删去 非割点 的情况,我们只关心如果删去了一个 割点,会不会使得有些节点无法到达有标记的节点。

由上可知,我们 不需要标记割点(因为我们只考虑删去 割点 的情况,如果要删去割点,那说明标记割点是无意义的)。


对于一个点双分量而言,可以分以下情况讨论:

  1. 点双内含有 $\geq 2$ 个割点:无论删去哪个割点,该分量仍然和其他分量连通,所以无需在该分量内标记。
  2. 点双内含有 $1$ 个割点:如果该割点被删了,那么这个分量就断开了,所以该分量内部需要标记 $1$ 个节点。(不标记割点),方案数为 $(sz-1)$ (因为分量里面有一个割点,要去掉标记它的可能性)。
  3. 点双内没有割点:说明这个分量本来就是独立开的(在缩点后,是单个独立节点)。所以该分量内需要标记 $2$ 个节点。方案数为 $C_{sz}^2$。

实现中的一些细节:

  1. 由于一个割点可能属于多个点双分量,所以我们采用 vector<int> dcc_list[maxn]; 来记录每个点双里面的节点。
  2. 对于一个割点 $u$ 来说,它的 from[] 数组没有意义。(如果需要缩点,则后续会让 from[u] = ++dcc,缩点后的 from[u] 就有意义了)
  3. 与 tarjan 求 SCC 不同,我们不需要记录节点是否在栈内。
  4. pop 栈的时候,注意我们是 popto 为止(包括 to),但是 不包括 u。这是因为 u 作为割点,可能还属于别的点双分量,之后还要用到。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;

int n,m, head[maxn], ecnt = 1;
struct Edge {
    int to, nxt;
} edges[maxn];
void addEdge(int u, int v) {
    Edge e = {v, head[u]};
    edges[ecnt] = e;
    head[u] = ecnt++;
}

int dfn[maxn], low[maxn], id, st[maxn], tail, from[maxn], dcc;
bool cut[maxn];
vector<int> dcc_list[maxn];
void dfs(int u, int p) {
    dfn[u] = low[u] = ++id;
    st[++tail] = u;
    int child = 0;

    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == p) continue;
        if (dfn[to]) {
            low[u] = min(low[u], dfn[to]);
        } else {
            child++;
            dfs(to, u);
            low[u] = min(low[u], low[to]);
            if (low[to] >= dfn[u]) {
                from[to] = ++dcc;
                while (st[tail] != to) {  // 注意是 pop 到 to 为止(包括to)
                    int cur = st[tail--];
                    from[cur] = from[to];
                    dcc_list[dcc].push_back(cur);
                }
                tail--;  // tail--后,指向的是 u
                dcc_list[dcc].push_back(to);
                dcc_list[dcc].push_back(u);  // 注意 u是割点,也要进入该分量
                // from[u] = dcc;  // from[u] 实际上没有意义
            }
            if (low[to] >= dfn[u] && p) cut[u] = 1;  // 割点(非根节点)
        }
    }
    if (!p && child >= 2) cut[u] = 1;  // 割点(根节点)
}

void tarjan() {
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) dfs(i, 0);
    }
}

void init() {
    for (int i = 1; i <= dcc; i++) dcc_list[i].clear();
    id = 0;
    tail = -1;
    dcc = 0;
    n = 0;
    ecnt = 1;

    fill(cut, cut+maxn, 0);
    fill(from, from+maxn, 0);
    fill(head, head+maxn, 0);
    fill(dfn, dfn+maxn, 0);
    fill(low, low+maxn, 0);
}

void solve(int T) {
    init();
    for (int i = 1; i <= m; i++) {
        int u,v; cin >> u >> v;
        n = max(n,u); n = max(n,v);
        addEdge(u,v); addEdge(v,u);
    }
    tarjan();

    int ans1 = 0;
    ll ans2 = 1;

    for (int i = 1; i <= dcc; i++) {
        int cut_cnt = 0;
        int sz = dcc_list[i].size();
        for (int j = 0; j < dcc_list[i].size(); j++) {
            int cur = dcc_list[i][j];
            if (cut[cur]) cut_cnt++;
        }
        if (cut_cnt >= 2) continue;
        if (cut_cnt == 1) ans1++, ans2 *= (ll)(sz - 1);
        if (cut_cnt == 0) ans1+=2, ans2 *= (ll)(sz) * (ll)(sz-1LL) / 2LL;
    }

    printf("Case %d: %d %lld\n", T, max(ans1, 2), ans2);
}

int main() {
    int T = 0;
    while (cin >> m && m) {
        T++;
        solve(T);
    }
}

例2 洛谷P5058 [ZJOI2004]嗅探器

题意

现有 $n$ 个节点的无向图。

给定两个节点 $a,b$,输出 最小编号的 $u$ 使得 $a,b$ 之间所有的路径都需要经过 $u$,且 $u \neq a, u \neq b$。

如果无解,则输出 “No solution”。

题解

点双缩点,如果 $a,b$ 在同一个点双内必然无解(根据定义,大小等于 $3$ 的点双内,任意两点之间有点不重复的路径)。

如果 $a,b$ 在不同的点双内则说明有解,缩点后,$a,b$ 就是树上的两个节点,它们之间有唯一路径,取这个路径上编号最小的割点即可。


一些注意事项:

  1. 每个割点单独形成一个点双。
  2. 缩点得到的树,所有的边必然和 割点 相连,所以建边的时候只需要考虑割点所在的dcc,还有它旁边有哪些dcc就可以了。本题中在缩点建树的过程中,使用了数组 vector<int> cut_from[maxn];。其中 cut_from[u] 代表以 $u$ 作为割点,它neighbor的dcc编号。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
const int maxm = 5e5+5;

int n,a,b,head[maxn],ecnt = 0;
struct Edge {
    int to, nxt;
} edges[maxm<<1];

void addEdge(int u, int v) {
    Edge e = {v, head[u]};
    head[u] = ecnt;
    edges[ecnt++] = e;
}

int dfn[maxn], low[maxn], dcc = 0, id = 0, st[maxn], from[maxn], tail = -1;
bool cut[maxn];
vector<int> dcc_list[maxn<<1];
vector<int> cut_from[maxn];  // cut_from[u] 代表以 u 作为割点,它neighbor的dcc编号
void tarjan(int u, int p) {
    dfn[u] = low[u] = ++id;
    st[++tail] = u;
    int child = 0;
    for (int e = head[u]; ~e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == p) continue;
        if (dfn[to]) low[u] = min(low[u], dfn[to]);
        else {
            child++;
            tarjan(to, u);
            low[u] = min(low[u], low[to]);
            if (low[to] >= dfn[u]) {
                from[u] = ++dcc;
                while (st[tail] != to) {
                    int cur = st[tail--];
                    from[cur] = from[u];
                    dcc_list[dcc].push_back(cur);
                }
                tail--;
                from[to] = from[u];
                dcc_list[dcc].push_back(to);
                dcc_list[dcc].push_back(u);
            }

            if (low[to] >= dfn[u] && p) {
                cut[u] = 1;
            }
        }
    }
    if (child >= 2 && !p)
        cut[u] = 1;
}

vector<int> adj[maxn<<1];  // 缩点后的图
int par[maxn<<1], dep[maxn<<1];  // 缩点后,dfs树用到的数组
int mp[maxn<<1];  // map: dcc -> cut vertex id (只有该dcc对应的是 单个割点形成的 dcc才有用)

void dfs(int u, int p) {
    par[u] = p;
    dep[u] = dep[p] + 1;
    for (int to : adj[u]) {
        if (to == p) continue;
        dfs(to, u);
    }
}

int ans = 1e9;
void LCA(int u, int v) {
    int f1 = mp[u], f2 = mp[v];
    if (dep[u] < dep[v]) swap(u,v);
    int d = dep[u] - dep[v];
    vector<int> path;
    while (d--) {
        path.push_back(u);
        u = par[u];
    }
    path.push_back(u);
    while (u != v) {
        path.push_back(u);
        path.push_back(v);
        u = par[u], v = par[v];
    }
    path.push_back(u);
    path.push_back(v);
    for (int c : path) {
        if (mp[c] == f1 || mp[c] == f2) continue;
        if (cut[mp[c]]) ans = min(ans, mp[c]);
    }
}

void rebuild() {
    for (int i = 1; i <= dcc; i++) {
        for (int j : dcc_list[i]) {
            if (cut[j]) cut_from[j].push_back(i);
        }
    }

    for (int u = 1; u <= n; u++) {
        if (cut[u]) {
            int fu = from[u] = ++dcc;
            mp[dcc] = u;
            dcc_list[dcc].push_back(u);
            for (int fv : cut_from[u]) {
                adj[fu].push_back(fv);
                adj[fv].push_back(fu);
            }
        }
    }
}

int main() {
    cin >> n;
    int u,v;
    fill(head, head+maxn, -1);
    while (cin >> u >> v && u && v) {
        addEdge(u,v); addEdge(v,u);
    }
    cin >> a >> b;
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i,0);
    }
    rebuild();
    for (int i = 1; i <= dcc; i++) {
        if (!dep[i]) dfs(i,0);
    }
    LCA(from[a], from[b]);

    if (ans == 0 || ans == 1e9) cout << "No solution" << endl;
    else cout << ans << endl;
}

例3 POJ3694 Network

题意

给定 $N$ 个节点和 $M$ 条边的无向图,初始图是连通的。

现在要加 $Q$ 条边(可重复),每次加边后,回答图中有多少个桥。

其中,$1 \leq N \leq 10^5, N-1 \leq M \leq 2 \times 10^5, 1\leq Q \leq 1000$

题解

既然是桥,那么就直接先求一个边双,然后缩点。

边双缩点后可以得到一棵树,所有加边操作都放到这个树上来考虑。

首先会发现,加上的新边必不可能是桥(因为图原本是连通的)。

每次加边 $(u,v)$,如果 $u,v$ 在同一个边双里,那么不会有任何影响。

如果 $u,v$ 不在同一个边双里,那么加上的这条新边就会在树上形成一个环,使得环内的所有边均 不再是桥


那么,回忆一下 AcWing 352 暗之连锁 中,我们可以将树边看作主要边,新加上的边就转化为主要边。

比如,我们加上 $(u,v)$,那么就给 $u,v$ 之间路径上所有的边打一个标记。被标记过的就不是桥,没标记的就都是桥。

然而树上差分的做法只适用于离线,只有所有修改操作结束后询问才有效。

在线的做法我们可以利用 树链剖分(询问边),每次修改前,先进行一下询问,查询有多少个在修改前是无标记的,将答案减去这个数量即可。

代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
const int maxm = 2e5+5;

int n,m, head[maxn], ecnt = 0, dfn[maxn], low[maxn], id = 0, from[maxn], ecc = 0;
bool bridge[maxm<<1];
struct Edge {
    int to, nxt;
} edges[maxm<<1];
void addEdge(int u, int v) {
    Edge e = {v, head[u]};
    edges[ecnt] = e;
    head[u] = ecnt++;
}

void tarjan(int u, int p) {
    dfn[u] = low[u] = ++id;
    for (int e = head[u]; ~e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == p) continue;
        if (dfn[to]) low[u] = min(low[u], dfn[to]);
        else {
            tarjan(to, u);
            low[u] = min(low[u], low[to]);
            if (low[to] > dfn[u]) {
                bridge[e] = bridge[e^1] = 1;
            }
        }
    }
}

// f 代表 from (ecc编号)
void dfs(int u, int f) {
    from[u] = f;
    for (int e = head[u]; ~e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (from[to] || bridge[e]) continue;  // to已访问,或者该边是桥
        dfs(to, f);
    }
}

vector<int> adj[maxn];
void rebuild() {
    for (int u = 1; u <= n; u++) {
        for (int e = head[u]; ~e; e = edges[e].nxt) {
            int v = edges[e].to;
            int fu = from[u], fv = from[v];
            if (fu == fv) continue;
            adj[fu].push_back(fv);
        }
    }
}

int sz[maxn], son[maxn], top[maxn], tr_id[maxn];
int par[maxn][20], dep[maxn];
void dfs2(int u, int p) {
    sz[u] = 1;
    dep[u] = dep[p] + 1;
    par[u][0] = p;
    for (int j = 1; j <= 19; j++) par[u][j] = par[par[u][j-1]][j-1];
    int maxsz = -1;
    for (int i = 0; i < adj[u].size(); i++) {
        int to = adj[u][i];
        if (to == p) continue;
        dfs2(to, u);
        sz[u] += sz[to];
        if (sz[to] > maxsz) maxsz = sz[to], son[u] = to;
    }
}

void dfs3(int u, int p, int topf) {
    top[u] = topf;
    tr_id[u] = ++id;
    if (son[u]) dfs3(son[u], u, topf);
    for (int i = 0; i < adj[u].size(); i++) {
        int to = adj[u][i];
        if (to == p || to == son[u]) continue;
        dfs3(to, u, to);
    }
}

struct tree_node {
    int sum;
    bool lazy;
} tr[maxn<<2];

void push_up(int cur) {
    tr[cur].sum = tr[cur<<1].sum + tr[cur<<1|1].sum;
}

void push_down(int cur) {
    if (!tr[cur].lazy) return;
    tr[cur].lazy = 0;
    int l = cur<<1, r = cur<<1|1;
    tr[l].lazy = tr[r].lazy = 1;
    tr[l].sum = tr[r].sum = 0;
}

void update(int cur, int l, int r, int L, int R) {
    if (l >= L && r <= R) {
        tr[cur].lazy = 1;
        tr[cur].sum = 0;
        return;
    }
    push_down(cur);
    int mid = (l+r) >> 1;
    if (L <= mid) update(cur<<1, l, mid, L, R);
    if (R > mid) update(cur<<1|1, mid+1, r, L, R);
    push_up(cur);
}

int query(int cur, int l, int r, int L, int R) {
    if (l >= L && r <= R) return tr[cur].sum;
    push_down(cur);
    int mid = (l+r) >> 1;
    int res = 0;
    if (L <= mid) res += query(cur<<1, l, mid, L, R);
    if (R > mid) res += query(cur<<1|1, mid+1, r, L, R);
    return res;
}

void build_tree(int cur, int l, int r) {
    if (l == r) {
        tr[cur].sum = 1;
        return;
    }
    int mid = (l+r) >> 1;
    build_tree(cur<<1, l, mid);
    build_tree(cur<<1|1, mid+1, r);
    push_up(cur);
}

int jump(int u, int d) {
    int j = 0;
    while (d) {
        if (d&1) u = par[u][j];
        j++, d >>= 1;
    }
    return u;
}

int LCA(int u, int v) {
    if (dep[u] < dep[v]) swap(u,v);
    int d = dep[u] - dep[v];
    u = jump(u, d);
    if (u == v) return u;
    for (int j = 19; j >= 0; j--) {
        if (par[u][j] != par[v][j]) 
            u = par[u][j], v = par[v][j];
    }
    return par[u][0];
}


int curans;

void update_path_helper(int u, int v) {
    if (v == -1) return;
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u,v);
        curans -= query(1, 2, ecc, tr_id[top[u]], tr_id[u]);
        update(1, 2, ecc, tr_id[top[u]], tr_id[u]);
        u = par[top[u]][0];
    }
    if (dep[u] > dep[v]) swap(u,v);
    curans -= query(1, 2, ecc, tr_id[u], tr_id[v]);
    update(1, 2, ecc, tr_id[u], tr_id[v]);
}

void update_path(int u, int v) {
    int x = LCA(u,v);
    int d,ux,vx;

    d = dep[u] - dep[x];
    if (!d) ux = -1;
    else ux = jump(u, d-1);

    d = dep[v] - dep[x];
    if (!d) vx = -1;
    else vx = jump(v, d-1);

    update_path_helper(u, ux);
    update_path_helper(v, vx);
}

void clearall() {
    fill(head, head+n+1, -1);
    fill(dfn, dfn+n+1, 0);
    fill(low, low+n+1, 0);
    fill(from, from+n+1, 0);
    fill(bridge, bridge+(m<<1)+2, 0);
    fill(sz, sz+ecc+1, 0);
    fill(son, son+ecc+1, 0);
    fill(top, top+ecc+1, 0);
    fill(tr_id, tr_id+ecc+1, 0);
    for (int i = 1; i <= 4*ecc+5; i++) tr[i].lazy = 0;
    for (int i = 1; i <= ecc; i++) 
        for (int j = 0; j <= 19; j++) par[i][j] = 0;
    fill(dep, dep+ecc+1, 0);
    for (int i = 1; i <= n; i++) adj[i].clear();
    ecnt = id = ecc = 0;
}

int main() {
    fastio;
    int T = 0;
    fill(head, head+maxn, -1);
    while (cin >> n >> m && n && m) {
        T++;
        for (int i = 1; i <= m; i++) {
            int u,v; cin >> u >> v;
            addEdge(u,v); addEdge(v,u);
        }
        tarjan(1, 0);
        for (int i = 1; i <= n; i++) {
            if (!from[i]) dfs(i, ++ecc);
        }
        rebuild();

        id = 0;
        dfs2(1, 0);
        dfs3(1, 0, 1);
        curans = ecc-1;

        cout << "Case " << T << ":\n";
        int Q; cin >> Q;
        if (ecc == 1) {
            while (Q--) {
                int u,v; cin >> u >> v;
                cout << 0 << "\n";
            }
        } else {
            build_tree(1, 2, ecc);
            while (Q--) {
                int u,v; cin >> u >> v;
                update_path(from[u],from[v]);
                cout << curans << "\n";
            }
            cout << "\n";
        }

        clearall();
    }
}

参考链接

  1. https://cloud.tencent.com/developer/article/1732615
  2. https://oi-wiki.org/graph/bcc/
  3. https://blog.csdn.net/fuyukai/article/details/51303292
  4. https://blog.csdn.net/a_forever_dream/article/details/103019013
  5. https://www.cnblogs.com/Aswert/p/14273854.html
  6. https://blog.csdn.net/qq_45458915/article/details/103672762