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.

A directed graph with black and white edges has a closed walk containing both colours exactly when some strongly connected component has internal edges of both colours. Join the two chosen edges with graph paths inside the strongly connected component. A corresponding claim for a simple cycle is false: differently coloured graph cycles can meet at a single vertex.

A finite directed graph admits an infinite edge-following walk from $s$ exactly when a directed cycle is reachable from $s$. An infinite walk repeats a vertex and therefore contains a reachable cycle; conversely, reach a cycle and repeat it. In a strongly connected component, a cycle exists precisely when the component has at least two vertices or is a singleton with a self-loop. Reachability followed by the two-pass strongly connected component algorithm decides the criterion in $O(|V|+|E|)$ time.

The nonempty set of vertices visited infinitely often by a single infinite walk lies within one strongly connected component. For two such vertices, arbitrarily late visits supply directed walks in both directions. This set need not be the whole component: the walk can keep choosing one cycle and omit other vertices.

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.

Assign each vertex of a finite directed graph a label in a total order. To find the least label reachable from each vertex, first compress its strongly connected components. Give each component its own least label, then process the condensation graph in reverse topological order, replacing each label by the minimum of itself and its successors' labels. Every reachable component is either the current one or reached through a first outgoing edge; induction over this order proves the recurrence. The graph-processing work is $O(|V|+|E|)$ with constant-cost label comparisons. Store a representative vertex as well when a witness is required.

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.