Skip to main content

Strongly Connected Components - Kosaraju

Learn Strongly Connected Components - Kosaraju (Graphs, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

Strongly Connected Components with Kosaraju In a directed graph, a strongly connected component (SCC) is a maximal group of vertices where every vertex can reach every other. Kosaraju's algorithm finds them with two DFS passes: (1) DFS on the graph and push vertices on a stack in order of finishing time ; (2) build the transpose graph (all edges reversed) and run DFS from the stack's top vertices. Each DFS tree of the second pass is one SCC. Cost: O(V + E) .

More lessons in Graphs