「Network」网络

形式化题目

给定一张 $N$ 个点、 $M$ 条边的无向连通图 $G$ 。依次加入 $Q$ 条边 $(a_1,b_1), (a_2,b_2), \dots, (a_Q,b_Q)$ ，对每个 $i$ 求出加入第 $i$ 条边之后图中桥的数量。

这里「桥」指删掉后会使图不连通的边；加入的边是累积的，不会撤销。

约束： $N \leqslant 10^5$ ， $M \leqslant 2 \times 10^5$ ， $Q \leqslant 1000$ 。

注意 $Q$ 只有 $10^3$ ，而 $M$ 高达 $2 \times 10^5$ ：图很大，但「重新来一遍」的机会很少。这个不对称就是本题的题眼。

正解

思路

第一步：先发现「桥只会减少」。

往图里加边只会制造新的环，不会破坏已有的环。因此一条非桥边永远是非桥边，一条桥边有可能因为新环覆盖它而失效，但绝不会反过来。所以答案是单调不增的。

更精确地说，新边 $(a,b)$ 只会消灭它所在环上的桥；不在任何新环上的桥保持不变。于是问题变成：怎么快速找出「被 $(a,b)$ 消灭的那些桥」。

第二步：把一般图压缩成树。

把图上所有非桥边构成的连通块各自缩成一个点——这正好是边双连通分量，记为 $\mathrm{id}(v)$ 。缩点之后，原图的桥就变成了这些新点之间的边。关键结论是：

缩点得到的图是一棵树，称为桥树。

理由是：如果缩点图里有环，环上每条边都不可能是桥（环上两点总有两条边不相交的路径），与缩点方式矛盾；又因为原图连通，缩点图连通。连通无环即树。

于是「 $(a,b)$ 消灭它所在环上的桥」可以翻译得很干净：设 $u = \mathrm{id}(a)$ 、 $v = \mathrm{id}(b)$ ，树上有唯一的 $u \to v$ 路径，路径上的每条树边都恰好是一条被新边消灭的桥，路径之外的桥全都不受影响。

维护桥数就变成了维护桥树上的剩余边数：每次询问把树上 $u \to v$ 路径上的所有边删掉。

下图是样例第 2 组数据（ $N=4$ ，边 $1-2, 2-1, 2-3, 1-4$ ）的桥树：左边是原图，两条 $1-2$ 之间的重边让 $1,2$ 落进同一个边双连通分量，整张图缩成三个点、两条桥。

graph LR
    subgraph G["原图"]
        A1["1"] === A2["2"]
        A2 --- A3["3"]
        A1 --- A4["4"]
    end
    subgraph T["桥树"]
        B12["块{1,2}"] --- B3["块{3}"]
        B12 --- B4["块{4}"]
    end

观察重点：重边 $1-2$ 不是桥，于是 $1,2$ 合成一个块；原图的三条非桥边在桥树里全部消失，只剩下两条真正的桥。加 $3-4$ 相当于在桥树上删掉 $3 \to \{1,2\} \to 4$ 这条路径上的两条边，桥数从 2 直接降到 0，这就是样例输出的 2、0。

第三步：用并查集把「删路径」做成摊还线性。

树上的路径删边不必逐条找。维护一个并查集：若某个节点的父边已经被删，就把它并进父亲的集合。这样 find(u) 直接给出「沿父边向上的第一个还有桥的点」。

text

1
2
3
4
5
6while u != v:
    if depth[u] < depth[v]:
        u, v = v, u          # 让 u 是更深的那一侧
    uf[u] = find(uf, parent[u])
    u = uf[u]
    remaining -= 1

为什么取更深的一侧一定对？设 $w$ 是 $u,v$ 的最近公共祖先。当 $u \neq v$ 时，二者不可能都落在 $w$ 上，所以较深的那个点到父亲的边必定在 $u \to v$ 的路径上，删掉它不会多删；上跳后 $u,v$ 的距离严格变小，循环必然终止于 $u = v$ ，此时路径上的桥正好全部删完，也不会少删。

