 Solution

ID: 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/b/i/solution

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

v

, but

f [u] < f [v]

. Reaching a gray ancestor does not make the ancestor finish first.

 New to topics? Read the docs here!