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

Use Kahn's algorithm for topological sorting. With an adjacency list representation, count every vertex's indegree by scanning the edges. Put all zero-indegree vertices in a queue. Repeatedly remove one such vertex $u$, append it to the output, and delete its outgoing edges by decrementing the stored indegree of each neighbour; enqueue a neighbour exactly when its count becomes zero.

The loop invariant is that stored counts are the indegrees in the unreported subgraph and the queue contains exactly its unreported zero-indegree vertices. A nonempty finite Directed acyclic graph always has such a vertex: otherwise following incoming edges would eventually repeat a vertex, creating a directed graph cycle. Thus the queue cannot become empty while any vertex remains.

For every original edge $u\to v$, $v$ cannot enter the output until that edge has been removed by outputting $u$. ThereforeEach vertex enters and leaves the queue once, and every edge is scanned a constant number of times, giving $\boxed{\Theta (|V|+|E|)}$ time and $O(|V|)$ auxiliary space beyond the adjacency lists. If given only an adjacency matrix, scanning neighbours instead takes $\Theta (|V{|}^2)$ time.

Allow a zero-length graph path, as in Question 5. Then every vertex $a$ reaches itself, proving reflexivity. If $a\equiv b$, its definition already includes both directions of reachability, so interchanging $a,b$ proves symmetry.

If $a\equiv b$ and $b\equiv c$, concatenate the graph paths $a\to b$ and $b\to c$ to obtain reachability from $a$ to $c$. Similarly concatenate $c\to b$ and $b\to a$ for the reverse direction. Repeated vertices can be removed if graph paths are required to be simple. Thus $a\equiv c$, proving transitivity. ConsequentlyThe zero-length convention matters for an isolated vertex: it is still a singleton strongly connected component.

Here the source's unrestricted “cycle” means a closed walk, permitting repeated vertices; part (d) explicitly separates this from a simple cycle.^[ref]

Suppose a closed walk contains both colours. Any two vertices on it reach one another by following suitable portions of the closed walk. All its vertices, and therefore all its edges, lie inside one strongly connected component. That strongly connected component contains internal edges of both colours.

Conversely, suppose one strongly connected component contains a black edge $u\to v$ and a white edge $x\to y$. Its strong connectivity supplies a graph path from $v$ to $x$ and another from $y$ to $u$, both inside the component. ConcatenateThis is a closed walk containing both chosen edges. Either connecting graph path may have length zero. Thus the mixed-colour closed walk criterion isThe edges must be internal: differently coloured edges merely leaving a strongly connected component do not establish the claim.

Take two directed triangles meeting only at a central vertex $a$. Make $a\to b\to c\to a$ entirely black and $a\to d\to e\to a$ entirely white. All five vertices lie in one strongly connected component, since every vertex can reach $a$ and can be reached from $a$. It contains internal edges of both colours.

A closed walk can traverse the black triangle and then the white triangle. But a simple cycle using edges from both triangles would have to pass through $a$ to change triangles and pass through $a$ again to return. It would repeat $a$ other than the single start/end identification, contradicting simplicity. Removing $a$ separates the two triangles, so no other transition between them is possible. ThereforeThis example avoids self-loops and works even when a directed simple cycle is required to have at least three vertices.

Use the two-pass strongly connected component algorithm. First run a complete depth-first search of $G$, starting a new search at each unvisited vertex as necessary. Append each vertex to a list when its recursive call finishes. Next construct the graph transpose $G^T$ by reversing every edge. Reset all visited flags. Process the vertices in decreasing first-pass finishing order, running depth-first search in $G^T$ from each still-unvisited vertex. The newly reached vertices in each such search form one strongly connected component.

To prove this, contract each strongly connected component to one vertex. The resulting condensation graph is a Directed acyclic graph, because a directed graph cycle of distinct components would make them mutually reachable and hence a single component. For a component $C$, write $F(C)$ for its largest first-pass finishing time. If there is an edge $C\to D$ between distinct components, then $F(C)>F(D)$. Indeed, if the first search reaches $C$ before $D$, it can reach $D$, which must finish before the search in $C$ finishes. If it reaches $D$ first, $D$ cannot reach $C$ or they would be the same component, so $D$ finishes before $C$ is discovered.

Among unreported components, the one with greatest $F$ therefore has no incoming edge from another unreported component in $G$. In the graph transpose it has no outgoing edge to any other unreported component. A second-pass search cannot escape it, while strong connectivity lets that search reach all its vertices. Earlier reported components are ignored by the visited flags. Repeating this argument provesBoth depth-first searches visit every vertex and scan every edge once, and transposition costs $\Theta (|V|+|E|)$. Therefore the total time complexity is $\boxed{\Theta (|V|+|E|)}$ with adjacency lists. Storage for the transpose is $O(|V|+|E|)$, while visited flags, finishing order and the search stack use $O(|V|)$ additional space. No sorting is needed: reverse the list recorded at finishing time.