Situation 1. G has no cycle
It seems we need to do BFS, traverse the graph from the bottom, let each edge point to the leaf vertex, since it's a graph without any cycles, so each vertex will have at most one edge point to it. And BFS takes O(V+E) time.

Situation 2. G has at most 1 cycle
If there is a cycle how could we choose the direction of 2 edges that point to the same vertex?