Ночные перекрытия
Дорожная служба составляет график ночных ремонтов: каждую ночь перекрывают одну улицу целиком, утром её открывают снова. Перед публикацией графика нужно знать, кого каждое перекрытие отрежет: сколько перекрёстков на эту ночь потеряют связь с остальным миром — до них нельзя будет доехать ни из города, ни из-за его пределов.
Перекрёстки пронумерованы от 1 до n, и перекрёсток 1 особый: это весь мир за краем карты, он связан с каждой улицей, которая уходит за край. Улицы двусторонние. Между двумя перекрёстками может быть несколько разных улиц — например, две проезжие части одного проспекта. Пятый тест — улицы Алматы из статьи, от центра до гор: 11 724 вершины вместе с миром и 15 169 кусков улиц, и перекрыть по очереди предлагают каждый.
Вход
В первой строке n и m (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 200 000). Дальше m строк a b — улица между перекрёстками a и b (a ≠ b); улицы нумеруются от 1 в порядке ввода. От перекрёстка 1 по улицам можно доехать до любого. Затем число ночей q (1 ≤ q ≤ 200 000) и q номеров улиц, которые перекрывают; номера могут повторяться.
Выход
q чисел, по одному в строке: сколько перекрёстков, кроме перекрёстка 1, не будут связаны с перекрёстком 1, пока перекрыта эта улица (остальные улицы открыты).
Примеры
Пример 1
8 10 1 2 1 3 2 3 3 4 4 5 4 5 5 6 6 7 7 5 6 8 5 4 5 6 8 10
5 0 0 0 1
Пример 2
4 3 1 2 2 3 2 4 3 1 2 3
3 1 1
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 2000 мс
- Память
- 256 МБ
- Проверка
- 8 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Перекрытие отрезает хоть кого-то, только если улица — мост. Как найти все мосты сразу, рассказано в статье. Осталось понять, кого именно отрезает каждый мост.
2Подсказка 2
Начните поиск в глубину с перекрёстка 1. Мост — ребро дерева поиска, и та его сторона, где нет перекрёстка 1, — это поддерево нижнего конца. Сколько в нём вершин?
3Подсказка 3
Посмотрите на первый пример: между перекрёстками 4 и 5 две улицы. Что сделает ваш код с улицей 5?
4Идея
Один поиск мостов из вершины 1, и по ходу — размер каждого поддерева: когда поиск возвращается из v в родителя, size(v) уже посчитан, и его прибавляют к size родителя. Если ребро u–v оказалось мостом, отрезано ровно поддерево v: все рёбра из него наружу, кроме моста, вели бы к предкам, а их нет. Ответ для моста — size(v), для любой другой улицы — 0. Все ответы готовы до первого вопроса, и каждый вопрос стоит O(1).
5Разбор
Поиск без рекурсии, со своим стеком: в пятом тесте стек поиска дорастает до 2453 перекрёстков, а в седьмом — до 58 130, и рекурсия в Python упрётся в предел. Для каждой вершины храним tin, low, size и номер ребра, по которому в неё пришли. Проход по ребру назад в родителя пропускаем только по номеру ребра: вторая улица к тому же перекрёстку — настоящий объезд, она должна опустить low. При возврате из v в u: low(u) = min(low(u), low(v)), size(u) += size(v), и если low(v) > tin(u), записываем cut_off[ребро] = size(v).
Почему корень — именно перекрёсток 1: тогда «отрезанная сторона» моста всегда поддерево, и не нужно гадать, какая из двух частей потеряла связь с миром. Если бы поиск начался с другой вершины, для моста над корнем пришлось бы брать дополнение: n − size.
В городе из пятого теста ненулевых ответов 3005 — столько мостов, — и 2201 из них равен единице: за улицей один тупиковый перекрёсток. Самый большой ответ — 128, это дороги в горы из статьи.
5+Решение
6Сложность
O(n + m) на поиск и O(1) на вопрос; память O(n + m). Перебор «перекрыть и обойти граф» стоил бы O(q(n + m)) — для последнего теста это больше двадцати миллиардов шагов.
7Типичные ошибки
- Пропуск родителя по вершине. Код «не ходить туда, откуда пришёл» выкидывает вместе с ребром дерева и вторую улицу к тому же перекрёстку. Двойная улица становится мостом, и в первом примере улица 5 «отрезает» четыре перекрёстка вместо нуля. В городе из пятого теста так появляются 25 ложных мостов.
- Рекурсия. Глубина поиска в седьмом тесте — 58 130; рекурсивная версия упадёт с
RecursionError, а с поднятым пределом может уронить сам интерпретатор. - Не та сторона моста. Если начинать поиск не с вершины 1, поддерево может оказаться как раз той частью, что осталась с миром.