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 / c

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|)$.