1047. Tarjan's Algorithm — SCC

Given a directed graph with n nodes and edges, find its strongly connected components using Tarjan's algorithm (single-pass DFS with low-link values). Return the components as a nested array, each component sorted ascending and the list of components sorted. The input is JSON {n, edges}.

Input: JSON {n, edges}.

Output: Nested array — the SCCs, sorted.

Examples

Input: {"n":5,"edges":[[0,1],[1,2],[2,0],[1,3],[3,4]]}
Output: [[0,1,2],[3],[4]]
Explanation: Same SCCs as Kosaraju.

Input: {"n":1,"edges":[]}
Output: [[0]]
Explanation: Single node.

Input: {"n":4,"edges":[[0,1],[2,3]]}
Output: [[0],[1],[2],[3]]
Explanation: All singletons.

Constraints

• 1<=n<=10^5
• directed

Asked by