Depth first search

[10 marks Depth First Search and Topological Sort. Let G be a directed acyclic graph. We want a linear time algorithm to decide if there is a directed path in G that goes through every vertex exactly once. For each of the following approaches, either prove or disprove that it works correctly. (a) 5 marks] Run DFS from some vertex. If the DFS tree is a path, then output the path, otherwise output FAIL. (b) [5 marks] Run DFS to find a topological sort of the graph and test if that ordering is a directed path. If it is, then output the path, otherwise output FAIL. (Recall that we get a topological sort by ordering the vertices in decreasing order of finish time.)