Kosaraju’s Algorithm — Breaking Down the Graph into Strong Pieces

Shreyas Naphad
Jul 10
2 min read

Let’s say you’re looking at a giant network of cities. You want to find groups of cities where each one is reachable from every other in the group — kind of like a tight-knit community.

These are called Strongly Connected Components (SCCs). And Kosaraju’s Algorithm is one of the best ways to find them.

🧠 What's a Strongly Connected Component (SCC)?

In a directed graph, an SCC is a group of nodes where: 👉 For every node u and v in the group, you can go from u → v and from v → u.

🔍 Where Do SCCs Matter?

Deadlock detection in OS
Social networks (friend circles)
Compilers (code dependencies)
Optimizing game logic / AI behavior

🛠️ Kosaraju’s Algorithm in 3 Steps

Kosaraju uses 2 DFS traversals and a graph reversal.

First DFS (Original Graph)
- Do DFS and push nodes onto a stack in the order they finish (post-order).
Transpose the Graph
- Reverse the direction of all edges (called the transpose).
Second DFS (on Transposed Graph)
- Pop nodes from the stack one-by-one.
- For each unvisited node, run DFS again → each DFS call gives you one SCC.

✈️ Analogy

Imagine people sending letters. If everyone in a group can send and receive letters to/from each other → that’s an SCC.

Kosaraju helps you find all such groups.

💡 Interview-Ready Insight

Time Complexity: O(V + E) — because it runs 2 DFS + 1 transpose. Can be used on large graphs efficiently. Common problem types:

“Find the number of strongly connected components.”
“Group nodes that can all reach each other.”

✅ Key Implementation Pointers

Use a stack to store finishing times in first DFS.
Reverse the graph using adjacency list.
Second DFS finds SCCs.
Track visited nodes carefully in both DFS runs.

🧠 Final Thought

Kosaraju is like taking a map, noting who finishes exploring first, flipping the map around, and letting leaders guide the rest. It’s clean, smart, and gets the job done beautifully.