Kruskal 能找到一棵最小生成树，但它挑中的边不一定是所有最优树都要的边。相同权重可以带来多种选择，任意一个排序顺序只展示了其中一种。

在 609E 指定边最优费用中，答案等于原 MST 费用，说明这条边至少可以进入一棵 MST。160D 再问一步：它是否在所有 MST 中都不可缺少？ 答案来自等权分组之后的桥，而不是某次 Kruskal 的选边记录。

官方题目与三类答案

题目为 Codeforces 160D Edges in MST。完整输入约定见官方页面，难度与标签也可查询官方题库 API。

项目 官方约定
难度、标签 2300；dfs and similar、dsu、graphs、sortings
图 连通无向带权图，无自环、无重边
顶点 n 2 到 100000
边数 m n−1 ≤ m ≤ min(100000, n(n−1)/2)
权重 1 到 1000000
输出 按输入边顺序，每条边一行
限制 2 秒、256 MB
输出字符串 精确含义
any 在所有 MST 中都会出现
at least one 至少出现在一棵 MST 中，但不是所有 MST 都包含它
none 不会出现在任何 MST 中

不要把 any 按日常英语猜成“任选一棵”。它在这道题的输出契约中表示每棵 MST 都包含这条边。

一次 Kruskal 为什么不能完成分类

三个顶点组成同权三角形，任何两条边都是 MST。一次 Kruskal 只选两条边，却不能把第三条标成 none；选中的两条也不能标成 any。

逐边强制加入或删除，再重新计算 MST，能判断分类，但重复扫描的代价过高。我们保留 Kruskal 的排序框架，只改变同权边的处理方式：同一组全部判定完，再统一合并。

  1. 冻结更轻边的连通关系

    处理权重 w 时，并查集只能包含权重严格小于 w 的边。

  2. 在本组临时图里判定

    同根边不可选；跨根边先可选，再用桥区分是否必选。

  3. 本组结束后统一合并

    为下一组准备连通关系，不让本组先处理的边抢占选择。

更轻边连通的两端为什么不可选

若 u、v 在权重严格小于 w 的边中已经连通，存在一条全由更轻边组成的路径。加入 e=(u,v,w) 会形成一个环，e 是这个环唯一最重的边。

假设某棵 MST 包含 e，删掉 e 得到一个割。那条更轻路径必有边跨过这个割，可以替换 e 并降低费用，矛盾。因此这样的边一定是 none。

这里必须是“严格更轻”。若原路径上的边与 e 同权，替换不会降低费用，不能用这个证明排除 e。

收缩后为什么可能出现平行边

把严格更轻边的每个连通块压成一个点，只保留本组跨块的边。原图虽然没有重边，临时图仍可能有平行边。

例如先由权重 1 的边连接 1—2、3—4，再处理权重 2 的 1—3 与 2—4。两条边在原图不同，收缩后却都连接 A={1,2} 与 B={3,4}。它们可以互相替代，都不是桥。

权重2的临时图中，A与B之间有两条平行可选边，B到C以及C到D是必选桥
原创六顶点例子的收缩图。这里只显示权重 2 的批次；A、B 内部的更轻边已收缩。两条 A—B 边必须保留各自的边编号。查看原图

完整例子的输入边按下表排序编号，但程序不要求输入已经按权重排列。

编号 原图边与权重 处理本组前的两端 本组角色 分类
e1 1—2，权重 1 两个单点 桥 any
e2 3—4，权重 1 两个单点 桥 any
e3 1—3，权重 2 A—B 平行边之一 at least one
e4 2—4，权重 2 A—B 另一条平行边 at least one
e5 3—5，权重 2 B—C 桥 any
e6 5—6，权重 2 C—D 桥 any
e7 1—4，权重 3 已由权重 1、2 连通 严格更轻路径形成环 none

两棵 MST 分别选择 e3 或 e4，并都保留 e1、e2、e5、e6，总权重都是 8。

临时图中的桥为什么等于必选边

先说明权重层之间的关系。任意 MST 都必须用更轻边连接每个更轻边连通块；否则沿这些更轻边找一个连接缺口，可以替换树中更重的跨割边并降低费用。到了权重 w，MST 的本组选择必须在临时图的每个连通分量中形成生成树，之后才轮到更重边。

临时图中一条跨块边不是自环，所以可以先选它，再把选择扩展成该分量的生成树；接着按 Kruskal 完成后续权重组，就得到一棵包含它的 MST。故所有跨块边至少可选。

如果它是桥，删除后本组连通分量被分开，本组任何生成树都必须使用它，因此所有 MST 必选。如果它不是桥，删除它不改变本组连通性，能构造一棵不含它的本组生成树；也能先选它再扩展。因此它属于部分 MST，而不是全部。

条件 依据 结论
更轻边已经连接两端 用更轻跨割边替换能严格降低费用 none
临时图中的桥 同权层无法绕开，更重边不能替代最优选择 any
临时图中的非桥跨块边 同权环允许替换，既可选也可不选 at least one

这里找的是每个权重组收缩图中的桥，不是原图中的桥。原图不含桥，也可能有 MST 必选边：权重 1、2、3 的三角形中，前两条是必选边。

桥判定要跳过父边而不是父顶点

