Kosaraju's Algorithm (Strongly Connected Components)
Description
In a directed graph, a Strongly Connected Component (SCC) is a maximal subset of vertices where every vertex is reachable from every other vertex in the same subset by following directed edges.
Given a directed graph represented as an adjacency list adj, where adj[i] contains the list of vertices that vertex i has a directed edge to, find the number of strongly connected components in the graph.
A single vertex with no self-loop and no cycle through other vertices still forms its own SCC of size 1. If the entire graph is one big cycle, then all vertices belong to a single SCC.
Examples
Example 1
Input: adj = [[2, 3], [0], [1], [4], []]
Output: 3
Explanation: The graph has 5 vertices (0 through 4). Vertices 0, 1, and 2 form a cycle: 0→2→1→0, so every vertex can reach every other within this group — they form one SCC {0, 1, 2}. Vertex 3 has an incoming edge from 0 and an outgoing edge to 4, but no path leads back from 3 to 0, so vertex 3 is its own SCC {3}. Vertex 4 has no outgoing edges at all, making it a singleton SCC {4}. Total: 3 SCCs.
Example 2
Input: adj = [[1], [2], [0]]
Output: 1
Explanation: The graph has 3 vertices forming a single cycle: 0→1→2→0. Every vertex can reach every other vertex by following directed edges around the cycle. All vertices belong to one SCC {0, 1, 2}.
Example 3
Input: adj = [[1], []]
Output: 2
Explanation: Vertex 0 has a directed edge to vertex 1, but vertex 1 has no outgoing edges. There is no path from 1 back to 0. Since mutual reachability is required for two vertices to share an SCC, each vertex forms its own SCC: {0} and {1}. Total: 2 SCCs.
Constraints
- 2 ≤ V (number of vertices, adj.size()) ≤ 10^5
- 0 ≤ adj[i][j] ≤ V - 1 (all vertex indices are valid and 0-based)
- The graph is directed
- Self-loops and multiple edges between the same pair of vertices are possible
Editorial
Brute Force
Intuition
The most natural way to find strongly connected components is to directly apply the definition: two vertices belong to the same SCC if and only if there is a directed path from the first to the second AND a directed path from the second back to the first.
Imagine you are organizing people into friend groups where the rule is: two people are in the same group only if person A can send a message chain to person B AND person B can send a message chain back to person A. To figure out the groups, you would test every pair of people individually — can A reach B, and can B reach A?
For the graph, we pick each unassigned vertex, then check every other unassigned vertex to see if the two are mutually reachable (via DFS or BFS in both directions). All vertices that are mutually reachable with the starting vertex form one SCC.
Step-by-Step Explanation
Let's trace through with adj = [[2, 3], [0], [1], [4], []] (5 vertices, edges: 0→2, 0→3, 1→0, 2→1, 3→4):
Step 1: Start with vertex 0 (unassigned). We need to find all vertices mutually reachable with 0.
Step 2: Check pair (0, 1). DFS from 0: follow 0→2→1, reaches vertex 1. Path from 0 to 1 exists.
Step 3: Reverse check: DFS from 1: follow 1→0, reaches vertex 0 directly. Path from 1 to 0 exists. Both directions confirmed — vertices 0 and 1 are in the same SCC.
Step 4: Check pair (0, 2). DFS from 0: follow 0→2, reaches vertex 2 directly. DFS from 2: follow 2→1→0, reaches vertex 0. Both directions work — vertex 2 joins the SCC {0, 1, 2}.
Step 5: Check pair (0, 3). DFS from 0: follow 0→3, reaches vertex 3. Forward path exists.
Step 6: Reverse check: DFS from 3: follow 3→4, then vertex 4 has no outgoing edges — dead end. No path from 3 back to 0. Vertices 0 and 3 are NOT in the same SCC.
Step 7: Check pair (0, 4). DFS from 0: 0→3→4, reaches 4. DFS from 4: no outgoing edges at all. No path back. NOT in same SCC.
Step 8: SCC #1 complete: {0, 1, 2}. Move to next unassigned vertex: 3. Check pair (3, 4): DFS from 3→4 exists, but DFS from 4 has no outgoing edges. Not mutually reachable. Vertex 3 forms singleton SCC #2.
Step 9: Vertex 4 is the last unassigned vertex. It forms singleton SCC #3: {4}.
Result: 3 strongly connected components.
Brute Force — Pairwise Reachability Check — Watch how we test every pair of vertices for mutual reachability using DFS in both directions to identify strongly connected components.
Algorithm
- Maintain a boolean array
assigned[]to track which vertices have been placed into an SCC - For each unassigned vertex
i:
a. Markias assigned and start a new SCC containingi
b. For each other unassigned vertexj:- Run DFS from
ito check ifjis reachable - Run DFS from
jto check ifiis reachable - If both paths exist, add
jto the current SCC and markjas assigned
c. Increment the SCC count
- Run DFS from
- Return the total SCC count
Code
#include <vector>
using namespace std;
class Solution {
public:
bool dfs(int curr, int dest, vector<vector<int>>& adj,
vector<bool>& visited) {
if (curr == dest) return true;
visited[curr] = true;
for (int next : adj[curr]) {
if (!visited[next] && dfs(next, dest, adj, visited))
return true;
}
return false;
}
bool isReachable(int src, int dest, vector<vector<int>>& adj) {
vector<bool> visited(adj.size(), false);
return dfs(src, dest, adj, visited);
}
int kosaraju(vector<vector<int>>& adj) {
int V = adj.size();
vector<bool> assigned(V, false);
int count = 0;
for (int i = 0; i < V; i++) {
if (!assigned[i]) {
assigned[i] = true;
for (int j = i + 1; j < V; j++) {
if (!assigned[j]
&& isReachable(i, j, adj)
&& isReachable(j, i, adj)) {
assigned[j] = true;
}
}
count++;
}
}
return count;
}
};class Solution:
def kosaraju(self, adj):
V = len(adj)
assigned = [False] * V
count = 0
def dfs(curr, dest, visited):
if curr == dest:
return True
visited[curr] = True
for nxt in adj[curr]:
if not visited[nxt] and dfs(nxt, dest, visited):
return True
return False
def is_reachable(src, dest):
visited = [False] * V
return dfs(src, dest, visited)
for i in range(V):
if not assigned[i]:
assigned[i] = True
for j in range(i + 1, V):
if (not assigned[j]
and is_reachable(i, j)
and is_reachable(j, i)):
assigned[j] = True
count += 1
return countimport java.util.ArrayList;
class Solution {
boolean dfs(int curr, int dest,
ArrayList<ArrayList<Integer>> adj,
boolean[] visited) {
if (curr == dest) return true;
visited[curr] = true;
for (int next : adj.get(curr)) {
if (!visited[next]
&& dfs(next, dest, adj, visited))
return true;
}
return false;
}
boolean isReachable(int src, int dest,
ArrayList<ArrayList<Integer>> adj) {
boolean[] visited = new boolean[adj.size()];
return dfs(src, dest, adj, visited);
}
public int kosaraju(ArrayList<ArrayList<Integer>> adj) {
int V = adj.size();
boolean[] assigned = new boolean[V];
int count = 0;
for (int i = 0; i < V; i++) {
if (!assigned[i]) {
assigned[i] = true;
for (int j = i + 1; j < V; j++) {
if (!assigned[j]
&& isReachable(i, j, adj)
&& isReachable(j, i, adj)) {
assigned[j] = true;
}
}
count++;
}
}
return count;
}
}Complexity Analysis
Time Complexity: O(V² × (V + E))
For each of the V vertices, we potentially check against every other vertex — up to O(V²) pairs total. Each check requires two DFS traversals (forward and reverse), each costing O(V + E). This gives O(V²) pair checks × O(V + E) per check = O(V² × (V + E)).
Space Complexity: O(V)
We use a visited array of size V for each DFS call, plus the assigned array of size V. The DFS recursion stack can also go up to O(V) deep. Total auxiliary space is O(V).
Why This Approach Is Not Efficient
The brute force approach runs in O(V² × (V + E)) time. With V up to 10^5 vertices, even the V² term alone gives 10^10 operations — far beyond what any computer can handle within typical time limits (usually around 10^8 operations per second).
The fundamental problem is redundant work: we are running a separate DFS for every single pair of vertices, even though many of these DFS traversals explore the exact same portions of the graph repeatedly. If vertex A can reach vertex B and vertex B can reach vertex C, then clearly A, B, and C are all in the same SCC — but the brute force doesn't exploit this transitivity. It checks (A,B), then (A,C), then (B,C) all independently.
Key insight: Instead of checking pairs individually, we can use DFS finish times to impose an ordering on vertices that naturally groups SCCs together. The vertex that finishes last in DFS belongs to a "root" SCC. By running DFS on the transposed graph (all edges reversed) in reverse finish-time order, each DFS tree in the transposed graph corresponds exactly to one SCC. This eliminates all redundant work and brings the total cost down to O(V + E) — just two linear DFS passes.
Optimal Approach - Kosaraju's Algorithm
Intuition
Kosaraju's algorithm is a clever two-pass DFS technique that finds all SCCs in linear time. The idea rests on two key observations:
Observation 1 — Finish Time Ordering: When you run DFS on a directed graph and record the order in which vertices finish (i.e., when all their descendants have been fully explored), vertices in "source" SCCs (those with no incoming cross-SCC edges) tend to finish later than vertices in "sink" SCCs. Specifically, the SCC whose vertex finishes last has no incoming edges from other SCCs in the condensation graph.
Observation 2 — Transposing Reverses Cross-SCC Flow: If you reverse all edges in the graph (creating the "transpose" graph), the SCCs stay exactly the same (because if A→B→A is a cycle, then reversing gives A←B←A, still a cycle). However, the cross-SCC edges now flow in the opposite direction. A "source" SCC in the original becomes a "sink" in the transpose.
Combining Both: Process vertices in decreasing order of finish time on the transpose graph. The vertex with the highest finish time belongs to a source SCC in the original graph, which is now a sink in the transpose — meaning DFS from it in the transpose will visit exactly the vertices of that SCC and nothing else. Remove those vertices and repeat.
Think of it like peeling an onion: the first pass orders the layers, and the second pass peels them one at a time from the outermost inward.
Step-by-Step Explanation
Let's trace Kosaraju's algorithm on adj = [[2, 3], [0], [1], [4], []] (edges: 0→2, 0→3, 1→0, 2→1, 3→4):
Phase 1: DFS on Original Graph — Record Finish Order
Step 1: Start DFS from vertex 0. Mark 0 as visited.
Step 2: From 0, visit first neighbor 2. Mark 2 visited. From 2, visit neighbor 1. Mark 1 visited.
Step 3: Vertex 1's only neighbor is 0, which is already visited. Vertex 1 finishes — push 1 to stack.
Step 4: Back at vertex 2. No unvisited neighbors remain. Vertex 2 finishes — push 2 to stack.
Step 5: Back at vertex 0. Visit next unvisited neighbor: 3. Mark 3 visited. From 3, visit neighbor 4. Mark 4 visited.
Step 6: Vertex 4 has no outgoing edges. Vertex 4 finishes — push 4 to stack.
Step 7: Back at vertex 3. No unvisited neighbors. Vertex 3 finishes — push 3 to stack.
Step 8: Back at vertex 0. All neighbors explored. Vertex 0 finishes (last!) — push 0 to stack. Stack (top→bottom): [0, 3, 4, 2, 1].
Phase 2: Transpose the Graph
Step 9: Reverse all edges: 0→2 becomes 2→0, 0→3 becomes 3→0, 1→0 becomes 0→1, 2→1 becomes 1→2, 3→4 becomes 4→3.
Phase 3: DFS on Transposed Graph in Reverse Finish Order
Step 10: Pop vertex 0 from stack. DFS from 0 on transposed graph: 0→1 (reversed 1→0), then 1→2 (reversed 2→1), then 2→0 (reversed 0→2, already visited). Visited {0, 1, 2} — SCC #1.
Step 11: Pop vertex 3. DFS from 3 on transposed graph: only edge 3→0 (reversed 0→3), but 0 is already visited. Only vertex 3 collected — SCC #2.
Step 12: Pop vertex 4. DFS from 4 on transposed graph: edge 4→3 (reversed 3→4), but 3 already visited. Only vertex 4 — SCC #3.
Result: 3 strongly connected components: {0,1,2}, {3}, {4}.
Kosaraju's Algorithm — Two DFS Passes with Transpose — Watch the three phases of Kosaraju's algorithm: DFS to record finish order, graph transposition, then DFS in reverse finish order to extract each SCC.
Algorithm
-
Pass 1 — Record Finish Order:
- Initialize a visited array and an empty stack
- For each unvisited vertex, run DFS on the original graph
- When DFS finishes exploring a vertex (all descendants done), push that vertex onto the stack
-
Transpose the Graph:
- Create a new adjacency list where every edge (u → v) becomes (v → u)
-
Pass 2 — Extract SCCs:
- Reset the visited array
- While the stack is not empty:
- Pop the top vertex
- If it is unvisited, run DFS from it on the transposed graph
- All vertices reached in this DFS form one SCC — increment the SCC count
-
Return the total SCC count
Code
#include <vector>
#include <stack>
using namespace std;
class Solution {
public:
void dfs1(int u, vector<vector<int>>& adj,
vector<bool>& visited, stack<int>& st) {
visited[u] = true;
for (int v : adj[u]) {
if (!visited[v])
dfs1(v, adj, visited, st);
}
st.push(u);
}
void dfs2(int u, vector<vector<int>>& transpose,
vector<bool>& visited) {
visited[u] = true;
for (int v : transpose[u]) {
if (!visited[v])
dfs2(v, transpose, visited);
}
}
int kosaraju(vector<vector<int>>& adj) {
int V = adj.size();
vector<bool> visited(V, false);
stack<int> st;
// Pass 1: fill stack with finish order
for (int i = 0; i < V; i++) {
if (!visited[i])
dfs1(i, adj, visited, st);
}
// Build transposed graph
vector<vector<int>> transpose(V);
for (int u = 0; u < V; u++) {
for (int v : adj[u])
transpose[v].push_back(u);
}
// Pass 2: process in reverse finish order
fill(visited.begin(), visited.end(), false);
int count = 0;
while (!st.empty()) {
int node = st.top();
st.pop();
if (!visited[node]) {
dfs2(node, transpose, visited);
count++;
}
}
return count;
}
};import sys
sys.setrecursionlimit(200000)
class Solution:
def kosaraju(self, adj):
V = len(adj)
visited = [False] * V
stack = []
# Pass 1: DFS on original graph, record finish order
def dfs1(u):
visited[u] = True
for v in adj[u]:
if not visited[v]:
dfs1(v)
stack.append(u)
for i in range(V):
if not visited[i]:
dfs1(i)
# Build transposed graph
transpose = [[] for _ in range(V)]
for u in range(V):
for v in adj[u]:
transpose[v].append(u)
# Pass 2: DFS on transposed graph in reverse finish order
visited = [False] * V
count = 0
def dfs2(u):
visited[u] = True
for v in transpose[u]:
if not visited[v]:
dfs2(v)
while stack:
node = stack.pop()
if not visited[node]:
dfs2(node)
count += 1
return countimport java.util.ArrayList;
import java.util.Stack;
class Solution {
void dfs1(int u, ArrayList<ArrayList<Integer>> adj,
boolean[] visited, Stack<Integer> st) {
visited[u] = true;
for (int v : adj.get(u)) {
if (!visited[v])
dfs1(v, adj, visited, st);
}
st.push(u);
}
void dfs2(int u, ArrayList<ArrayList<Integer>> transpose,
boolean[] visited) {
visited[u] = true;
for (int v : transpose.get(u)) {
if (!visited[v])
dfs2(v, transpose, visited);
}
}
public int kosaraju(ArrayList<ArrayList<Integer>> adj) {
int V = adj.size();
boolean[] visited = new boolean[V];
Stack<Integer> st = new Stack<>();
// Pass 1: fill stack with finish order
for (int i = 0; i < V; i++) {
if (!visited[i])
dfs1(i, adj, visited, st);
}
// Build transposed graph
ArrayList<ArrayList<Integer>> transpose = new ArrayList<>();
for (int i = 0; i < V; i++)
transpose.add(new ArrayList<>());
for (int u = 0; u < V; u++) {
for (int v : adj.get(u))
transpose.get(v).add(u);
}
// Pass 2: process in reverse finish order
java.util.Arrays.fill(visited, false);
int count = 0;
while (!st.isEmpty()) {
int node = st.pop();
if (!visited[node]) {
dfs2(node, transpose, visited);
count++;
}
}
return count;
}
}Complexity Analysis
Time Complexity: O(V + E)
The algorithm performs exactly two full DFS traversals of the graph (one on the original, one on the transpose). Each DFS visits every vertex once and traverses every edge once, costing O(V + E) per pass. Building the transposed graph requires iterating over all edges once — also O(V + E). Total: O(V + E) + O(V + E) + O(V + E) = O(V + E).
Space Complexity: O(V + E)
We store the transposed graph as a separate adjacency list, which takes O(V + E) space. Additionally, we use a visited array of size V, a stack holding up to V vertices, and the DFS recursion stack of depth up to V. The dominant term is the transposed graph storage: O(V + E).