Given a directed graph, count how many strongly connected components it contains. A strongly connected component is a maximal group of vertices where every vertex can reach every other vertex in the group. Pattern focus: SCC. Use Kosaraju's or Tarjan's algorithm to identify components efficiently.
n = number of vertices, edges = directed edges [u, v]
number of strongly connected components
Example 1:
Input:
n = 5 edges = [[1,2],[2,3],[3,1],[3,4],[4,5]]
Output:
3
Explanation:
The components are {1,2,3}, {4}, and {5}.
Example 2:
Input:
n = 4 edges = [[1,2],[2,1],[3,4],[4,3]]
Output:
2
Explanation:
There are two strongly connected pairs.
Example 3:
Input:
n = 3 edges = [[1,2],[2,3]]
Output:
3
Explanation:
No pair of vertices can reach each other in both directions.