Если есть цикл, конечно, ответа не существует.

Иначе, рассмотрим произвольную вершину. Посмотрим на ребра, в нее ведущие. Рассмотрим среди них самую правую в топологической сортировке. Если она не является ее предком в дереве (которое требуется построить), то у нее в поддереве не будет этой вершины (так как остальные вершины находятся левее). А значит, у каждой вершины, кроме корня, предком является вершина, ведущая в нее, находящаяся как можно правее в топологической сортировке. Таким образом можно построить дерево.

Как проверить, что это дерево подходит? Достаточно проверить, что для любого ребра ориентированного графа, вершина, из которой исходит ребро, является предком второй вершины. Это можно сделать с помощью времен входа-выхода.

Таким образом, время работы есть $$$O(n+m)$$$.