Strong connectivity
A strongly connected component is a maximal set of vertices where every vertex can reach every other vertex by directed paths. Collapsing SCCs into single nodes always produces a directed acyclic graph.
Graph algorithms / interactive lesson
Kosaraju-Sharir Algorithm
Find strongly connected components with a graph transpose, finishing times, and a second depth-first search in reverse finish order.
University
Guided lesson
Strongly connected components
Kosaraju-Sharir
Step 1 / 50Transposed graph
About the algorithm
Kosaraju-Sharir decomposes a directed graph into strongly connected components using two depth-first searches. The first DFS runs on the transposed graph and records finishing times; the second DFS returns to the original graph and follows vertices in reverse finishing order.
Why the transpose helps
Reversing every edge swaps sources and sinks of the component DAG. Finishing times from the transposed graph give an order that lets the second pass start at a component that will not leak into an unprocessed predecessor in the original graph.
Complexity
The algorithm reverses each edge once and performs two ordinary DFS passes, so the running time is O(V + E) and the extra memory is O(V + E) when the transposed graph is stored explicitly.
Code companion
Connect each visual decision to an implementation pattern.
G_T = transpose(G)
visited = empty set
order = empty stack
for v in G_T.vertices:
if v not visited:
dfs_finish(G_T, v, visited, order)
assigned = empty set
components = []
while order is not empty:
v = order.pop()
if v not assigned:
component = dfs_collect(G, v, assigned)
components.append(component)
return components