Warshall Reachability

Problem

Compute the reflexive reachability sets of a directed graph with the Warshall algorithm.

Return a list of n sorted lists; the i-th list contains every node reachable from i through zero or more edges, so it always includes i itself. edges is a list of [u, v] pairs.

Hint

Initialize the diagonal to True so each node reaches itself.

Test cases

case 1

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

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

case 2

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

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

case 3

in: [3,[]]

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

case 4

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

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

Starter codePython

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

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