We are given a directed graph, the number of vertices and edges. We need to decide, whether there is a [starting] vertex where we can get started and visit all the vertices. All this in linear time.

I was thinking about DFS - if the number of vertices in the result matches the total number of vertices, obviously there is a way to visit all the vertices. The only problem about this - I guess - is that how do I choose the vertex where I'm starting off. Or can I do DFS with all the vertices and still remain in linear time?

(I tried to look into Eulerian path and Hamilton path problems, but I think they have nothing to do with my problem)

Any feedback is appreciated.

We are given a directed graph, the number of vertices and edges. We need to decide, whether there is a [starting] vertex where we can get started and visit all the vertices. You can revisit vertices, but can't "use" edges twice or more time. All this in linear time.

I was thinking about DFS - if the number of vertices in the result matches the total number of vertices, obviously there is a way to visit all the vertices. The only problem about this - I guess - is that how do I choose the vertex where I'm starting off. Or can I do DFS with all the vertices and still remain in linear time?

(I tried to look into Eulerian path and Hamilton path problems, but I think they have nothing to do with my problem)

Any feedback is appreciated.