Second Best MST

Difficulty: Hard · Topic: Minimum spanning trees

For a small weighted undirected graph, return the weight of the second best spanning tree: the cheapest spanning tree whose total weight is strictly larger than the MST weight. If no strictly heavier spanning tree exists, return -1.

Input sizes for this exercise are small enough to enumerate edge subsets, so focus on the definition first.

Examples

second_best_mst(4, [[0,1,1],[1,2,2],[2,3,3],[0,3,4],[0,2,5]])
→ 7

second_best_mst(3, [[0,1,1],[1,2,1],[0,2,1]])
→ -1

Every spanning tree has weight 2.

Target complexity: time O(C(E,V-1) * V), space O(V)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.