64. Tarjan's Algorithm

Hard

Topics

Helpful tools to learn & understand

Watch key transitions, pointers, and variables update step-by-step.

Open

Read clean, documented implementations across multiple patterns.

View Code

Sketch diagrams on an infinite canvas and draft notes directly inline.

Draw

Input: graph = [[1, 3], [2], [0], [2]]

Output: [[[0, 1, 2, 3]]]

Explanation: The graph has one strongly connected component consisting of all the nodes.

Input: graph = [[1], [2], [3], [0]]

Output: [[0, 1, 2, 3]]

Explanation: All nodes form a single strongly connected component because they form a cycle.

Input: graph = [[1], [2], [0], [4, 5], [5], [6], [4]]

Output: [[4, 5, 6], [0, 1, 2], [3]]

Explanation: There are three SCCs: {4, 5, 6}, {0, 1, 2}, and {3}.

Time Complexity

O(V+E)

Space Complexity

O(V)