160D MST 边分类用桥判断临时图中哪些边不可替代。这一次没有权重：我们可以自由选择起点和终点，希望两点之间“无论怎样绕路都必须经过”的边尽量多。

直接枚举两点再检查所有路径行不通。关键是把两个问题分开：哪些边可能不可替代？这些边对同一对端点能贡献多少？ 前者由桥判定回答，后者在压缩后的树上变成距离。

官方题目与输入边界

题目为 Codeforces 1000E We Need More Bosses。下表按官方题目页及官方题库 API核对，本文只重述求解所需的图模型。

项目 官方约定
难度与标签 2100；dfs and similar、graphs、trees
图 连通、无向、无自环、无重边
顶点 n 2 ≤ n ≤ 300000
边数 m n−1 ≤ m ≤ 300000
端点 1 到 n，两端不同
目标 自选 s、t，使所有 s 到 t 路径共同包含的边数最大
输出 一个整数，不要求输出端点或路径
时间、内存 2 秒、256 MB

“必经”不是最短路中的必经：绕远路也允许，只要存在一条避开某边的路径，该边就不能计入这对端点的答案。也不是“选一条经过桥最多的任意游走”，重复往返同一条边不会增加必须穿越的不同关口。

为什么只需考虑桥

无向边 e 是桥，当且仅当删掉它会让原连通图断开。

如果 e 不是桥，删掉后整张图仍连通，任意 s、t 都存在避开 e 的路径，所以 e 不可能对任何一对端点必经。反过来，删掉一条桥后产生两侧：s、t 分居两侧时，每条路径都必须穿越它；两点同侧时则能在该侧内部连接，不必穿越它。

因此答案不是桥的总数，而是能够同时把同一对端点分开的桥数。三条边组成的星形图有三座桥，任意两点间最多只经过两座；这个例子已经否定了“数出所有桥就输出”的解法。

朴素删边 BFS 可以找桥，复杂度 O(m(n+m))；再枚举所有点对代价更高。它适合独立验证小图，不适合三十万顶点的正式输入。

low 保存了什么，桥在哪里判定

用 tin[u] 记录 DFS 首次访问 u 的序号。low[u] 汇总：从 u 的 DFS 子树沿树边向下，再至多沿一条非父边回到已访问祖先，能够到达的最小 tin。

遇到的边 处理
通往未访问 v 进入子树，等 v 完成后用 low[v] 更新 low[u]
非父边通往已访问 v 用 tin[v] 更新 low[u]
当前顶点的父边 按边编号跳过，避免把原路返回当成绕路

对 DFS 树边 u→v，如果 low[v]>tin[u]，v 的整棵子树没有其他途径连接 u 或更高祖先，删掉这条边必然断开，它就是桥。若 low[v]≤tin[u]，存在非父边绕回去，再沿树边连接到 u，可以避开 u—v；它不是桥。注意是严格大于，不是大于等于。

无向 DFS 中出现指向已完成后代的方向时，使用其更大的 tin 不会把 low 降低。不要机械换成 low[v]，否则会把别的子树可达信息错误当成当前非树边直接提供的连接。

本文用显式栈模拟递归：每个顶点保存下一条待处理邻边下标。只有弹出 v、它的邻边全部处理完时，才能把 low[v] 传给父亲并判断父边。 若在首次发现 v 时就判断，low 尚未汇总回边，会把环中的边误判为桥。

八个顶点的手算

按以下顺序输入：1—2、2—3、3—1、3—4、4—5、5—6、6—4、5—7、7—8。从 1 开始，按邻接表顺序遍历。

顶点 tin 完成时 low 父亲 父边是桥吗
1 1 1 无 不适用
2 2 1 1 否，三角形提供绕路
3 3 1 2 否
4 4 4 3 是，4>3
5 5 4 4 否，第二个三角形提供绕路
6 6 4 5 否
7 7 7 5 是，7>5
8 8 8 7 是，8>7

删桥后有四块：A={1,2,3}、B={4,5,6}、C={7}、D={8}。剩余桥为 A—B、B—C、C—D。选 s=1、t=8 可以同时跨过三座桥；选 s=4、t=6 则没有必经边。

两个三角形及两个单点删桥后压成四个顶点，桥树为A到B到C到D，直径为三条边
原创八顶点示意：三角形内部可绕路，红色连接是桥。下方距离按边计数。查看完整图

压缩后为什么一定是一棵树

先删除全部桥，在剩余图中找连通块，把每块压成一个点，并把原桥连接到对应块。

原图连通，因此压缩图也连通。若压缩图有环，环上任一条原桥都能沿环的另一侧、再借助块内路径绕开，与“桥”矛盾。因此压缩图连通且无环，是树。

如果桥数为 b，块数就是 b+1；没有桥时所有顶点压成一个点。这里的块常称为边双连通分量，包括孤立单点；不是强连通分量，也不是按割点分解的点双连通分量。

设 s、t 所在块为 S、T。桥树上 S 到 T 有唯一简单路径。这条路径上的每座桥都把 S、T 分到两侧，必经；路径外的桥不会分开它们，不必经过。块内非桥也不能必经。于是原问题的数值恰好等于树上距离 dist(S,T)，最大值就是直径。

两次 BFS 为什么能找到直径

