Нумерация глав
Черновики глав учебника лежат в папке под рабочими номерами от 1 до n. Перед печатью главам нужно дать номера в книге — тоже от 1 до n, каждый по разу, — так, чтобы глава, на которую опирается другая, стояла раньше неё. Правильных нумераций обычно много. Редактор хочет такую, где у главы с рабочим номером 1 номер в книге как можно меньше; среди таких — где как можно меньше номер у главы 2; и так далее.
Один из тестов — главы базового курса этого сайта, рабочие номера которым даны по алфавиту их адресов.
Вход
В первой строке числа n и m (1 ≤ n ≤ 100 000, 0 ≤ m ≤ 200 000). Дальше m строк a b: глава a должна стоять в книге раньше главы b (1 ≤ a, b ≤ n, a ≠ b).
Выход
n чисел через пробел: номер в книге у главы 1, у главы 2, …, у главы n. Если правильной нумерации нет, выведите -1.
Примеры
Пример 1
3 1 3 1
2 3 1
Пример 2
6 5 5 1 5 2 4 2 6 3 2 3
2 4 6 3 1 5
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 2000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Самое естественное: номера по порядку, и каждый следующий номер в книге — самой маленькой по рабочему номеру главе из тех, что уже можно ставить. Проверьте на первом примере, какой номер получит глава 1.
2Подсказка 2
Главе 1 выгодно получить маленький номер, но её держит глава 3. Чтобы глава 1 встала пораньше, глава 3 должна встать ещё раньше — даже ценой номера главы 2. Жадность с начала книги этого не видит. А с конца?
3Подсказка 3
Какая глава должна получить последний номер n? Из глав, за которыми ничего не обязано идти, выгоднее всего отдать его той, у которой рабочий номер больше.
4Идея
Нумеруем с конца. Номер n получает глава с наибольшим рабочим номером среди тех, за которыми не обязана стоять ни одна ненумерованная глава. Вычёркиваем её и повторяем с номером n − 1. Это алгоритм Кана на перевёрнутом графе, где очередь заменена кучей с максимумом наверху.
5Разбор
Почему последний номер выгодно отдать наибольшей свободной главе c. Пусть в лучшей нумерации L номер n достался другой свободной главе x; тогда x < c, ведь c — наибольшая свободная. Переставим: c получает номер n, а все главы, у которых номер был больше прежнего номера c, сдвигаются на единицу вниз. Нумерация осталась правильной: за c ничего не обязано идти, а порядок остальных не изменился. Все главы с рабочими номерами меньше c получили тот же номер или на единицу меньше, и x — точно меньше. Значит, новая нумерация лексикографически меньше L, и L не была лучшей. Дальше та же задача для оставшихся глав и номеров 1 … n − 1.
Почему не работает жадность с начала. В первом примере глава 3 должна стоять раньше главы 1. Свободны главы 2 и 3; жадность отдаёт номер 1 главе 2, потом 2 — главе 3, и глава 1 получает 3: ответ 3 1 2. А нумерация 2 3 1 лучше: глава 1 получает номер 2. Жадность с начала строит лексикографически наименьший порядок глав — это другая задача, и на ней она верна.
Реализация: для каждой главы считаем, сколько глав обязано стоять после неё. Главы со счётчиком 0 — в кучу (в Python — heapq с минусом, в Go — container/heap с обратным сравнением). Достали главу — она получает очередной номер с конца, а у глав, которые обязаны стоять перед ней, счётчик уменьшается. Если номера раздали не все, в графе цикл: −1.
5+Решение
6Сложность
Каждая глава один раз входит в кучу и выходит из неё, каждое условие просматривается один раз: O((n + m) log n).
7Типичные ошибки
- Жадность с начала книги. Минимизирует порядок, а не номера:
wrong.pyпадает на первом примере. - С конца, но с наименьшей главой. Последний номер должен уходить главе с наибольшим рабочим номером: маленький номер нужнее маленьким главам.
- Вывод порядка вместо номеров. Ответ — номер в книге для каждой главы по порядку рабочих номеров, а не список глав по порядку в книге.
- Цикл. Если раздали меньше n номеров, выводите −1.