Log inSign up
hardGeeksforGeeksNot Started

Kosaraju Algorithm

Given a directed graph with V vertices and E edges represented as an adjacency list adj, count or output all Strongly Connected Components (SCCs) using Kosaraju's 2-Pass DFS Algorithm.

Graph
Solve on GeeksforGeeks
Lesson

Problem Statement

### Problem Statement

Given a directed graph with V vertices numbered 0 to V - 1 and an adjacency list adj.

A Strongly Connected Component (SCC) is a maximal subgraph where every vertex is reachable from every other vertex within that subgraph.

Compute and return the total number of Strongly Connected Components (SCCs) in the graph using Kosaraju's Algorithm.

---

### Examples

Example 1: ``text Input: V = 5, adj = [[2, 3], [0], [1], [4], []] Output: 3 Explanation: - Component 1: {0, 1, 2} (cycle 0 -> 2 -> 1 -> 0) - Component 2: {3} - Component 3: {4} Total SCCs = 3.

Example 2: ``text Input: V = 4, adj = [[1], [2], [3], []] Output: 4 Explanation: The graph is a directed line 0 -> 1 -> 2 -> 3 with no cycles. Each individual vertex forms its own SCC. Total = 4.

---

### Constraints - 1 <= V <= 10^5 - 0 <= adj[i].length <= V - Directed graph without self-loops.

Constraints:

  • 1 <= V <= 105
  • 0 <= E <= 2 * 105
  • 0-indexed directed graph

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Explain why the condensation of SCCs forms a Directed Acyclic Graph (DAG).
  • Master the 3-step sequence: Finish-time stack -> Graph Transposition -> Transpose DFS.
  • Understand why reversing edges traps DFS inside the target component.
  • Implement Kosaraju's algorithm across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Finding groups of mutually reachable entities in directed networks.
  • Solving 2-SAT boolean satisfiability (variable x and ¬x must not belong to same SCC).
  • Condensing large directed graphs into DAGs for dependency resolution.

Algorithmic Decision Tree:

  • If undirected graph connectivity -> Simple BFS/DFS or DSU in O(V + E).
  • If directed graph mutual reachability -> Kosaraju's (2 DFS passes) or Tarjan's (1 DFS pass) in O(V + E).

Connected Patterns:

Tarjan's SCC AlgorithmTopological SortCritical Connections in a Network

1. All-Pairs Reachability Intersection

Intuition

For every pair of vertices (u, v), run BFS to check if u can reach v and v can reach u. Group mutually reachable nodes into SCCs.

Algorithm

  1. Compute boolean reachability matrix reachable[u][v] by running BFS from each vertex u.
  2. Maintain a visited set of grouped vertices.
  3. For each unvisited vertex u:
  4. Collect all unvisited vertices v where reachable[u][v] && reachable[v][u].
  5. Mark all collected vertices as visited and increment SCC count.
  6. Return SCC count.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4
5using namespace std;
6
7void bfs(int src, const vector<vector<int>>& adj, vector<bool>& reachable) {
8 queue<int> q;
9 q.push(src);
10 reachable[src] = true;
11
12 while (!q.empty()) {
13 int u = q.front();
14 q.pop();
15 for (int v : adj[u]) {
16 if (!reachable[v]) {
17 reachable[v] = true;
18 q.push(v);
19 }
20 }
21 }
22}
23
24int countSCCsBruteForce(int V, const vector<vector<int>>& adj) {
25 vector<vector<bool>> reachable(V, vector<bool>(V, false));
26 for (int i = 0; i < V; ++i) {
27 bfs(i, adj, reachable[i]);
28 }
29
30 vector<bool> visited(V, false);
31 int sccCount = 0;
32
33 for (int i = 0; i < V; ++i) {
34 if (!visited[i]) {
35 sccCount++;
36 for (int j = 0; j < V; ++j) {
37 if (reachable[i][j] && reachable[j][i]) {
38 visited[j] = true;
39 }
40 }
41 }
42 }
43 return sccCount;
44}
45
46int main() {
47 int V = 5;
48 vector<vector<int>> adj = {{2, 3}, {0}, {1}, {4}, {}};
49 cout << "SCC Count (Brute Force): " << countSCCsBruteForce(V, adj) << endl;
50 return 0;
51}

