Strongly Connected Components (Kosaraju's)
A hard Graph interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Graph
- Sheets
- 1
- Core for
- 11 roles
The problem
Given a directed graph with n nodes and a list of edges, find all strongly connected components using Kosaraju's algorithm. A strongly connected component is a maximal subgraph where every node is reachable from every other node.
Example 1
- Input
- n = 5, edges = [[0,1],[1,2],[2,0],[1,3],[3,4]]
- Output
- [[0,1,2],[3],[4]]
- Why
- Nodes 0,1,2 form a cycle and are strongly connected. Nodes 3 and 4 are each their own component.
Example 2
- Input
- n = 4, edges = [[0,1],[1,2],[2,3],[3,0]]
- Output
- [[0,1,2,3]]
- Why
- All 4 nodes form a single cycle, so one strongly connected component.
Constraints
- 1 <= n <= 10^4
- 0 <= edges.length <= 10^4
How to think about it
Updated 2026-09-09If you condense every strongly connected component into a single mega-node, the resulting graph is guaranteed to be a directed acyclic graph. In a DAG of components, reversing all edges swaps sources and sinks without breaking internal component connectivity. Processing nodes in decreasing order of their finish times on the reversed graph isolates each component one by one without leaks.
Approaches, worst first
Kosaraju two-pass DFS algorithm
time O(V + E) · space O(V + E)
Pass 1: Run DFS on original graph, pushing nodes to a stack as they finish. Pass 2: Transpose all graph edges. Pop nodes from the stack; for each unvisited node, launch a DFS on the transposed graph to collect all vertices reachable in this traversal into a single component.
Tarjan single-pass low-link algorithmWrite this one
time O(V + E) · space O(V + E)
Use discovery times and `low` values with a stack in a single DFS pass. When a node's discovery time equals its low value, pop the stack until that node is removed to form one component.
Where people lose marks · 3
- Pass 2 must process nodes in the exact finish order determined by Pass 1; popping in arbitrary order mixes distinct components.
- Reversing edge directions incorrectly or failing to clear visited state between the two passes.
- Disconnected graphs require running the initial finish-time DFS across all vertices 0 to n - 1.
The theory behind it
Graph — the ground this problem stands on. All Graph problems
What Graph is
A graph is a network of individual points, called vertices or nodes, connected by lines called edges. Think of a subway transit map, an electrical circuit, or a web of social friends. Unlike a tree, a graph has no designated top node and no parent-child hierarchy. Connections can run one-way or both ways, and paths can loop back on themselves to form closed cycles.
When to reach for it
Reach for graph algorithms when inputs describe relationships, networks, flights between cities, course prerequisites, or clone networks. Signals include finding the shortest route across unweighted connections, ordering tasks that depend on earlier tasks, counting isolated clusters, or checking whether a path contains an infinite loop. Whenever problems present pairs of related entities and ask for reachability, distances, or dependencies, graph representations apply.
How the pattern works
First convert edge lists into an adjacency list, mapping each node to an array of its neighbors. Choose your exploration strategy based on the goal: use a queue and breadth-first search to find the shortest path in unweighted networks, or use recursion and depth-first search to explore full paths and detect cycles. Because graphs can have loops, always track visited nodes in a set or boolean array. Add nodes to the visited set at the moment they enter the queue so they are never visited twice.
More Graph problems
Target Roles
Core requirement for 11 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .