Transitive Reduction Size

Problem

Count the edges kept by the transitive reduction of a directed graph.

An edge u to v is redundant when there is a directed path from u to v of length at least two, otherwise it must be kept. edges is a list of [u, v] pairs. Return the number of kept edges.

Hint

The transitive reduction keeps exactly the edges that no longer path can replace.

Test cases

case 1

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

expected: 2

case 2

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

expected: 2

case 3

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

expected: 4

Starter codePython

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

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