Недостающие улицы
В городе n перекрёстков и m улиц, часть из них с односторонним движением. Где-то на карте есть тупики-ловушки: въехать можно, а выехать, не нарушая правил, нельзя. Есть и места наоборот, куда по правилам не попасть вовсе. Мэрия готова проложить несколько новых односторонних улиц — между любыми двумя перекрёстками, где угодно, — чтобы из каждого перекрёстка можно было доехать до каждого. Какое наименьшее число улиц для этого нужно?
Вход
В первой строке n и m (1 ≤ n ≤ 60 000, 0 ≤ m ≤ 100 000). Дальше m строк a b t: улица между перекрёстками a и b; при t = 1 по ней можно ехать только из a в b, при t = 0 — в обе стороны. Бывают петли и повторяющиеся улицы.
Выход
Наименьшее число новых односторонних улиц.
Пятый, шестой и седьмой тесты — центр Алматы по данным OpenStreetMap, как в статье: улицы как на карте, двусторонние улицы, ставшие односторонними наугад, и направления по Роббинсу. Вершина, которой нет на карте, — весь мир за её краем.
Примеры
Пример 1
8 11 1 2 1 2 3 1 3 1 1 2 4 1 4 5 1 5 6 1 6 4 1 5 7 1 7 8 1 8 7 1 3 8 1
1
Пример 2
5 2 1 2 0 3 4 0
3
Ограничения
- Время · Python
- 6000 мс
- Время · Go
- 2000 мс
- Память
- 256 МБ
- Проверка
- 12 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Внутри компоненты сильной связности новые улицы не нужны: там и так из всех мест можно доехать до всех. Сожмите каждую компоненту в точку. Какой граф получится?
2Подсказка 2
В сжатом графе нет циклов. Посмотрите на компоненты, в которые не ведёт ни одна стрелка, и на те, из которых не выходит ни одна. Сколько новых улиц нужно хотя бы для них?
3Идея
Найдём компоненты сильной связности и посмотрим на граф компонент — конденсацию. Это граф без циклов. Пусть в нём s истоков (компонент без входящих стрелок) и t стоков (без исходящих); компонента без стрелок вовсе считается и тем и другим. Если компонента одна, ответ 0. Иначе ответ равен max(s, t).
Меньше нельзя: в каждый исток должна войти хотя бы одна новая улица — иначе туда по-прежнему не попасть, и новая улица входит только в одну компоненту. Значит, новых улиц не меньше s, и по той же причине не меньше t. Что max(s, t) всегда хватает, доказали Капали Эсваран и Роберт Тарьян в 1976 году. Идея — подобрать как можно больше пар «исток и сток, достижимый из него» и связать пары в один круг: из стока каждой пары провести улицу в исток следующей. Оставшиеся истоки и стоки подцепляются к этому кругу по одному. Аккуратно выбрать пары не так просто, как кажется: в 2005 году С. Рагхаван нашёл ошибку в опубликованном алгоритме построения, хотя сама формула верна.
4Разбор
Тарьяном находим номер компоненты для каждого перекрёстка. Затем проходим по всем улицам: улица между разными компонентами даёт выход первой и вход второй. Считаем компоненты без входов и без выходов и печатаем больший счёт; если компонента одна — ноль.
Двусторонние улицы — это просто два ребра. В первом примере компоненты {1 2 3}, {4 5 6} и {7 8}: исток, середина и сток, поэтому хватит одной улицы — из стока в исток. Во втором примере три острова без стрелок между ними, каждый и исток, и сток: нужно три улицы, круг 1 → 3 → 5 → 1.
На настоящей карте Алматы ответ 5: столько стоков-ловушек вне главной компоненты, а истоков всего два. Если же сделать все двусторонние улицы односторонними наугад, понадобится 1266 новых улиц, а по Роббинсу — ни одной.
4+Решение
5Сложность
Тарьян и подсчёт — O(n + m). Рекурсивный поиск в глубину на одиннадцатом тесте уходит на глубину 60 000: в Python без поднятого предела рекурсии он упадёт, поэтому эталон обходит граф своим стеком кадров.
6Типичные ошибки
- Считать перекрёстки вместо компонент. Перекрёсток без входящих улиц — исток, но исток бывает и большим: в первом примере у каждого перекрёстка есть и вход, и выход, а ответ 1.
- Сложить истоки и стоки. Одна улица из стока в исток закрывает сразу обоих.
- Забыть, что граф может уже быть сильно связным. Тогда истоков и стоков по одному — сама единственная компонента, — а ответ 0.
- Забыть про острова без улиц. Компонента без стрелок — и исток, и сток одновременно.