每个树节点至多被合并一次，所以 $Q$ 次询问的总跳数不超过 $N-1$ 。

下面把样例第 2 组的两步询问摊开，看 remaining 怎么走：

步骤	询问	桥树上的路径	本次删掉的桥	输出
初始	—	—	—	桥数 $= 2$
第 1 次	$1\ 2$	块 $\{1,2\}$ 到自身	无（两端已同块）	`2`
第 2 次	$3\ 4$	$3 \to \{1,2\} \to 4$	两条	`0`

第 1 次询问两端落在同一个块里，find 结果相等，循环体一次都不执行，这正是「重边不改变任何东西」在算法里的体现。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 13:30
 * update_at: 2026-10-10 13:30
 */

// 桥 + 块树询问：先 Tarjan 求桥，删桥后给每个点标出 2-边连通块号，
// 再把块当点、桥当边建出桥森林；每次询问把 u,v 在森林路径上的桥逐一缩掉，
// 输出当前还没被任何一次询问覆盖过的桥数。
#include <cstdio>
#include <vector>
using namespace std;

typedef long long ll;

int n, m;
vector<int> head, nxt, toArr;

struct Frame { // 迭代 Tarjan 的栈帧
    int u, e, inArc; // 点、待处理的邻接弧、进入当前点的那条弧
};

vector<char> markBridges() { // 求桥：bridge[e] = 1 表示弧 e 属于某条桥
    vector<int> tin(n + 1, 0), low(n + 1, 0); // 0 兼作「没访问过」
    vector<char> bridge(toArr.size(), 0);
    int timer = 0;
    for (int s = 1; s <= n; ++s) {
        if (tin[s]) continue;
        timer += 1;
        tin[s] = low[s] = timer;
        vector<Frame> stk;
        Frame f;
        f.u = s; f.e = head[s]; f.inArc = -1;
        stk.push_back(f);
        while (!stk.empty()) {
            Frame top = stk.back();
            if (top.e) {
                stk.back().e = nxt[top.e];
                if (top.e == (top.inArc ^ 1)) continue; // 配对弧：无向边不能当回边用
                int v = toArr[top.e];
                if (tin[v]) {
                    if (tin[v] < low[top.u]) low[top.u] = tin[v];
                } else {
                    timer += 1;
                    tin[v] = low[v] = timer;
                    Frame nf;
                    nf.u = v; nf.e = head[v]; nf.inArc = top.e;
                    stk.push_back(nf);
                }
            } else {
                stk.pop_back();
                if (!stk.empty()) {
                    int p = stk.back().u;
                    if (low[top.u] < low[p]) low[p] = low[top.u];
                    if (low[top.u] > tin[p]) { // 子树回不到 p 之上，这条弧的边是桥
                        bridge[top.inArc] = 1;
                        bridge[top.inArc ^ 1] = 1;
                    }
                }
            }
        }
    }
    return bridge;
}

int findUF(vector<int> &uf, int x) { // 并查集找根 + 路径压缩（迭代写法）
    int r = x;
    while (uf[r] != r) r = uf[r];
    while (uf[x] != r) {
        int old = uf[x];
        uf[x] = r;
        x = old;
    }
    return r;
}

