1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree ====================================================================== 题目信息 -------- :题号: 1489 :难度: Hard :主题: 图、最小生成树、并查集 :原题: `LeetCode 1489 `_ :重点: 删除关键边会使最小生成树总权重增加或无法连通;伪关键边可出现在至少一棵最小生成树中,但不是关键边 题目重述 -------- 给定包含 ``n`` 个节点的连通无向加权图,``edges[i] = [a,b,weight]``,边的原始编号为 ``i``。 若删除某条边后最小生成树总权重增加或图无法生成 spanning tree,则它是关键边。若某条非关键边能够出现在至少一棵最小生成树中,则它是伪关键边。请返回 ``[关键边编号列表, 伪关键边编号列表]``,内部顺序不限。 ``2 <= n <= 100``,边数不超过 ``200``,图连通且无重复边。 自建示例 -------- 唯一最小生成树中的边全部关键: .. code-block:: text 输入:n = 3, edges = [[0,1,1],[1,2,1],[0,2,2]] 输出:[[0,1],[]] 解释:权重为 1 的两条边构成唯一最小生成树,删除任一都会增加最优总权重。 多个等权生成树中的边均为伪关键: .. code-block:: text 输入:n = 3, edges = [[0,1,1],[1,2,1],[0,2,1]] 输出:[[],[0,1,2]] 解释:任意选择两条边都能形成权重为 2 的最小生成树,没有单条边必须出现。