PreviousNext
Coding/Graphs and trees

Strongly connected component count

Write codeHard35 min

Your task

You are given a directed graph with n nodes labelled 0..n-1 and a list of directed edges [u, v]. A strongly connected component (SCC) is a maximal set of nodes where every node is reachable from every other node in the set. Return the number of strongly connected components. Constraints: 1 <= n <= 2000, the graph may have self-loops and parallel edges, and there may be isolated nodes.

Examples

count_scc(n: int, edges: list[list[int]]) -> int
Example 1
Inputcount_scc(5, [[0, 1], [1, 2], [2, 0], [1, 3], [3, 4]])
Output3