Strongly connected component

A strongly connected component is a maximal set of vertices in a directed graph such that each can reach every other by a directed path.

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.

Contract each strongly connected component of a directed graph to one vertex, retaining edges between different components. A directed cycle between contracted vertices would make those components mutually reachable, contradicting their distinctness; thus the condensation graph is a Directed acyclic graph. Parallel edges can be retained by algorithms that count them consistently.

A positive-integer labeling with $a⇝b\Rightarrow \ell (a)\le \ell (b)$ and $a/⇝b\Rightarrow \ell (a)>\ell (b)$ exists exactly when the condensation graph is totally ordered by reachability. Mutual paths force equal labels, and equal labels force mutual paths. Two incomparable components would require strict inequalities in both directions. Conversely number the components in topological order; total comparability forces every earlier component to reach every later one, proving both conditions. Compute the labeling in linear time. Reachability here includes length-zero paths.