Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Functional programming, design and analysis of algorithms / 7

The source explicitly labels this question “Corrected”; that label does not imply that the four assertions in part (b) are true.

In depth-first search, mark every vertex white initially. At a white start vertex $u$, increment a global clock, record $d[u]$ and color it gray. Scan its outgoing adjacency list; recursively visit each still-white neighbor, recording the discovery edge. After all neighbors have been processed, color $u$ black, increment the clock and record $f[u]$. Start again from every remaining white vertex to obtain a forest. Each vertex is discovered once and each edge scanned once, so the time is $O(|V|+|E|)$ with adjacency lists.

The DFS parenthesis property says that for distinct vertices $u,v$, their intervals $[d[u],f[u]]$ and $[d[v],f[v]]$ are disjoint or one lies strictly inside the other. Moreover $v$ is a proper descendant in a rooted tree of $u$ exactly when $d[u]<d[v]<f[v]<f[u]$. A recursive call finishes before its caller returns, while completed calls from separate branches have disjoint intervals; these two possibilities prove the property.

False. Take two vertices $u,v$ with both directed edges, and start depth-first search at $v$. The timestamps are $d[v]=1$, $d[u]=2$, $f[u]=3$, $f[v]=4$. There is an edge, hence a directed path, from $u$ to $v$, but $f[u]<f[v]$. Reaching a gray ancestor does not make the ancestor finish first.

False. Use only the directed edge $u\to v$, but choose $v$ first in the outer loop of depth-first search. It finishes before a second discovery tree starts at $u$: $d[v]=1$, $f[v]=2$, $d[u]=3$, $f[u]=4$. The edge supplies the required directed path and $f[u]>f[v]$, yet $d[u]>d[v]$. A path to an already black vertex need not put the two vertices into one discovery tree.

False. Let the directed edges be $r\to u$, $u\to r$, and $r\to v$. Start depth-first search at $r$ and explore its neighbor $u$ before $v$. ThenThe directed path $u\to r\to v$ exists and $d[u]<d[v]$, but $u$ and $v$ are siblings in the discovery tree. An existing path may leave the current recursive branch via a gray ancestor and only later enter a different branch. The usual white-path condition would need all vertices of a suitable path to be white when $u$ is discovered; that condition is absent here.

False for directed distance. Take four vertices $a,b,c,d$. Put both directed edges between every distinct pair in $\{a,b,c\}$, and add $d\to a$ and $d\to b$. Every vertex has out-degree two, satisfying $|V|/2$, and there are no self-loops. Nevertheless no directed path leads from any of $a,b,c$ to $d$, so the claimed finite upper bound on graph distance fails.

If “connected” means weakly connected, that portion does follow: a weak component of size $m$ gives each of its vertices out-degree at most $m-1$, so each component would have size at least $|V|/2+1$, making two components impossible. It does not imply a strongly connected directed graph. Thus either the strong-connectivity interpretation fails outright or the weak interpretation leaves the distance assertion false; the complete claim is false in either case.

First run breadth-first search from $s$ to compute each distance $D(v)$. All are finite by hypothesis. Next compute the strongly connected components and their condensation graph $H$. For every component $C$, initialize a representative $b(C)$ minimizing $D(v)$ over $v\in C$. Process components in reverse topological order, usingBreak equal-distance ties consistently, for example by fixed vertex index. Return $b(C)$ for every $u\in C$.

Every vertex of one strongly connected component reaches every other; every reachable different component is reached through some first outgoing edge of $H$. Since $H$ is a Directed acyclic graph, reverse topological order has already solved every successor. Induction over that order proves that the representative minimizes $D$ over all reachable vertices. This is minimum reachable label propagation.

All stages take $O(|V|+|E|)$ time and $O(|V|+|E|)$ space with explicit adjacency lists. Retaining parallel component edges is harmless: they can be scanned once each without sorting or deduplication. Reachability here includes the length-zero path, so $u\in P(u)$; this standard convention also makes the requested answer meaningful at a sink.

Replace breadth-first search by Dijkstra's algorithm from $s$, using the positive edge weights to compute $D(v)$. The strongly connected components, the condensation graph and the reverse-topological order propagation are unchanged, because reachability ignores weights. Only the label assigned to a reachable vertex changes.

With a binary heap, the total time is $O((|V|+|E|)\log |V|)$, including the linear component-processing stages. More specialized priority queues give their corresponding shortest-path bounds. The proof still compares the precomputed distances from $s$; it must not add the weight of a path from $u$ to the candidate, which would optimize a different quantity.