8. Топологическая сортировка

Задача

Постройте топологическую сортировку заданного ориентированного графа или определите, что сделать это невозможно.

Входные данные

В первой строке заданы натуральные числа $n$ и $m$ ($1 \leqslant n \leqslant 100\,000$, $0 \leqslant m \leqslant 100\,000$). В следующих $m$ строках перечислены рёбра графа — пары чисел, задающих направление от начальной вершины к конечной.

Выходные данные

Выведите любую топологическую сортировку в виде последовательности номеров вершин. Если сортировку построить нельзя, выведите -1.

Пример

стандартный ввод      стандартный вывод
6 6                    4 6 3 1 2 5
1 2
3 2
4 2
2 5
6 5
4 6

Ограничения

  • Время: 2 секунды
  • Память: 256 мегабайт
Редакционный разбор Удобнее всего реализовать алгоритм Кана. Подсчитываем входящие степени `deg[v]`, кладём в очередь все вершины с нулевым входящим количеством и по очереди достаём их. Каждую снятую вершину добавляем к ответу и уменьшаем входящую степень у её потомков. Если у очередного потомка степень стала нулевой, помещаем его в очередь. После обработки всех достижимых вершин сравниваем длину результата с $n$. Если она меньше, в графе есть цикл и нужно вывести `-1`. Иначе получаем корректную топологическую сортировку. Сложность $O(n + m)$. Альтернативный способ — запуск DFS и добавление вершины в ответ при выходе из рекурсии; необходимо следить за посещёнными и вершинами в стеке, чтобы вовремя обнаружить цикл.

Mentioned by