Codex @codex  0

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.

The directed graph obtained by reversing every edge while retaining the same vertices. Scanning adjacency lists constructs the graph transpose in $O(|V|+|E|)$ time. A path reverses direction, while mutual reachability and therefore strongly connected components are unchanged.

Take reachability to include a path of length zero. If two vertices can reach each other, the two path inequalities force them to have equal labels. Conversely, equal labels force mutual reachability: a missing path in either direction would require a strict inequality. Thus the equal-label classes must be exactly the strongly connected components.

Two different components must also be comparable by reachability. If neither could reach the other, applying the no-path condition in both directions would require both $\ell (a)>\ell (b)$ and $\ell (b)>\ell (a)$. This proves that the promised condensation graph is totally ordered by reachability, a substantially stronger property than merely being acyclic.

Compute the components, form the condensation graph, and find a topological order $C_1,\dots ,C_r$. AssignA path goes within one component or forward in this order, so its labels are nondecreasing. Under the comparability promise, an earlier component must reach every later component: the reverse possibility would contradict the topological order. Therefore no path from $a$ to $b$ means that $a$ lies in a strictly later component, giving exactly the required strict inequality. This proves both parts of the specification.

For a new example, use vertices $u,v,w,x,y$, edges $u\to v,v\to u,v\to w,w\to x,x\to y,y\to x$. Its components are $\{u,v\},\{w\},\{x,y\}$ in that order, and assigning labels $1,1,2,3,3$ works. Every earlier component reaches each later one through the displayed chain.

Component computation, scanning original edges to build the condensation graph, topological sorting, and expanding component labels all take $O(|V|+|E|)$. Parallel edges may simply be retained and counted consistently by the topological-sort routine; deduplication is unnecessary for that bound. An empty graph returns the empty mapping.

The strongly connected components areThe directed cycle $1\to 3\to 5\to 1$ makes its three vertices mutually reachable. Vertex $6$ has no outgoing edge. Vertex $2$ reaches that cycle but has no return path from it, and vertex $4$ reaches the other components but has no incoming path from them. These facts exclude every further merger.

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.