Time & Space Complexity

  • Time complexity: O(V * (V + E))
  • Space complexity: O(V^2)

2. Tarjan's 1-Pass Low-Link SCC Algorithm

Intuition

Single DFS traversal maintaining discovery time tin and lowest reachable ancestor low, using an explicit stack to peel off SCCs when low[u] == tin[u].

Algorithm

  1. Maintain discovery time tin, low, and boolean array onStack.
  2. In dfs(u):
  3. tin[u] = low[u] = ++timer, push u to stack, onStack[u] = true.
  4. For neighbor v of u:
  5. If v unvisited: dfs(v), low[u] = min(low[u], low[v]).
  6. Else if onStack[v]: low[u] = min(low[u], tin[v]).
  7. If low[u] == tin[u]:
  8. Pop nodes from stack until u is popped; increment SCC count.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <stack>
4#include <algorithm>
5
6using namespace std;
7
8class TarjanSCC {
9 int V, timer = 0, sccCount = 0;
10 vector<int> tin, low;
11 vector<bool> onStack;
12 stack<int> st;
13
14 void dfs(int u, const vector<vector<int>>& adj) {
15 tin[u] = low[u] = ++timer;
16 st.push(u);
17 onStack[u] = true;
18
19 for (int v : adj[u]) {
20 if (tin[v] == -1) {
21 dfs(v, adj);
22 low[u] = min(low[u], low[v]);
23 } else if (onStack[v]) {
24 low[u] = min(low[u], tin[v]);
25 }
26 }
27
28 if (low[u] == tin[u]) {
29 sccCount++;
30 while (true) {
31 int node = st.top();
32 st.pop();
33 onStack[node] = false;
34 if (node == u) break;
35 }
36 }
37 }
38
39public:
40 int countSCCs(int v, const vector<vector<int>>& adj) {
41 V = v;
42 tin.assign(V, -1);
43 low.assign(V, -1);
44 onStack.assign(V, false);
45 timer = 0;
46 sccCount = 0;
47
48 for (int i = 0; i < V; ++i) {
49 if (tin[i] == -1) dfs(i, adj);
50 }
51 return sccCount;
52 }
53};
54
55int main() {
56 int V = 5;
57 vector<vector<int>> adj = {{2, 3}, {0}, {1}, {4}, {}};
58 TarjanSCC solver;
59 cout << "Tarjan SCC Count: " << solver.countSCCs(V, adj) << endl;
60 return 0;
61}

Time & Space Complexity

  • Time complexity: O(V + E)
  • Space complexity: O(V)

3. Kosaraju's 2-Pass DFS Algorithm

Intuition

Step 1: Order vertices by finishing time using DFS on G. Step 2: Transpose all edges to get GT. Step 3: Pop from stack and run DFS on GT to peel off each SCC.

Algorithm

  1. Step 1 (Order by finish time): Run DFS on original graph G. When returning from u, push u onto a stack.
  2. Step 2 (Transpose graph): Construct adjT where for every directed edge u -> v in G, add v -> u in adjT.
  3. Step 3 (SCC Traversal): Reset visited array. While stack is not empty:
  4. Pop u from stack.
  5. If !visited[u]:
  6. Run DFS on adjT starting from u.
  7. Increment sccCount by 1.
  8. Return sccCount.

Kosaraju's 2-Pass Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Pass 1: DFS pushes to stack on finish
Visual state
Values and pointers at this exact step
table
This state table trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Check / comparison
Finished Pass 1
Decision / next transition
Transpose graph
Why this step matters

