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) / 7 / d

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.