Bottleneck Spanning Weight

Problem

Minimize the heaviest edge used by a spanning tree.

Run Kruskal on the undirected [u, v, w] list and return the weight of the last edge added to the tree; that greedy bound is optimal for the bottleneck objective. Return -1 when no spanning tree exists, and 0 when n <= 1.

Hint

Any spanning tree must bridge the cut that forced the last heavy edge, so that weight is a lower bound.

Test cases

case 1

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

expected: 3

case 2

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

expected: 5

case 3

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

expected: -1

case 4

in: [2,[[0,1,7]]]

expected: 7

case 5

in: [1,[]]

expected: 0

Starter codePython

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

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