Given a directed acyclic graph G, give a linear time algorithm to determine if the graph has a directed path that visits every vertex.
You can assume you are given a list of nodes and two adjacency lists: Enter[v] which contains all the edges entering node v, and Exit[v] which contains all the edges leaving node v.
I was thinking that I could pick a node that doesn't have edges entering it and run DFS on it. During DFS, every time I get to a node with no children, I check if all the nodes have been visited. If not, I backtrack and explore a different path each time. If I make it back to the original node or if I hit a node with no children, I can check if I have seen all the nodes. If not, I return that there is no such path, else I have found a path.
Would this work?