Дан ориентированный граф с n вершинами и m рёбрами. Требуется перенумеровать его вершины таким образом, чтобы каждое рёбро вело из вершины с меньшим номером в вершину с большим.
Иными словами, требуется найти перестановку вершин (топологический порядок), соответствующую порядку, задаваемому всеми рёбрами графа.
Если мы будем в момент выхода из dfs(v) добавлять нашу вершину в начало некоего списка, то в конце концов в этом списке получится топологическая сортировка.
Таким образом, искомая топологическая сортировка — это сортировка в порядке убывания времён выхода.