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