Checking if there is a single path that visits all nodes in a directed graph

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?

The problem is how to deal with visited vertex.

If you keep following, the time complexity is not linear because of repeated visiting. Otherwise, your algorithm will fail in the following simple example:

1 --> 2 -----------> 3 --> 4
        \         /
         --> 5 -->

The first search find 1-2-3-4, then it goes back to 2 and find 1-2-5-3. Now because 3 is visited, the search stops, and thus finally fails.

A hint (or answer) to solve the problem: performing a topological ordering firstly.

StackExchange Computer Science Q#88368, answer score: 4