What is Kosaraju's Algorithm?
Learn how Kosaraju's algorithm finds strongly connected components using two DFS passes, and how to explain it in an interview.
Expected Interview Answer
Kosaraju's algorithm finds all strongly connected components (SCCs) of a directed graph in O(V + E) time using two depth-first search passes: one on the original graph to record finish times, and one on the transposed (edge-reversed) graph processed in reverse finish order.
The first pass runs DFS on the original graph and pushes each vertex onto a stack when its DFS call finishes, so vertices that finish last end up on top. The graph is then transposed by reversing every edge's direction. The second pass pops vertices off the stack one at a time and, for each unvisited vertex, runs DFS on the transposed graph; every vertex reached in that single DFS call forms exactly one strongly connected component. This works because reversing edges and processing in decreasing finish order guarantees that a DFS launched from a vertex in the transposed graph can never leak into a different SCC that finished earlier. SCCs are used to collapse cyclic dependency graphs into a DAG, detect deadlock cycles, and analyze web-link or software module structure.
- O(V + E) linear time for full SCC decomposition
- Conceptually simple: two DFS passes plus a transpose
- Collapses cycles into a condensation DAG
- Foundational for dependency and deadlock analysis
AI Mentor Explanation
Kosaraju's algorithm is like figuring out which cricket teams have mutual head-to-head rivalries, meaning each team in the group has both beaten and lost to every other team in that group at some point. First you tour every team following only "beat" arrows and note the order in which you finish exploring each team's full record, stacking the last-finished team on top. Then you flip every "beat" arrow into "lost to" and revisit teams starting from the top of that stack, and every team reachable in one such sweep forms one mutual-rivalry group. This two-pass, arrow-reversal trick is exactly why it correctly separates the cricketing world into tightly mutual rivalry clusters instead of one tangled mess.
Step-by-Step Explanation
Step 1
First DFS pass, record finish order
Run DFS on the original graph; push each vertex to a stack when its DFS call completes.
Step 2
Transpose the graph
Reverse the direction of every edge to build the transposed graph.
Step 3
Second DFS pass on transpose
Pop vertices off the stack in order; for each unvisited one, run DFS on the transpose to collect one SCC.
Step 4
Build the condensation DAG
Collapse each SCC into a single node to get an acyclic summary graph of dependencies.
What Interviewer Expects
- Explain both DFS passes and why the graph must be transposed between them
- State the O(V + E) linear time complexity
- Justify why processing in decreasing finish order is correct
- Name a use case: cycle collapsing, deadlock detection, dependency analysis
Common Mistakes
- Forgetting to transpose the graph before the second DFS pass
- Running the second pass in the wrong (increasing) finish-time order
- Confusing SCCs (directed graphs) with connected components (undirected graphs)
- Not resetting the visited set between the two DFS passes appropriately
Best Answer (HR Friendly)
“Kosaraju's algorithm finds tightly-connected clusters in a one-way graph, where every node in a cluster can reach every other node and get back. I do one pass to figure out a smart finishing order, reverse all the arrows, then do a second pass in that order, and each sweep in the second pass hands me one cluster.”
Code Example
from collections import defaultdict
def kosaraju(n, edges):
graph = defaultdict(list)
reverse = defaultdict(list)
for u, v in edges:
graph[u].append(v)
reverse[v].append(u)
visited = [False] * n
order = []
def dfs1(u):
visited[u] = True
for v in graph[u]:
if not visited[v]:
dfs1(v)
order.append(u)
for u in range(n):
if not visited[u]:
dfs1(u)
visited = [False] * n
sccs = []
def dfs2(u, component):
visited[u] = True
component.append(u)
for v in reverse[u]:
if not visited[v]:
dfs2(v, component)
for u in reversed(order):
if not visited[u]:
component = []
dfs2(u, component)
sccs.append(component)
return sccsFollow-up Questions
- How does Tarjan's algorithm find SCCs differently, using only one DFS pass?
- How would you build the condensation DAG from the discovered SCCs?
- Why does processing in decreasing finish order guarantee correctness?
- How would you detect a cycle using SCC results?
MCQ Practice
1. How many DFS passes does Kosaraju's algorithm perform?
It performs one DFS pass on the original graph and one on the transposed graph.
2. What must happen to the graph between the two DFS passes?
The graph is transposed, reversing every edge, before the second DFS pass runs.
3. What is the overall time complexity of Kosaraju's algorithm?
Both DFS passes and the transpose run in linear time relative to vertices and edges, giving O(V + E).
Flash Cards
What does Kosaraju's algorithm compute? — All strongly connected components of a directed graph.
What is done between the two DFS passes? — The graph is transposed (every edge direction reversed).
What order is used for the second DFS pass? — Decreasing finish-time order from the first pass, via a stack.
What is Kosaraju's algorithm's time complexity? — O(V + E), linear in vertices and edges.