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

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 .
Both occur. Starting the outer traversal with leaves undiscovered and gives time . Starting with and taking its edge to first makes an ancestor and gives time . The argument does not assume any particular order on the other edges.

New to topics? Read the docs here!