int main() {
    int caseNo = 0;
    while (true) {
        if (scanf("%d %d", &n, &m) != 2) break; // 输入结束
        if (n == 0 && m == 0) break;
        caseNo += 1;

        head.assign(n + 1, 0);
        nxt.assign(2 * m + 2, 0);
        toArr.assign(2 * m + 2, 0);
        for (int i = 1; i <= m; ++i) { // 无向边存成两条配对弧 2i 与 2i+1
            int a, b;
            scanf("%d %d", &a, &b);
            nxt[2 * i] = head[a]; toArr[2 * i] = b; head[a] = 2 * i;
            nxt[2 * i + 1] = head[b]; toArr[2 * i + 1] = a; head[b] = 2 * i + 1;
        }

        vector<char> bridge = markBridges();

        // 删掉所有桥后给每个点标出它所属的块
        vector<int> block(n + 1, 0);
        int blocks = 0;
        for (int s = 1; s <= n; ++s) {
            if (block[s]) continue;
            blocks += 1;
            block[s] = blocks;
            vector<int> stk;
            stk.push_back(s);
            while (!stk.empty()) {
                int u = stk.back();
                stk.pop_back();
                for (int e = head[u]; e; e = nxt[e]) {
                    int v = toArr[e];
                    if (!bridge[e] && !block[v]) {
                        block[v] = blocks;
                        stk.push_back(v);
                    }
                }
            }
        }

        int treeEdges = 0; // 桥数：两条配对弧都被标记，除以 2
        for (int i = 0; i < (int)bridge.size(); ++i) if (bridge[i]) treeEdges += 1;
        treeEdges /= 2;

        // 块当点、桥当边建桥森林（端点由配对弧 e 与 e^1 直接给出，只扫偶数弧）
        vector<int> thead(blocks + 1, 0), tnxt(2 * treeEdges + 2, 0), tto(2 * treeEdges + 2, 0);
        int cnt = 0;
        for (int e = 2; e < (int)toArr.size(); e += 2) {
            if (!bridge[e]) continue;
            int x = block[toArr[e]], y = block[toArr[e ^ 1]];
            cnt += 1;
            tnxt[cnt] = thead[x]; tto[cnt] = y; thead[x] = cnt;
            cnt += 1;
            tnxt[cnt] = thead[y]; tto[cnt] = x; thead[y] = cnt;
        }
        vector<int> tparent(blocks + 1, 0), tdepth(blocks + 1, 0); // 0 = 没访问过，-1 = 树根
        for (int s = 1; s <= blocks; ++s) {
            if (tparent[s]) continue;
            tparent[s] = -1;
            vector<int> stk;
            stk.push_back(s);
            while (!stk.empty()) {
                int u = stk.back();
                stk.pop_back();
                for (int e = thead[u]; e; e = tnxt[e]) {
                    int v = tto[e];
                    if (tparent[v] == 0) {
                        tparent[v] = u;
                        tdepth[v] = tdepth[u] + 1;
                        stk.push_back(v);
                    }
                }
            }
        }

        int remaining = treeEdges;
        vector<int> uf(blocks + 1);
        for (int i = 0; i <= blocks; ++i) uf[i] = i;

        int q;
        scanf("%d", &q);
        if (caseNo > 1) printf("\n"); // 复刻 py 的用例之间空一行
        printf("Case %d:\n", caseNo);
        for (int i = 0; i < q; ++i) {
            int a, b;
            scanf("%d %d", &a, &b);
            int u = findUF(uf, block[a]), v = findUF(uf, block[b]);
            while (u != v) { // 只会往上并
                if (tdepth[u] < tdepth[v]) { int t = u; u = v; v = t; }
                int up = tparent[u]; // 深的一侧到父亲的桥必然落在路径上
                uf[u] = findUF(uf, up);
                u = uf[u];
                remaining -= 1;
            }
            printf("%d\n", remaining);
        }
    }
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 00:56
# update_at: 2026-10-02 01:20

import sys
from array import array


def mark_bridges(n: int, head: array, nxt: array, to: array) -> bytearray:
    """迭代 Tarjan 求桥：bridge[e] = 1 表示弧 e 属于某条桥。

    无向边存成两条配对弧 2i 与 2i+1，所以弧 e 的配对弧就是 e ^ 1；
    栈帧写成 [当前点, 待处理的邻接弧, 进入当前点的那条弧]，
    第三条专门用来跳过沿同一条边回到父亲的配对弧。
    """
    tin = array('i', bytes(4 * (n + 1)))            # 0 兼作“没访问过”
    low = array('i', bytes(4 * (n + 1)))
    bridge = bytearray(len(to))
    timer = 0
    for s in range(1, n + 1):
        if tin[s]:
            continue
        timer += 1
        tin[s] = low[s] = timer
        stack = [[s, head[s], -1]]
        while stack:
            top = stack[-1]
            e = top[1]
            if e:
                top[1] = nxt[e]
                if e == (top[2] ^ 1):               # 配对弧：无向边不能当回边用
                    continue
                u, v = top[0], to[e]
                if tin[v]:
                    if tin[v] < low[u]:
                        low[u] = tin[v]
                else:
                    timer += 1
                    tin[v] = low[v] = timer
                    stack.append([v, head[v], e])
            else:
                stack.pop()
                if stack:
                    p = stack[-1][0]
                    if low[top[0]] < low[p]:
                        low[p] = low[top[0]]
                    if low[top[0]] > tin[p]:        # 子树回不到 p 之上，这条弧的边是桥
                        bridge[top[2]] = bridge[top[2] ^ 1] = 1
    return bridge


def label_blocks(n: int, head: array, nxt: array, to: array, bridge: bytearray) -> tuple[array, int]:
    """删掉所有桥后给每个点标出它所属的块，返回块号表与块总数。"""
    block = array('i', bytes(4 * (n + 1)))
    total = 0
    for s in range(1, n + 1):
        if block[s]:
            continue
        total += 1
        block[s] = total
        stack = [s]
        while stack:
            u = stack.pop()
            e = head[u]
            while e:
                v = to[e]
                if not bridge[e] and not block[v]:
                    block[v] = total
                    stack.append(v)
                e = nxt[e]
    return block, total


def bridge_forest(blocks: int, tree_edges: int, block: array, to: array, bridge: bytearray) -> tuple[array, array]:
    """把块当成点、桥当成边，建出桥森林，返回每个块的父块与深度（根深度 0）。

    桥森林的边数等于桥数，而且两个端点由配对弧 e 与 e ^ 1 直接给出，
    所以只扫偶数编号的弧就够了。原图连通时它就是一棵树。
    """
    thead = array('i', bytes(4 * (blocks + 1)))
    tnxt = array('i', bytes(8 * tree_edges + 8))
    tto = array('i', bytes(8 * tree_edges + 8))
    cnt = 0
    for e in range(2, len(to), 2):
        if not bridge[e]:
            continue
        x, y = block[to[e]], block[to[e ^ 1]]
        cnt += 1
        tnxt[cnt] = thead[x]; tto[cnt] = y; thead[x] = cnt
        cnt += 1
        tnxt[cnt] = thead[y]; tto[cnt] = x; thead[y] = cnt

    parent = array('i', bytes(4 * (blocks + 1)))     # 0 = 没访问过，-1 = 所在树的根
    depth = array('i', bytes(4 * (blocks + 1)))
    for s in range(1, blocks + 1):
        if parent[s]:
            continue
        parent[s] = -1                              # 根用 -1 做哨兵，0 留给“没访问过”
        stack = [s]
        while stack:
            u = stack.pop()
            e = thead[u]
            while e:
                v = tto[e]
                if parent[v] == 0:
                    parent[v] = u
                    depth[v] = depth[u] + 1
                    stack.append(v)
                e = tnxt[e]
    return parent, depth


def find(uf: array, x: int) -> int:
    """并查集找根，同时做路径压缩（迭代写法，避免递归深度）。"""
    r = x
    while uf[r] != r:
        r = uf[r]
    while uf[x] != r:
        uf[x], x = r, uf[x]
    return r


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    case_no = 0
    while True:
        n, m = next(data), next(data)
        if n == 0 and m == 0:
            break
        case_no += 1

        head = array('i', bytes(4 * (n + 1)))
        nxt = array('i', bytes(8 * m + 8))
        to = array('i', bytes(8 * m + 8))
        for i in range(1, m + 1):
            a, b = next(data), next(data)
            nxt[2 * i], to[2 * i], head[a] = head[a], b, 2 * i
            nxt[2 * i + 1], to[2 * i + 1], head[b] = head[b], a, 2 * i + 1

        bridge = mark_bridges(n, head, nxt, to)
        block, blocks = label_blocks(n, head, nxt, to, bridge)
        tree_edges = sum(bridge) // 2              # 两条配对弧都被标记，除以 2 才是边数
        tparent, tdepth = bridge_forest(blocks, tree_edges, block, to, bridge)

        remaining = tree_edges
        uf = array('i', range(blocks + 1))          # 已经缩成一团的块用并查集合并（每个块自成一类）

        q = next(data)
        answers = []
        for _ in range(q):
            a, b = next(data), next(data)
            u, v = find(uf, block[a]), find(uf, block[b])
            while u != v:                           # 只会往上并，最后一次询问前必然停止
                if tdepth[u] < tdepth[v]:
                    u, v = v, u                     # 让 u 是更深的那一侧
                up = tparent[u]                     # 深的一侧到父亲的桥必然落在路径上
                uf[u] = find(uf, up)
                u = uf[u]
                remaining -= 1
            answers.append(remaining)

        out.append(f"Case {case_no}:")
        out += map(str, answers)
        out.append("")

    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    solve()

复杂度

阶段	复杂度
Tarjan 求初始桥	$O(N + M)$
缩点、建桥树、求父与深度	$O(N + M)$
$Q$ 次询问的路径缩点	$O\big((N + Q)\,\alpha(N)\big)$
总计	$O\big(N + M + Q\,\alpha(N)\big)$

空间 $O(N + M)$ 。作为对照，每次加边重跑一遍 Tarjan 是 $O(Q(N+M))$ ，在 $Q = 10^3$ 、 $N + M \approx 3 \times 10^5$ 时要约 $3 \times 10^8$ 次操作，而正解只有约 $7 \times 10^5$ 次，差了两个数量级以上。

实现上有三处值得注意：

无向边存成配对弧 $2i$ 与 $2i+1$ ，Tarjan 里用 e == (进入弧 ^ 1) 跳过「沿原路边返回父亲」；
桥的两条配对弧都要打标记，缩点时若只标一条，配对弧会被误当成非桥边而错合并分量；
三个 DFS（Tarjan、标分量、建树）全部写成迭代， $N = 10^5$ 也不会爆栈。

总结

本题的核心不是 Tarjan，而是把「加边」翻译成树上操作：先在初始图上求一次桥并缩成桥树，之后每次加边都等价于在桥树上删掉一条路径上的边。因为加边只减不增，桥树的形状永远不变，父节点和深度一次预处理即可永久使用；再用并查集把「已经删掉的边」合并到父亲，使得 $Q$ 次询问的总跳数与 $Q$ 无关。整个套路就是「一次 Tarjan + 一张桥树 + 一个并查集」。

图示解析

下面这张图串起从建模到输出的全部环节：

text

1
2
3
4
5
6
7
8
9
10输入: N 点 M 边无向连通图 + Q 次加边
`- 观察: 加边只制造环 => 桥只减不增
   `- 关键: 新边 (a,b) 只消灭 "所在环上" 的桥
      `- 结构: 把非桥边缩成块(边双连通分量) => 桥树(一棵树)
         |- 路径之外无影响
         `- "消灭 (a,b) 所在环的桥" ⇔ "删桥树上 id(a) -> id(b) 的路径边"
            `- 维护: 并查集把"已删父边的点"并入父亲
               |- u != v 时取更深一侧上跳, remaining -= 1
               `- 每点至多被合并一次 => 总跳数 <= N-1
                  `- 答案 = remaining (当前桥树剩余边数)

顺着读：无向图上的桥问题先被化简成桥树上的删边问题；桥树不变的性质让父节点与深度可以只算一次；并查集沿用「已缩点集合」的经典技巧，把路径删边摊还到线性。最后剩下的边数就是答案，全程不需要任何动态树结构。

「Network」 网络

目录

形式化题目

正解

思路

代码

复杂度

总结

图示解析