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