Minimum Arborescence Step Lite

Problem

Perform the first greedy step of the Chu-Liu/Edmonds minimum arborescence algorithm.

For every non-root node pick its cheapest incoming edge and sum the weights, then check whether the chosen edges form a cycle. Return [total_weight, has_cycle], or [-1, False] when some non-root node has no incoming edge. edges is a list of directed [u, v, w] triples.

Hint

A cycle of cheapest incoming edges must be contracted in the full algorithm.

Test cases

case 1

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

expected: [3,false]

case 2

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

expected: [-1,false]

case 3

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

expected: [2,false]

case 4

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

expected: [2,true]

case 5

in: [2,[],0]

expected: [-1,false]

Starter codePython

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

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