Transitive Closure Row Bits

Problem

Return one row of the transitive closure as 0/1 bits.

For node k, bit j is 1 exactly when j is reachable from k by a directed path, and bit k is always 1 because a node reaches itself with a zero-length walk. edges is a directed [u, v] list. The returned list has length n.

Hint

One graph search from k fills the whole row, including k itself.

Test cases

case 1

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

expected: [1,1,1]

case 2

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

expected: [0,0,1]

case 3

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

expected: [0,1,0]

case 4

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

expected: [0,0,1,1]

case 5

in: [1,[],0]

expected: [1]

Starter codePython

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

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