Negative Cycle Reachable Sources

Problem

List every source node from which a negative-weight cycle is reachable.

For each candidate source run Bellman-Ford for n rounds; if round n still relaxes an edge, a negative cycle is reachable from that source. edges is a list of directed [u, v, w] triples that may contain negative weights. Return the qualifying sources in ascending order.

Hint

A change during the n-th full round is the textbook proof that a reachable negative cycle exists.

Test cases

case 1

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

expected: [0,1,2]

case 2

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

expected: []

case 3

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

expected: [1,2]

case 4

in: [1,[]]

expected: []

case 5

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

expected: [0,1]

Starter codePython

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

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