Strongly connected components

O(V + E)

In a directed graph, a strongly connected component is a maximal set of vertices where every vertex can reach every other by following edges. Kosaraju's algorithm finds them all in two passes. First it runs DFS over the whole graph, pushing each vertex onto a stack the moment it finishes (so the last-to-finish ends up on top). Then it reverses every edge and runs DFS again, this time taking start vertices off the stack in that order — each tree the second DFS grows is exactly one SCC. Reversing the edges is the clever part: it confines the second search to a single component. It runs in O(V + E). SCCs reveal cyclic dependencies, condense a graph into a DAG of components, and underlie 2-SAT. Each component is shown in its own colour.

Directed graph
Edit the input and press Play

How it works

  1. Pass 1: DFS the graph, recording each vertex when it finishes.
  2. Reverse every edge (transpose the graph).
  3. Pass 2: DFS the transpose, taking vertices in reverse finish order.
  4. Each tree the second pass grows is one strongly connected component.

Pseudocode

1kosaraju(graph):                    # O(V + E)2  pass 1: DFS the graph, pushing each3          vertex onto a stack when it finishes4  transpose the graph (reverse every edge)5  pass 2: pop vertices in that order; each6          DFS on the transpose marks one SCC7  vertices coloured alike form a component