Контест 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
- Алгоритм Кана по входящим степеням.
- Обычная очередь даст какой-то порядок, но не наименьший.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.