Перекрёсток на ремонте
Перекрёсток закрывают на ремонт целиком: через него нельзя ни проехать, ни повернуть, но все остальные перекрёстки и улицы открыты. Если перекрёсток был единственной связью между частями города, люди из разных частей потеряют друг друга. Для каждого перекрёстка посчитайте, сколько пар других перекрёстков потеряют связь, если закрыть его.
Улицы двусторонние, между двумя перекрёстками может быть несколько улиц. Пятый тест — улицы Алматы из статьи, от центра до гор; там перекрёсток 1 — весь мир за краем карты, и для него ответ тоже нужен.
Вход
В первой строке n и m (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 200 000). Дальше m строк a b — улица между перекрёстками a и b (a ≠ b). Из любого перекрёстка можно доехать до любого.
Выход
n чисел, по одному в строке: для каждого перекрёстка v — число неупорядоченных пар {x, y} различных перекрёстков, отличных от v, между которыми нет пути, пока v закрыт.
Примеры
Пример 1
7 8 1 2 2 3 3 1 3 4 4 5 5 6 6 4 4 7
0 0 8 11 0 0 0
Пример 2
4 3 1 2 2 3 3 4
0 2 2 0
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 2000 мс
- Память
- 256 МБ
- Проверка
- 8 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Ответ не ноль только у точек сочленения. Когда точку v закрывают, остальной город распадается на несколько частей. Если известны их размеры, число потерянных пар считается одной формулой.
2Подсказка 2
Из каких частей складывается город без v? Подумайте о дереве поиска в глубину: какие поддеревья детей v отваливаются целиком, а какие остаются связанными с тем, что выше v?
3Подсказка 3
В первом примере закройте перекрёсток 4. Треугольник 4, 5, 6 касается перекрёстка 4 ребром 6–4. Он отваливается или нет?
4Идея
Поиск в глубину, как в статье, плюс размеры поддеревьев. Ребёнок c вершины v отваливается вместе со всем поддеревом, если low(c) ≥ tin(v): из поддерева не подняться выше v. Такие поддеревья — отдельные части, и рёбер между ними нет: по лемме из статьи все рёбра не из дерева ведут к предкам. Остальные дети держатся за верхнюю часть города, и вместе с ней составляют ещё одну часть размера n − 1 − Σ отвалившихся. У корня отваливаются все дети. Если части имеют размеры s1, …, sk, а их сумма T = n − 1, то пар из разных частей
$$\frac{T^2 - \sum_i s_i^2}{2}.$$5Разбор
Поиск без рекурсии, со стеком кадров. При возврате из c в v: обновить low(v), прибавить size(c) к size(v) и, если v — корень или low(c) ≥ tin(v), прибавить size(c) к сумме отвалившихся частей v и size(c)² — к сумме их квадратов. После поиска для каждой вершины остаток rest = n − 1 − сумма, и ответ (T² − сумма квадратов − rest²) / 2. Для вершины, которая не точка сочленения, у неё одна часть, rest = T, и ответ ноль сам собой.
В первом примере у перекрёстка 4 три части: {1, 2, 3}, {5, 6} и {7}. Пар 3·2 + 3·1 + 2·1 = 11. Часть {5, 6} касается перекрёстка 4 ребром 6–4, поэтому low(5) = tin(4), и отваливается она по нестрогому неравенству.
В городе из пятого теста ненулевых ответов 2553: 2552 точки сочленения и сам мир за краем карты — если его закрыть, расходятся куски города, которые связаны только улицами за краем. Больше всего, 1 484 160 пар, теряется у двух перекрёстков — в начале дороги на «Медеу» и в начале дороги в Большое Алматинское ущелье: каждый делит граф на 128 вершин в горах и 11 595 остальных, и 128 · 11 595 = 1 484 160.
5+Решение
6Сложность
O(n + m): один поиск и один проход по вершинам. Ответ доходит до n²/2 ≈ 5·10⁹ — в Go тип int 64-битный, в Python числа любые, но в языках с 32-битным int он переполнится.
7Типичные ошибки
- Строгое неравенство. Проверка моста low(c) > tin(v) вместо проверки вершины low(c) ≥ tin(v). Часть, которая обратным ребром касается самой v, считается связанной с остальным городом, хотя без v она отваливается. В первом примере у перекрёстка 4 выходит 5 вместо 11.
- Корень по общему правилу. У корня условие low(c) ≥ tin(корня) верно для любого ребёнка, и это правильно: у корня отваливаются все дети. Ошибка — проверять «больше одного ребёнка» и на этом останавливаться: число пар зависит от размеров всех частей.
- Перебор. Закрыть каждый перекрёсток и сосчитать части обходом — O(n(n + m)), в последнем тесте это миллиарды шагов.