Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2017/functional-programming-design-and-analysis-of-algorithms-resit/7/c/i/solution

False. Use vertices , edges , , , and start depth-first search at , scanning before . The times are
There is a directed path and , but and are separate children of . Thus is not a descendant of . The path leaves through an already gray ancestor; its later branch need not be explored inside 's recursive call. This is consistent with the DFS parenthesis property.
Figure 1.
DFS counterexamples distinguish reachability from tree ancestry
. Left: the path from u through its ancestor x reaches a later sibling v, after u has finished. Right: root order a,u,c makes three singleton DFS trees, though u has an incoming and an outgoing edge. Details.

New to topics? Read the docs here!