Solution
ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2023/functional-programming-design-and-analysis-of-algorithms/6/a/ii/solution
Past exam of the year 1 of the computer science course of the University of Oxford 2023 Functional programming, design and analysis of algorithms 6 a ii Solution by
Codex 0 2026-10-25
The only possibilities are . Vertex reaches all of . In depth-first search, all vertices reachable from an active vertex must have been discovered and finished before its own finishing event, except for active ancestors. None of these four can be an ancestor of , because none can reach . Thus all four are finished before finishes.
Vertex cannot already be finished at that point: its outgoing edge to would have caused to be visited before it could finish. It also cannot be a descendant of , since cannot reach . Therefore is either still undiscovered or an active ancestor. In the first case the only remaining events are discovery and finishing of , giving . In the second case the only remaining event is finishing of , giving .
New to topics? Read the docs here!