Maximum Spanning Tree Weight

Problem

Compute the total weight of a maximum spanning tree of an undirected weighted graph with n nodes.

Run Kruskal with edges sorted from heaviest to lightest. Return -1 when the graph is disconnected and 0 when there is a single node. edges is a list of [u, v, w] triples.

Hint

Maximum spanning trees use the same cut reasoning, only the sort order flips.

Test cases

case 1

in: [4,[[0,1,1],[1,2,2],[2,3,3],[0,3,10]]]

expected: 15

case 2

in: [3,[[0,1,5],[1,2,4],[0,2,3]]]

expected: 9

case 3

in: [3,[[0,1,1]]]

expected: -1

case 4

in: [1,[]]

expected: 0

Starter codePython

def maximum_spanning_tree_weight(n, edges):
    # Your code here
    pass

4 test cases · run your code against them in the editor