Kosaraju SCC Size Sequence

Problem

Return the sizes of all strongly connected components in decreasing order.

Run Kosaraju's algorithm: DFS to compute finish times, then DFS on the reversed graph in reverse finish order, recording each component size. edges is a list of [u, v] pairs. Return the sorted descending list of sizes.

Hint

The second pass can never leave a strongly connected component.

Test cases

case 1

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

expected: [1,1,1]

case 2

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

expected: [3]

case 3

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

expected: [3,2]

case 4

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

expected: [2,2]

case 5

in: [1,[]]

expected: [1]

Starter codePython

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

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