Minimum Spanning Tree Verification

Problem

Verify whether a proposed set of edges is a minimum spanning tree of an undirected weighted graph with n nodes.

edges is a list of [u, v, w] triples. The proposed tree must have n - 1 edges, form a spanning tree without cycles, and have total weight equal to the Kruskal MST weight. Return a boolean.

Hint

A valid spanning tree must have exact size, no cycle, and minimum total weight.

Test cases

case 1

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

expected: true

case 2

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

expected: false

case 3

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

expected: false

case 4

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

expected: true

case 5

in: [1,[],[]]

expected: true

Starter codePython

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

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