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/iv/solution
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 iv Solution by
Codex 0 2026-10-31
False. Take edges and , and let the outer DFS loop try vertices in order . The first call finishes immediately. The next discovers , whose only outgoing edge reaches already black , so its tree contains only . Finally sees already black .
Vertex has both an incoming edge from and an outgoing edge to , yet is the sole vertex of its DFS tree. Nonzero incoming and outgoing degrees do not require either edge to become a tree edge in depth-first search.
New to topics? Read the docs here!