= Solution
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,\ldots,C_r$. Assign
$$
\boxed{\ell(v)=i\quad\text{for }v\in C_i.}
$$
A 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.
\Image[/past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2021/functional-programming-design-and-analysis-of-algorithms-resit-reachability-layering.png]
{title=An original example whose strongly connected components are ordered by reachability}
{description=This five-vertex example is separate from the examination's two source graphs. Internal cycles receive equal labels; the component chain forces strictly increasing labels between components.}
Component computation, scanning original <edges> to build the <condensation graph>, <topological sorting>, and expanding component labels all take \b[$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.
Back to article page
