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,图连通且无重复边。

自建示例

唯一最小生成树中的边全部关键:

输入: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 的最小生成树,没有单条边必须出现。