Strongly Connected Components with Kosaraju
Run DFS on the original graph to get finish-order, transpose the graph, and run DFS again in reverse finish-order to identify SCCs.
Strongly Connected Components with Kosaraju is a free DSA Interview Prep lesson on CoddyKit — lesson 4 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Strongly Connected Components Defined
A Strongly Connected Component (SCC) of a directed graph is a maximal set of nodes such that there is a path from every node to every other node within the set. For example, if nodes A, B, C form a cycle (A→B→C→A), they are all in the same SCC. A single node with no self-loop is its own SCC. SCCs reveal the cyclic structure of a directed graph.
Kosaraju's Algorithm: Two DFS Passes
Kosaraju's algorithm finds all SCCs in O(V + E) using two DFS passes. Pass 1: run DFS on the original graph and push nodes to a stack in finishing order (post-order). Pass 2: run DFS on the transposed (reversed) graph, processing nodes in reverse finishing order (pop from stack). Each DFS tree in pass 2 is one SCC.
Why Kosaraju's Works
In pass 1, the SCC whose DFS tree finishes last is the one with no outgoing edges to other SCCs (a 'sink' SCC in the condensation DAG). In the transposed graph, this SCC has no incoming edges from other SCCs — so DFS from it in pass 2 stays confined within that SCC. Each subsequent DFS in pass 2 stays within its own SCC because all cross-SCC edges were reversed and lead back to already-visited SCCs.
Pass 1: Build Finish Order
Run DFS on the original graph and push each node to a stack after it finishes (post-order). We don't care about components in this pass — just the finish order. The last node to finish will be in a 'source' SCC of the condensation DAG.
from collections import defaultdict
def kosaraju(n, edges):
graph = defaultdict(list)
rev_graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
rev_graph[v].append(u) # reversed edges
visited = set()
finish_stack = []
def dfs1(node):
visited.add(node)
for nxt in graph[node]:
if nxt not in visited:
dfs1(nxt)
finish_stack.append(node) # push after all neighbours done
for i in range(n):
if i not in visited:
dfs1(i)
return finish_stack, rev_graphPass 2: DFS on Transposed Graph
Pop nodes from the finish stack (largest finish time first) and run DFS on the transposed graph. Each DFS from an unvisited node discovers exactly one SCC. Mark all nodes reached in this DFS as belonging to the same component.
from collections import defaultdict
def kosaraju_full(n, edges):
graph = defaultdict(list)
rev_graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
rev_graph[v].append(u)
visited = set()
finish_stack = []
def dfs1(node):
visited.add(node)
for nxt in graph[node]:
if nxt not in visited: dfs1(nxt)
finish_stack.append(node)
for i in range(n):
if i not in visited: dfs1(i)
visited.clear()
sccs = []
def dfs2(node, component):
visited.add(node)
component.append(node)
for nxt in rev_graph[node]:
if nxt not in visited: dfs2(nxt, component)
while finish_stack:
node = finish_stack.pop()
if node not in visited:
component = []
dfs2(node, component)
sccs.append(component)
return sccs
# Graph with SCCs: {0,1,2} and {3}
edges = [(0,1),(1,2),(2,0),(1,3)]
print(kosaraju_full(4, edges)) # [[3], [0,2,1]] or similarTransposing the Graph
The transposed graph reverses every edge: if the original has u → v, the transpose has v → u. Transposing preserves SCCs — if A and B are in the same SCC in the original, they remain in the same SCC in the transpose (since all paths reverse but still connect). Building the transpose during input parsing (as shown above) avoids a separate transposition step.
Iterative Version for Large Graphs
For large graphs, replace recursive DFS with iterative DFS using an explicit stack to avoid Python's recursion limit. The iterative version pushes nodes, processes them, and maintains a separate 'return' marker to simulate post-order.
def dfs1_iterative(start, graph, visited, finish_stack):
stack = [(start, iter(graph[start]))]
visited.add(start)
while stack:
node, neighbours = stack[-1]
try:
nxt = next(neighbours)
if nxt not in visited:
visited.add(nxt)
stack.append((nxt, iter(graph[nxt])))
except StopIteration:
stack.pop()
finish_stack.append(node)
print('Iterative DFS for large graphs avoids recursion limit')Tarjan's Algorithm: Alternative SCC
Tarjan's algorithm finds SCCs in a single DFS pass (compared to Kosaraju's two passes). It maintains a stack of nodes and assigns each node a discovery time and low-link value. When a node's discovery time equals its low-link, it is the root of an SCC. Tarjan's is slightly more complex to implement but avoids building the transpose graph. Both are O(V + E).
Applications of SCCs
SCCs are used in: (1) Compiler optimisation — identifying mutually recursive functions. (2) Social network analysis — finding tightly-knit communities. (3) 2-SAT problem — determining satisfiability of 2-literal clauses. (4) Web crawling — identifying clusters of pages with dense cross-links. (5) Condensation DAG — after finding SCCs, the condensation of the graph is a DAG, enabling topological analysis of cyclic graphs.
Condensation DAG
The condensation of a directed graph contracts each SCC into a single node and adds an edge between two super-nodes if there is an edge between their constituent SCCs. The result is always a DAG — you can run topological sort on it. This enables algorithms that only work on DAGs (like DP) to be applied to general directed graphs by working on their condensation.
def build_condensation(n, edges, sccs):
# Assign each node to its SCC index
scc_id = [0] * n
for idx, component in enumerate(sccs):
for node in component:
scc_id[node] = idx
# Build condensation edges
condensation_edges = set()
for u, v in edges:
su, sv = scc_id[u], scc_id[v]
if su != sv:
condensation_edges.add((su, sv))
return list(condensation_edges)
edges = [(0,1),(1,2),(2,0),(1,3)]
sccs = [[3],[0,1,2]]
print(build_condensation(4, edges, sccs)) # [(0,1)] or [(1,0)]Number of SCCs and Graph Properties
The number of SCCs in a directed graph reveals its cyclic structure. A DAG has n SCCs (each node is its own SCC). A strongly connected graph has exactly 1 SCC. In general, the SCCs form a DAG when condensed — the condensation. If the condensation DAG has a unique source (node with in-degree 0) and a unique sink (node with out-degree 0) in the condensation, certain connectivity properties hold. These properties are tested in problems about reachability after adding minimal edges.
Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: SCCs are maximal sets where every node is reachable from every other, Kosaraju's uses two DFS passes — first on original graph for finish order, then on transposed graph, and the condensation of any directed graph is a DAG usable for further analysis. Next up we build TrieNode data structures for insert, search, and prefix operations.
Frequently asked questions
Is the “Strongly Connected Components with Kosaraju” lesson free?
Yes — the full text of “Strongly Connected Components with Kosaraju” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Strongly Connected Components with Kosaraju”?
Run DFS on the original graph to get finish-order, transpose the graph, and run DFS again in reverse finish-order to identify SCCs. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 4 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Strongly Connected Components with Kosaraju” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Kahn's Algorithm: BFS Topological Sort
- DFS Post-Order Topological Sort
- Course Schedule I and II
- Strongly Connected Components with Kosaraju