Funcia
Lv.4dfsgraphscc

Strongly Connected Components

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

Points 0..n-1 are joined by one-way paths edges[i] = [a, b]. Two points are in the same group if each can reach the other. Return [number of groups, size of the largest group].

Examples

nedgesresult
5[[0, 1], [1, 2], [2, 0], [2, 3], [3, 4]][3, 3]
4[[0, 1], [1, 0], [2, 3], [3, 2], [1, 2]][2, 2]
3[][3, 1]

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(n: int, edges: int[][]) → int[]

Constraints

  • 1≤1 \le n ≤100,000\le 100{,}000, 0≤0 \le edges.length ≤200,000\le 200{,}000; repeats and self-loops may appear.

Expected complexity

Time
O(N + M)
Space
O(N + M)

Examples

nedgesExpected
5[[0,1],[1,2],[2,0],[2,3],[3,4]][3,3]
4[[0,1],[1,0],[2,3],[3,2],[1,2]][2,2]
3[][3,1]

Hint

Hint

Strongly connected components: Kosaraju (post-order on the graph, then DFS on the reversed graph in reverse post-order) or Tarjan, iteratively. Peeling one component at a time with forward/backward searches is O(N(N+M))O(N(N + M)) when components are many.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)222 msestimated
C++ (GCC, gnu++23)222 msderived
Python 3.131000 msderived
Java 251414 msderived
Kotlin 2.4 (JVM)1444 msestimated
C# 14 (.NET 10)1444 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness408verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.