桥树无权，任取顶点 r，第一次 BFS 找最远点 x；从 x 再 BFS，最远点 y 的距离就是直径。BFS 的距离按边数计算，不要给最终结果加一。

给出一个处理并列最远点的证明。以 r 为根，取任意一条直径 a—b，令 c=LCA(a,b)，其长度为深度之和减两倍 depth(c)。x 的深度不小于 a、b。

若 x 不在 c 的子树中，LCA(x,a) 是 c 的严格祖先，故 dist(x,a)>dist(a,b)，矛盾。若 x 在 c 的子树中，则至少可选 a、b 中一个端点 z，使 LCA(x,z)=c（若 c 恰为某端点，选该端点也成立）。由于 depth(x) 不小于另一个端点的深度，dist(x,z)≥dist(a,b)。直径已是最大距离，所以只能相等，x 是某条直径的端点。

第二次 BFS 求 x 的最远距离，不小于这条直径，也不可能超过全局直径，因此正好等于答案。第一次出现并列最远点时取任何一个都成立。此证明用到了树的唯一路径；不要把两次 BFS 当作一般有环图求直径的定理。

完整 C++17 实现

不使用递归 DFS。图保存原始边编号；删桥分块用迭代栈，直径用数组队列。代码依赖官方的连通输入约定。

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
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

struct Edge { int to, id; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<Edge>> g(n);
    vector<pair<int, int>> edges(m);
    for (int id = 0; id < m; ++id) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        edges[id] = {u, v};
        g[u].push_back({v, id});
        g[v].push_back({u, id});
    }
    vector<int> tin(n, 0), low(n), parent(n, -1), parentEdge(n, -1);
    vector<size_t> nextEdge(n, 0);
    vector<char> bridge(m, false);
    vector<int> stack;
    stack.reserve(n);
    int timer = 0;
    tin[0] = low[0] = ++timer;
    stack.push_back(0);
    while (!stack.empty()) {
        int u = stack.back();
        if (nextEdge[u] < g[u].size()) {
            Edge e = g[u][nextEdge[u]++];
            if (e.id == parentEdge[u]) continue;
            int v = e.to;
            if (tin[v] == 0) {
                parent[v] = u;
                parentEdge[v] = e.id;
                tin[v] = low[v] = ++timer;
                stack.push_back(v);
            } else {
                low[u] = min(low[u], tin[v]);
            }
        } else {
            stack.pop_back();
            if (parent[u] != -1) {
                int p = parent[u];
                bridge[parentEdge[u]] = (low[u] > tin[p]);
                low[p] = min(low[p], low[u]);
            }
        }
    }
    vector<int> component(n, -1);
    int count = 0;
    for (int start = 0; start < n; ++start) {
        if (component[start] != -1) continue;
        stack.push_back(start);
        component[start] = count;
        while (!stack.empty()) {
            int u = stack.back();
            stack.pop_back();
            for (Edge e : g[u]) {
                if (bridge[e.id] || component[e.to] != -1) continue;
                component[e.to] = count;
                stack.push_back(e.to);
            }
        }
        ++count;
    }
    vector<vector<int>> tree(count);
    for (int id = 0; id < m; ++id) {
        if (!bridge[id]) continue;
        auto [u, v] = edges[id];
        int a = component[u], b = component[v];
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
    auto farthest = [&](int start) {
        vector<int> distance(count, -1), queue(count);
        int head = 0, tail = 0, best = start;
        queue[tail++] = start;
        distance[start] = 0;
        while (head < tail) {
            int u = queue[head++];
            if (distance[u] > distance[best]) best = u;
            for (int v : tree[u]) {
                if (distance[v] != -1) continue;
                distance[v] = distance[u] + 1;
                queue[tail++] = v;
            }
        }
        return pair<int, int>{best, distance[best]};
    };
    int x = farthest(0).first;
    cout << farthest(x).second << '\n';
    return 0;
}

找桥、分块、建树和两次 BFS 都只扫描线性数量的顶点与邻边，总时间 O(n+m)，总空间 O(n+m)。tin、距离与最终答案不超过 n，int 足够；没有权重和或乘法费用。三十万顶点长链需要显式栈，不能依赖默认线程调用栈深度。

边界与独立验证

情形 结果或检查点
两个顶点一条边 答案 1
一条长链 每条边都是桥，答案 n−1
一个大环 无桥，压缩成一个点，答案 0
星形树 n≥3 时答案 2，不是桥总数 n−1
两环仅共享一个顶点 可以有割点但没有桥，答案 0
两环由一条边连接 桥树两个顶点，答案 1
有多个最远点 任取一个最远点，仍是某条直径的端点
非连通输入 不属于官方约定；不能直接把多个桥树当成一棵树
平行边 官方排除，程序仍按父边编号跳过，避免错误依赖父顶点

tests/verify-bridge-tree-article.cjs 提取正文代码，以 C++17 和警告选项编译。参考解对每条边做删除后的连通搜索，直接统计每一对原图端点被多少次删除分隔；不使用 low、桥树或两次 BFS。还覆盖小图穷举、随机连通图、打乱输入及最大规模链、星和环。

接下来可把本文与树上 LCA 查询对照：本文只求全局最大值，两次 BFS 足够；若改成多次询问指定点对的必经桥数，先映射到桥树顶点，再用 LCA 求树上距离。