Strongly Connected Components (Kosaraju's Algorithm) Solution
Strongly Connected Components (Kosaraju's Algorithm) solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Strongly Connected Components (Kosaraju's Algorithm) is a hard coding problem on depth-first search and graph, asked in Amazon, Microsoft, Adobe and Flipkart interviews.
- Difficulty: Hard
- Topics: Depth-First Search, Graph
- Asked at: Amazon, Microsoft, Adobe, Flipkart
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a directed graph with n vertices numbered 0 to n - 1; each edges[i] = [u, v] is an edge from u to v.
Two vertices belong to the same strongly connected component when each can reach the other along directed edges. Every vertex lies in exactly one component (a vertex alone is a component of size one).
Return the number of strongly connected components.
Example 1
Input: n = 5, edges = [[0,2],[2,1],[1,0],[0,3],[3,4]]
Output: 3
Explanation: The components are {0, 1, 2}, {3} and {4}.
Example 2
Input: n = 3, edges = [[0,1],[1,2],[2,0]]
Output: 1
Explanation: The three edges form one cycle, so every vertex reaches every other.
Example 3
Input: n = 4, edges = [[0,1],[1,2],[2,3]]
Output: 4
Explanation: A path has no way back, so each vertex is its own component.
Constraints
1 <= n <= 50000 <= edges.length <= 10^4edges[i].length == 20 <= u, v < n, u != vthere are no repeated edges
Hints for Strongly Connected Components (Kosaraju's Algorithm)
Hint 1
If you start a DFS inside a "sink" component — one with no edges leaving it — the DFS visits exactly that component.
Hint 2
In a first DFS, record vertices in order of finishing time. The vertex that finishes last lies in a source component of the condensation.
Hint 3
Reverse every edge: sources become sinks. Run DFS on the reversed graph in decreasing finishing time; each new start discovers one whole component.
How to solve Strongly Connected Components (Kosaraju's Algorithm)
Kosaraju's algorithm uses two depth-first searches. The first orders vertices by finishing time; the second, on the transposed graph and in reverse finishing order, peels off one strongly connected component per DFS tree.
Approach
- Build the adjacency list
gand its transposerg(every edge reversed). - DFS over
gfrom every unvisited vertex, appending each vertex toorderwhen it finishes. - Clear the visited marks. Walk
orderfrom last to first; whenever a vertex is unvisited, count a new component and DFS from it overrg, marking everything reached. - Return the count.
Why it works
For two components C and D with an edge from C to D, the latest finishing time in C exceeds every finishing time in D. So the vertex taken first in the second pass belongs to a source component of the condensation — which is a sink in the transpose — and a DFS on rg from it cannot leave its component. Its component is then removed and the argument repeats on what remains.
Complexity
- Time —
O(n + E) - Space —
O(n + E)
Pitfalls
- The second pass must run on the reversed graph; running it on
gmerges components. - Use finishing order, not discovery order.
- Isolated vertices are components too — loop over every vertex, not just those that appear in an edge.
Reference solution
Python
import sys
from typing import List
def kosaraju(n: int, edges: List[List[int]]) -> int:
sys.setrecursionlimit(max(1000, 4 * n + 100))
g = [[] for _ in range(n)]
rg = [[] for _ in range(n)]
for u, v in edges:
g[u].append(v)
rg[v].append(u)
seen = [False] * n
order = []
def dfs1(u):
seen[u] = True
for v in g[u]:
if not seen[v]:
dfs1(v)
order.append(u)
def dfs2(u):
seen[u] = True
for v in rg[u]:
if not seen[v]:
dfs2(v)
for u in range(n):
if not seen[u]:
dfs1(u)
for u in range(n):
seen[u] = False
count = 0
for u in reversed(order):
if not seen[u]:
count += 1
dfs2(u)
return countJava
public static int kosaraju(int n, int[][] edges) {
List<List<Integer>> g = new ArrayList<>(), rg = new ArrayList<>();
for (int i = 0; i < n; i++) { g.add(new ArrayList<>()); rg.add(new ArrayList<>()); }
for (int[] e : edges) { g.get(e[0]).add(e[1]); rg.get(e[1]).add(e[0]); }
boolean[] seen = new boolean[n];
List<Integer> order = new ArrayList<>();
for (int u = 0; u < n; u++) if (!seen[u]) sccFirst(g, u, seen, order);
seen = new boolean[n];
int count = 0;
for (int t = order.size() - 1; t >= 0; t--) {
int u = order.get(t);
if (!seen[u]) { count++; sccSecond(rg, u, seen); }
}
return count;
}
static void sccFirst(List<List<Integer>> g, int u, boolean[] seen, List<Integer> order) {
seen[u] = true;
for (int v : g.get(u)) if (!seen[v]) sccFirst(g, v, seen, order);
order.add(u);
}
static void sccSecond(List<List<Integer>> rg, int u, boolean[] seen) {
seen[u] = true;
for (int v : rg.get(u)) if (!seen[v]) sccSecond(rg, v, seen);
}C++
static void sccFirst(vector<vector<int>>& g, int u, vector<bool>& seen, vector<int>& order) {
seen[u] = true;
for (int v : g[u]) if (!seen[v]) sccFirst(g, v, seen, order);
order.push_back(u);
}
static void sccSecond(vector<vector<int>>& rg, int u, vector<bool>& seen) {
seen[u] = true;
for (int v : rg[u]) if (!seen[v]) sccSecond(rg, v, seen);
}
int kosaraju(int n, vector<vector<int>>& edges) {
vector<vector<int>> g(n), rg(n);
for (auto& e : edges) { g[e[0]].push_back(e[1]); rg[e[1]].push_back(e[0]); }
vector<bool> seen(n, false);
vector<int> order;
for (int u = 0; u < n; u++) if (!seen[u]) sccFirst(g, u, seen, order);
seen.assign(n, false);
int count = 0;
for (int t = (int)order.size() - 1; t >= 0; t--) {
if (!seen[order[t]]) { count++; sccSecond(rg, order[t], seen); }
}
return count;
}JavaScript
var kosaraju = function(n, edges) {
var g = [], rg = [], seen = [], order = [];
for (var i = 0; i < n; i++) { g.push([]); rg.push([]); seen.push(false); }
for (var k = 0; k < edges.length; k++) { g[edges[k][0]].push(edges[k][1]); rg[edges[k][1]].push(edges[k][0]); }
var dfs1 = function(u) {
seen[u] = true;
for (var j = 0; j < g[u].length; j++) if (!seen[g[u][j]]) dfs1(g[u][j]);
order.push(u);
};
var dfs2 = function(u) {
seen[u] = true;
for (var j = 0; j < rg[u].length; j++) if (!seen[rg[u][j]]) dfs2(rg[u][j]);
};
for (var u = 0; u < n; u++) if (!seen[u]) dfs1(u);
for (var x = 0; x < n; x++) seen[x] = false;
var count = 0;
for (var t = order.length - 1; t >= 0; t--) {
if (!seen[order[t]]) { count++; dfs2(order[t]); }
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Graph Data Structure