MST Cut Property Check

Problem

Find the lightest edge crossing the cut defined by a vertex subset, which by the cut property belongs to some minimum spanning tree.

edges is a list of [u, v, w] triples for an undirected weighted graph and subset lists the vertices on one side. Return [u, v, w] for the crossing edge with the smallest weight, sorting the endpoints and breaking ties by smaller u then v. Return [] when no edge crosses the cut.

Hint

Scan all edges and keep the minimum among those with exactly one endpoint in the subset.

Test cases

case 1

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

expected: [1,2,2]

case 2

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

expected: [0,2,2]

case 3

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

expected: []

case 4

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

expected: [0,1,3]

Starter codePython

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

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