Tarjan Low-Link Values

Problem

Return the Tarjan low-link value of every node of a directed graph.

Run Tarjan's SCC DFS visiting nodes 0 to n-1 and neighbors in increasing order: low[v] is the smallest discovery time reachable from v's subtree by tree or back edges to nodes still on the stack. edges is a list of [u, v] pairs. The result is the low array in node order.

Hint

Back edges only lower the value while their target is still on the stack.

Test cases

case 1

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

expected: [0,0,0]

case 2

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

expected: [0,0,0,3]

case 3

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

expected: [0,1,3,1]

case 4

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

expected: [0,1,2]

case 5

in: [1,[]]

expected: [0]

Starter codePython

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

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