Pass 1: DFS pushes to stack on finish. Stack top-to-bottom: [0, 1, 2, 3, 4].

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <stack>
4
5using namespace std;
6
7class Kosaraju {
8 void dfs1(int u, const vector<vector<int>>& adj, vector<bool>& visited, stack<int>& st) {
9 visited[u] = true;
10 for (int v : adj[u]) {
11 if (!visited[v]) dfs1(v, adj, visited, st);
12 }
13 st.push(u); // Finish time push
14 }
15
16 void dfs2(int u, const vector<vector<int>>& adjT, vector<bool>& visited) {
17 visited[u] = true;
18 for (int v : adjT[u]) {
19 if (!visited[v]) dfs2(v, adjT, visited);
20 }
21 }
22
23public:
24 int kosaraju(int V, const vector<vector<int>>& adj) {
25 stack<int> st;
26 vector<bool> visited(V, false);
27
28 // Step 1: Order by finishing time
29 for (int i = 0; i < V; ++i) {
30 if (!visited[i]) dfs1(i, adj, visited, st);
31 }
32
33 // Step 2: Transpose the graph
34 vector<vector<int>> adjT(V);
35 for (int u = 0; u < V; ++u) {
36 for (int v : adj[u]) {
37 adjT[v].push_back(u);
38 }
39 }
40
41 // Step 3: DFS on transpose graph in stack order
42 fill(visited.begin(), visited.end(), false);
43 int sccCount = 0;
44
45 while (!st.empty()) {
46 int u = st.top();
47 st.pop();
48
49 if (!visited[u]) {
50 sccCount++;
51 dfs2(u, adjT, visited);
52 }
53 }
54
55 return sccCount;
56 }
57};
58
59int main() {
60 int V = 5;
61 vector<vector<int>> adj = {{2, 3}, {0}, {1}, {4}, {}};
62 Kosaraju solver;
63 cout << "Optimal Kosaraju SCC Count: " << solver.kosaraju(V, adj) << endl;
64 return 0;
65}

Time & Space Complexity

  • Time complexity: O(V + E)
  • Space complexity: O(V + E)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.All-Pairs Reachability Matrix (Floyd-Warshall / BFS)O(V * (V + E)) or O(V^3)O(V^2)Run BFS from every vertex u. Two vertices u and v are in the same SCC if u reaches v and v reaches u.Full V-source traversals.
2.Tarjan's 1-Pass SCC AlgorithmO(V + E)O(V)Single DFS traversal using low-link values and explicit stack.Tricky edge cases on cross-edges.
3.Kosaraju's 2-Pass DFS Algorithm (Optimal & Standard)OptimalO(V + E)O(V + E)Order by finish times, transpose graph, and DFS to collect SCCs.Standard linear graph traversal.

Common Pitfalls & Crucial Edge Cases

Reversing edges in the wrong direction

Failing to ensure GT has edge v -> u whenever G has u -> v.

Forgetting to reset the visited array between Pass 1 and Pass 2

Causes Pass 2 to immediately terminate without visiting anything.

Pushing to stack on entry rather than exit

Pushing on entry gives discovery order instead of finishing order.

Crucial Edge Cases to Validate:

  • DAG with no cycles — Every single vertex is its own SCC; returns V.
  • Single strongly connected cycle (0 -> 1 -> 2 -> 0) — Entire graph is 1 SCC; returns 1.
  • Disconnected components — Handled naturally by outer loop over 0 to V - 1.
  • Self-loops — Valid 1-vertex SCC.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Summarize the 3 steps in 15 seconds: (1) DFS finish-time stack, (2) Transpose edges, (3) DFS in stack order on transpose.
  2. Mention that the condensation graph of SCCs is always a DAG.
  3. Contrast with Tarjan's algorithm (which does it in 1 pass but is harder to write bug-free).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does reversing all edges in the graph (forming the transpose graph GT) isolate strongly connected components during Pass 2?

2.What does the stack in Kosaraju's algorithm store after Pass 1?

Back to DSA Sheet