Condensation DAG Edge Count

Problem

Count the distinct edges of the condensation: the DAG obtained by contracting every strongly connected component of a directed graph into one node.

Compute components with Kosaraju, then count unique ordered pairs (C1, C2) with C1 different from C2 that contain at least one original edge. edges is a list of [u, v] pairs.

Hint

Deduplicate component pairs with a set after contracting the SCCs.

Test cases

case 1

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

expected: 0

case 2

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

expected: 1

case 3

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

expected: 3

case 4

in: [1,[]]

expected: 0

case 5

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

expected: 0

Starter codePython

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

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