Сколько семестров
В учебном плане n курсов, и у некоторых есть пререквизиты: курс a нужно сдать раньше курса b. За семестр можно пройти сколько угодно курсов, но только тех, у которых все пререквизиты сданы в прошлых семестрах. За сколько семестров можно пройти весь план?
Та же задача у сборщика программ: за один такт параллельной сборки можно собрать все пакеты, чьи зависимости уже готовы. Среди тестов — 66 глав базового курса этого сайта, стандартная библиотека Go с её 2790 импортами и пакеты Debian из песочницы, где запускается ваш код.
Вход
В первой строке числа n и m (1 ≤ n ≤ 100 000, 0 ≤ m ≤ 200 000). Дальше m строк a b: курс a — пререквизит курса b (1 ≤ a, b ≤ n, a ≠ b). Пары могут повторяться.
Выход
Наименьшее число семестров или -1, если пройти план нельзя: пререквизиты замкнулись в круг.
Примеры
Пример 1
6 6 1 2 1 3 2 4 3 4 4 5 1 6
4
Пример 2
4 4 1 2 2 3 3 1 1 4
-1
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
В первый семестр можно взять все курсы без пререквизитов. Какие курсы откроются ко второму?
2Подсказка 2
Семестр курса — на единицу больше самого позднего семестра среди его пререквизитов. Если считать это рекурсией без запоминания, сколько раз посчитается курс в тесте, где двадцать слоёв по пятьдесят курсов?
3Идея
Это алгоритм Кана, запущенный волнами. Волна 1 — курсы, которые ничего не ждут. Сдали волну — у каждого курса уменьшаем счётчик несданных пререквизитов, и те, у кого он дошёл до нуля, образуют следующую волну. Число волн и есть ответ: раньше курс пройти нельзя, потому что до него тянется цепочка пререквизитов такой длины, а позже не нужно, потому что в своей волне у курса уже всё сдано.
4Разбор
Читаем пары, для каждого курса считаем, сколько у него пререквизитов, и запоминаем, кого он открывает. Первая волна — курсы со счётчиком 0. Обходим волну, уменьшаем счётчики, собираем следующую. Если по окончании сданы не все курсы, оставшиеся ждут друг друга по кругу: выводим −1.
Ответ равен числу курсов на самой длинной цепочке пререквизитов. Для глав базового курса это 18: от «Что умеет программа» через списки, словари, объекты, стек, графы и автоматы до «Экспедиции коммивояжёра». Стандартная библиотека Go собирается минимум в 29 тактов, сколько бы ни было ядер, а пакеты Debian без правил dpkg не настроить вовсе: libc6 и libgcc-s1 зависят друг от друга.
Повторяющиеся пары не мешают: каждая и увеличивает счётчик, и уменьшает его.
4+Решение
5Сложность
Каждый курс попадает в волну один раз, каждая пара просматривается один раз: O(n + m).
6Типичные ошибки
- Рекурсия без запоминания. Число путей растёт экспоненциально: в тесте с двадцатью слоями их 5019. Уже на стандартной библиотеке Go такое решение не успевает — это
wrong.py. С запоминанием рекурсия становится той же динамикой по топологическому порядку, но в Python ей нужен большой запас глубины: в одном из тестов цепочка из ста тысяч курсов. - Пропущенный цикл. Если не проверить, что сданы все курсы, на плане с кругом выйдет число вместо −1.
- Одна очередь без волн. Обычный алгоритм Кана тоже подходит, если помнить для каждого курса номер его волны: волна курса — на единицу больше волны пререквизита, который освободил его последним.