= Two-pass strongly connected component algorithm
{title2=$O(|V|+|E|)$}
Run <depth-first search> on a finite <directed graph>, then search its <graph transpose> in decreasing first-pass finish order, marking <vertices> permanently during the second pass. Each second-pass search tree is one <strongly connected component>. The component finish-order property ensures that the next search cannot enter another still-unassigned component in the <graph transpose>; mutual reachability ensures that it reaches every <vertex> in its own component. Two traversals and transposition take $O(|V|+|E|)$ time.
Back to article page
