Transitive Closure

Problem

Compute the transitive closure of a directed graph with n nodes as an n by n 0/1 matrix.

Cell [i][j] is 1 when there is a directed path from i to j using at least one edge, so the diagonal is 1 exactly for nodes lying on a cycle. edges is a list of [u, v] pairs.

Hint

Floyd-Warshall reachability: if i reaches k and k reaches j, then i reaches j.

Test cases

case 1

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

expected: [[0,1,1],[0,0,1],[0,0,0]]

case 2

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

expected: [[1,1,1],[1,1,1],[1,1,1]]

case 3

in: [3,[]]

expected: [[0,0,0],[0,0,0],[0,0,0]]

case 4

in: [2,[[0,0]]]

expected: [[1,0],[0,0]]

case 5

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

expected: [[0,1,1,1],[0,0,1,1],[0,0,0,1],[0,0,0,0]]

Starter codePython

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

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