Контест Senior Задачи на Java обновлено

Порядок выполнения задач

Условие

Есть n задач с номерами от 1 до n и m зависимостей вида a b: задачу a нужно выполнить раньше задачи b. Найдите порядок выполнения всех задач. Если подходящих порядков несколько, выведите лексикографически наименьший (на каждом шаге берётся доступная задача с наименьшим номером).

Ввод: в первой строке n и m (1 ≤ n ≤ 10⁴, 0 ≤ m ≤ 2·10⁴), далее m строк a b.

Вывод: номера задач через пробел или cycle, если зависимости циклические.

Пример

5 4
3 1
3 2
1 4
2 4
3 1 2 4 5

Как подойти

Kahn + PriorityQueue.

Подсказки: 2
  1. Алгоритм Кана по входящим степеням.
  2. Обычная очередь даст какой-то порядок, но не наименьший.

Решите в тренажёре

Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.