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

Use a global clock starting at zero, incrementing once on discovery and once on finish. Scan starting vertices and each adjacency list in increasing numerical order. The first search descends through $1,2,5,7,4$, returns from $4$, and then visits $6$ from $7$. After that search finishes, the unvisited vertex $3$ starts a second tree.A dash denotes a root with no predecessor. $2\to 6$ is a forward edge: vertex $6$ is a proper descendant of $2$, but its predecessor is $7$. Its interval satisfies $d(2)<d(6)<f(6)<f(2)$. $4\to 1$ is a back edge, because $1$ is still an active ancestor when it is examined. The other non-tree edge $4\to 5$ is also a back edge, while $3\to 6$ reaches an already finished vertex in a different search tree.^[ref]

Use the two-pass strongly connected component algorithm: first run depth-first search on the original directed graph, then search its graph transpose in decreasing order of the first pass's finishing times. The first-pass order from part (a) isReversing the edges gives outgoing adjacency listsThe second pass first visits only $3$. Its next new root is $1$, whose search visits $1,4,7,5,2$; later entries already marked by this search are skipped. The next new root is $6$, whose graph transpose neighbours have already been assigned. Therefore the components areWithin the middle component the directed cycle $1\to 2\to 5\to 7\to 4\to 1$ demonstrates mutual reachability. The source edge structure does not provide return paths from $6$ or to $3$. More generally, decreasing finish order chooses a remaining component whose graph transpose search cannot escape to another still-unassigned component, so each second-pass tree is exactly one component. This explains the partition rather than merely listing it. The algorithm takes $O(|V|+|E|)$ with adjacency lists.^[ref]

Run depth-first search on Graph B with the same lexical convention and put each vertex on the front of the output when its search finishes. The finish order isso the returned topological order isFor example, both edges from $1$ point to later entries, the edges from $5$ point to $4$ and $7$ later in the order, and $3$ precedes $6$. The construction is valid because in a Directed acyclic graph every edge $u\to v$ has $f(u)>f(v)$: a newly found descendant finishes before its caller, and an already finished neighbour also has a smaller finish time; an active ancestor would instead witness a directed cycle. Thus reversing the finish order puts every prerequisite before its successor. The time is $O(|V|+|E|)$.

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.