Strongly Connected Components
Mastery
In a directed graph with n nodes, two nodes are in the same strongly connected component (SCC) if each can reach the other. Return the number of SCCs.
For n = 5 and edges = [[0, 1], [1, 2], [2, 0], [1, 3], [3, 4]] the answer is 3 ({0, 1, 2}, {3}, {4}).
Examples
Example 1
Input:
count_scc(5, [[0, 1], [1, 2], [2, 0], [1, 3], [3, 4]])
Output:
3
Example 2
Input:
count_scc(3, [])
Output:
3
Constraints
0 <= n <= 1000000 <= len(edges) <= 200000
Theory
Go to TheoryKeywords
dsa-sheetgraphsspanning-trees-and-components
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.