DFS 中，tin[v] 是进入 v 的时间，low[v] 表示从 v 的 DFS 子树经树边以及至多一条非树边，能够回到的最早进入时间。子树返回后更新父亲的 low；对于树边 p—v，判定式是 **low[v] > tin[p]**。

如果只写“邻点等于父亲就跳过”，A—B 两条平行边都会被跳过，第二条无法作为回到父亲的非树边，程序会把第一条误判为桥。正确做法是只跳过进入当前点的那一条边编号。

自检：原图没有重边，能否把临时图的平行边去重？

不能。每条边都对应一个独立的输入答案，平行边还提供同权替代路径；去重会把原本可替换的连接误判为桥。

完整非递归 C++17 实现

local 数组为并查集根分配临时编号，只重置本组出现的根，不在每组清空 n 个位置。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
100
#include <algorithm>
#include <iostream>
#include <numeric>
#include <utility>
#include <vector>
using namespace std;

struct Edge { int u, v, w; };
struct DSU {
    vector<int> p, size;
    explicit DSU(int n) : p(n + 1), size(n + 1, 1) {
        iota(p.begin(), p.end(), 0);
    }
    int find(int x) {
        while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; }
        return x;
    }
    void unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return;
        if (size[a] < size[b]) swap(a, b);
        p[b] = a; size[a] += size[b];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<Edge> edges(m);
    for (auto &e : edges) cin >> e.u >> e.v >> e.w;
    vector<int> order(m), answer(m, 0), local(n + 1, -1);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int a, int b) {
        if (edges[a].w != edges[b].w) return edges[a].w < edges[b].w;
        return a < b;
    });
    DSU dsu(n);
    for (int left = 0; left < m; ) {
        int right = left;
        while (right < m && edges[order[right]].w == edges[order[left]].w) ++right;
        vector<int> roots;
        vector<vector<pair<int, int>>> graph;
        auto index = [&](int root) {
            if (local[root] == -1) {
                local[root] = static_cast<int>(graph.size());
                roots.push_back(root);
                graph.emplace_back();
            }
            return local[root];
        };
        for (int j = left; j < right; ++j) {
            int id = order[j];
            int a = dsu.find(edges[id].u), b = dsu.find(edges[id].v);
            if (a == b) continue; // answer 0: none
            answer[id] = 1;       // candidate: at least one
            int x = index(a), y = index(b);
            graph[x].push_back({y, id});
            graph[y].push_back({x, id});
        }
        int k = static_cast<int>(graph.size()), timer = 0;
        vector<int> tin(k, -1), low(k), parent(k, -1), parent_edge(k, -1), next(k, 0);
        vector<int> stack;
        for (int root = 0; root < k; ++root) {
            if (tin[root] != -1) continue;
            tin[root] = low[root] = timer++;
            stack.push_back(root);
            while (!stack.empty()) {
                int v = stack.back();
                if (next[v] < static_cast<int>(graph[v].size())) {
                    auto [to, id] = graph[v][next[v]++];
                    if (id == parent_edge[v]) continue;
                    if (tin[to] == -1) {
                        parent[to] = v; parent_edge[to] = id;
                        tin[to] = low[to] = timer++;
                        stack.push_back(to);
                    } else {
                        low[v] = min(low[v], tin[to]);
                    }
                } else {
                    stack.pop_back();
                    int p = parent[v];
                    if (p != -1) {
                        if (low[v] > tin[p]) answer[parent_edge[v]] = 2; // any
                        low[p] = min(low[p], low[v]);
                    }
                }
            }
        }
        for (int root : roots) local[root] = -1;
        for (int j = left; j < right; ++j) {
            const auto &e = edges[order[j]];
            dsu.unite(e.u, e.v);
        }
        left = right;
    }
    const char *labels[] = {"none", "at least one", "any"};
    for (int value : answer) cout << labels[value] << '\n';
}

边界与复杂度

情况或错误 检查方式
原图本来就是树 所有边为 any，与边权是否相同无关
同权三角形或同权环 环上的边均为 at least one
提前合并本组一条边 会错误排除后面的同权替代边
收缩产生平行边 保留不同边编号，只跳过父边
临时图不连通 对每个未访问临时顶点启动 DFS
low 条件写成 ≥ 回到父亲的替代边被误判成桥
每组重新初始化 n 个位置 不同权重很多时退化；只维护本组出现的根
输入编号与排序编号混用 输出必须沿原始边顺序

排序 O(m log m)，并查集 O(m α(n))，所有临时图的边总数不超过 m、出现的点总数不超过 2m，桥 DFS 总计 O(m)。总时间 **O(m log m+m α(n)+n)**，空间 **O(n+m)**。代码不计算总树权重，官方边权、时间戳与编号均可由 int 保存；若扩展到计算总费用，则应使用 long long。

项目 tests/verify-mst-edge-classification-article.cjs 从正文提取并无警告编译代码。小图穷举所有生成树，收集全部最小树并按出现次数分类；较大图则逐边用删除与端点收缩后的 Prim 检查，不把桥算法自身当成标准答案。另含十万顶点长链、大同权环和大量权重组。

回到算法路线，把 609E 的可选性与代价、本题的必选性，与离线连通性比较：并查集维护的时刻不同，得到的信息就不同。