Частоты для вышек
Радиовышки сети нужно настроить на частоты. Некоторые пары вышек мешают друг другу — такие должны работать на разных частотах. Частот мало, и инженеры знают про сеть одно полезное свойство: в любой её части найдётся вышка, которой внутри этой части мешают не больше d других. Частью здесь называется любой набор вышек — и вся сеть, и любой её кусок.
Назначьте вышкам частоты с номерами от 1 до d + 1 так, чтобы мешающие друг другу вышки работали на разных частотах. Если подходящих назначений несколько, годится любое. В одном из тестов вместо вышек — кварталы центра Алматы из статьи о раскраске графа: соседние кварталы должны получить разные цвета.
Вход
В первой строке число вышек n, число мешающих пар m и число d (1 ≤ n ≤ 105, 0 ≤ m ≤ 3·105, 0 ≤ d < n). Дальше m строк a b: вышки a и b мешают друг другу (1 ≤ a, b ≤ n, a ≠ b, пары не повторяются). Гарантируется, что свойство из условия выполнено.
Выход
n чисел через пробел — частоты вышек 1, 2, …, n, каждая от 1 до d + 1.
Примеры
Пример 1
4 3 1 1 3 3 4 4 2
1 2 2 1
Пример 2
6 10 3 1 2 1 3 1 4 1 5 1 6 2 3 3 4 4 5 5 6 6 2
1 3 2 3 2 4
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 11 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Раздайте частоты жадно, в порядке номеров: каждой вышке — наименьшую частоту, которой нет у уже настроенных соседей. Проверьте на первом примере. Почему жадный способ иногда тратит лишнюю частоту и от чего это зависит?
2Подсказка 2
Жадная вышка получает частоту не больше, чем «число уже настроенных соседей + 1». Значит, нужен порядок, в котором у каждой вышки к её ходу настроено не больше d соседей. Какую вышку тогда разумно настроить последней?
3Идея
Последней — ту, у которой во всей сети не больше d соседей: она есть по условию, и к её ходу при любом раскладе будет занято не больше d частот. Уберём её из сети. Оставшиеся вышки — тоже часть сети, и в них снова найдётся вышка с не больше чем d соседями среди оставшихся: она будет предпоследней. И так далее. Это порядок «наименьший последним» из статьи: снимаем вышку с наименьшим числом оставшихся соседей, а настраиваем в обратном порядке.
4Разбор
Почему хватает d + 1 частоты. Возьмём любую вышку v. Когда её настраивают, настроены ровно те её соседи, которых сняли позже v, — то есть те, что ещё оставались в сети в момент, когда снимали v. Их не больше числа оставшихся соседей v в тот момент, а это число не больше d: снимаем мы вышку с наименьшим числом соседей, а по условию в оставшейся части есть вышка, у которой их не больше d. Значит, занято не больше d частот, и среди номеров 1, …, d + 1 свободный найдётся.
Снимать вышки за O(n + m) помогают корзины: корзина с номером k хранит вышки, у которых осталось k соседей. Когда соседа снимают, вышка переезжает в корзину на единицу ниже, а старая запись остаётся и при извлечении пропускается. Указатель на самую нижнюю непустую корзину после каждого снятия опускается не больше чем на единицу, поэтому всего он проходит O(n + m) шагов.
4+Решение
5Сложность
O(n + m): каждая вышка снимается один раз, каждая пара просматривается дважды при снятии и дважды при настройке. Можно и кучей за O((n + m) log n) — так сделано в листинге статьи, и это тоже укладывается во время.
6Типичные ошибки
- Жадно в порядке номеров. Это
wrong.py. В первом примере вышки 1 и 2 получают частоту 1, вышка 3 — частоту 2, а вышке 4, соседке и 2, и 3, остаётся третья, хотя хватает двух. В четвёртом тесте — дереве, построенном против этого порядка, — жадный способ тратит 17 частот вместо двух. - Сначала вышки с наибольшим числом соседей. Порядок Уэлша и Пауэлла часто хорош, но гарантии не даёт: в пятом тесте ему нужно 6 частот при d = 3.
- DSatur. Самый стеснённый следующим — сильный способ, и почти все тесты он проходит. Но в одиннадцатом тесте ему нужно 4 частоты при d = 2: гарантию d + 1 даёт именно порядок «наименьший последним».
- Снимать по исходному числу соседей. Если отсортировать вышки по числу соседей один раз в начале и не обновлять его, получится тот же порядок Уэлша и Пауэлла, только записанный задом наперёд, и оценка не работает: важно число соседей среди оставшихся.