Given a directed graph, find the size of its largest strongly connected component. Pattern focus: Strongly Connected Components. This is an application of SCC decomposition where only the component size matters.
n = number of vertices, edges = directed edges [u, v]
size of the largest SCC
Example 1:
Input:
n = 5 edges = [[1,2],[2,3],[3,1],[3,4],[4,5]]
Output:
3
Explanation:
The largest SCC is {1,2,3} with size 3.
Example 2:
Input:
n = 6 edges = [[1,2],[2,1],[3,4],[4,3],[5,6]]
Output:
2
Explanation:
The largest SCC has size 2.
Example 3:
Input:
n = 4 edges = [[1,2],[2,3],[3,4]]
Output:
1
Explanation:
The graph is acyclic, so every SCC has size 1.