Перекрытия улиц
Город готовится к ремонту дорог: улицы будут перекрывать одну за другой и не открывать до конца ремонта. Диспетчеру нужно заранее знать, во что превратится город после каждого перекрытия: на сколько частей он распадётся, если считать связанными перекрёстки, между которыми можно проехать по открытым улицам.
Два теста — настоящий граф улиц центра Алматы из OpenStreetMap: 7909 перекрёстков и 10 423 куска улиц. В одном перекрывают все улицы в случайном порядке, в другом — только куски крупных дорог.
Вход
В первой строке n и m (1 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000) — число перекрёстков и улиц. Дальше m строк: концы улицы a и b (1 ≤ a, b ≤ n). Улицы нумеруются от 1 в порядке ввода; между двумя перекрёстками может быть несколько улиц, а улица может начинаться и кончаться на одном перекрёстке. Затем число перекрытий q (1 ≤ q ≤ m) и q различных номеров улиц в порядке перекрытия.
Выход
q чисел, по одному в строке: на сколько частей распался город сразу после каждого перекрытия. Отдельный перекрёсток, к которому не ведёт ни одна открытая улица, — тоже часть.
Примеры
Пример 1
6 7 1 2 2 3 3 4 4 5 5 1 3 6 1 3 5 7 1 3 6 4
1 1 2 3 4
Пример 2
4 5 1 2 1 2 2 3 3 3 3 4 4 1 4 2 5
1 1 2 3
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 9 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
После каждого перекрытия можно пересчитать части обходом в ширину. Сколько это стоит при ста тысячах перекрытий?
2Подсказка 2
Система непересекающихся множеств умеет сливать части, но не разрезать. Все перекрытия известны заранее. Что, если смотреть на ремонт с конца?
3Идея
Прочитаем список перекрытий задом наперёд — это список открытий. Начнём с города, в котором закрыто всё, что будет закрыто: соберём части из улиц, которые не перекрывают никогда. Ответ для последнего перекрытия — это число частей сейчас. Откроем улицу последнего перекрытия — получим город после предпоследнего, и так до первого. Каждое открытие — слияние, а слияния система непересекающихся множеств делает почти мгновенно.
4Разбор
Счётчик частей начинается с n и уменьшается на единицу при каждом удачном слиянии. Сначала сливаем концы всех улиц, которых нет в списке перекрытий. Потом идём по списку с конца: записываем текущее число частей как ответ для i-го перекрытия и только после этого открываем i-ю улицу. Порядок важен: ответ для перекрытия i — город, где эта улица уже закрыта. В конце печатаем ответы в прямом порядке.
Кратные улицы и улицы-петли решение не смущают: если концы уже в одной части, слияние ничего не делает. Во втором примере после первого перекрытия перекрёстки 1 и 2 связаны второй улицей, и город по-прежнему целый.
Такой приём — отвечать на запросы не в том порядке, в котором их задали, — называют офлайн-обработкой. Он работает, потому что все запросы известны заранее. Если бы перекрытия приходили по одному и отвечать нужно было сразу, пришлось бы брать структуры динамической связности — они сложнее на порядки.
4+Решение
5Сложность
O((n + m) α(n)) времени и O(n + m) памяти. Обход после каждого перекрытия — O(q·(n + m)): на настоящем Алматы это десять тысяч обходов города, а в пятом тесте — сто тысяч обходов графа из пятидесяти тысяч вершин.
6Типичные ошибки
- Обход после каждого перекрытия. Верно, но уже на третьем тесте — 10 423 обхода города, каждый по 7909 перекрёсткам и всем их улицам, — не укладывается во время.
- Записать ответ после открытия. Тогда ответы сдвинутся на одно перекрытие: для последнего получится город, где его улица ещё открыта.
- Забыть улицы, которые не перекрывают. В четвёртом тесте перекрывают только 2616 кусков крупных дорог, а остальные почти восемь тысяч улиц открыты всё время.