Обратный BFS и проверка маршрута за O(1) на шаг — задача «Navigation System» РАЗБОР

Когда задача звучит «обработать $K$ вопросов про кратчайшие пути на одном графе с $n$ вершинами и $m$ рёбрами», у участника есть выбор. Можно запускать BFS на каждый вопрос — это $O(K \cdot (n + m))$ и при $n, m, K \sim 2 \cdot 10^5$ совершенно не уложится. А можно запустить одно BFS один раз и подготовить структуру, по которой каждый вопрос отвечается за $O(1)$ — итог $O(n + m + K)$, с огромным запасом по времени.

Эта задача — отличный учебный кейс под технику. Граф направленный, у нас есть фиксированная цель $t$, и нам нужно по уже выбранному маршруту покомпонентно проанализировать каждый шаг: «по кратчайшему пути в $t$ или нет, и были ли альтернативы». Один трюк — построить обратный граф и пустить BFS из $t$ по нему, получая массив dist[v] = длина кратчайшего пути из $v$ в $t$. Дальше каждый шаг маршрута становится тривиальной проверкой.

---

Что дано

В Берёзовске $n$ перекрёстков, пронумерованных от $1$ до $n$, и $m$ односторонних дорог. По дорогам можно проехать из любого перекрёстка в любой другой. Поликарп живёт у перекрёстка $s$, работает у перекрёстка $t$.

Сегодня он выбрал маршрут $p_1, p_2, \ldots, p_k$, где $p_1 = s$, $p_k = t$, а каждое $p_{i+1}$ — соседний с $p_i$ по дороге $p_i \to p_{i+1}$.

Когда Поликарп выезжает с какого-то перекрёстка $u$, навигатор показывает какой-нибудь кратчайший путь из $u$ в $t$ (если их несколько, выбирается любой — система не подсказывает, какой именно). Если Поликарп едет по тому ребру, которое навигатор показал — путь не пересчитывается. Если едет в другую сторону — навигатор пересчитывает кратчайший путь от новой вершины.

Найти минимальное и максимальное возможное число пересчётов.

Ограничения

• $2 \le n \le 2 \cdot 10^5$
• $1 \le m \le 2 \cdot 10^5$
• $2 \le k \le n$
• Между двумя вершинами не больше одной дороги в каждом направлении.
• Из любой вершины достижима любая другая.

Формат ввода

n m
u_1 v_1
…
u_m v_m
k
p_1 p_2 … p_k

Формат вывода

Два целых числа через пробел: минимальное и максимальное количество пересчётов.

Пример

Вход:

6 9
1 5
5 4
1 2
2 3
3 4
4 1
2 6
6 4
4 2
4
1 2 3 4

Выход:

1 2

Разберём пример руками

Список рёбер: $1 \to 5$, $5 \to 4$, $1 \to 2$, $2 \to 3$, $3 \to 4$, $4 \to 1$, $2 \to 6$, $6 \to 4$, $4 \to 2$. Цель — $t = 4$. Маршрут — $1 \to 2 \to 3 \to 4$.

Вычислим dist[v] — кратчайшее расстояние из $v$ в $t = 4$:

• $\text{dist}[4] = 0$ (мы уже в $t$).
• $\text{dist}[5] = 1$ (есть дорога $5 \to 4$).
• $\text{dist}[3] = 1$ (есть дорога $3 \to 4$).
• $\text{dist}[6] = 1$ (есть дорога $6 \to 4$).
• $\text{dist}[1] = 2$ (через $1 \to 5 \to 4$ за два шага).
• $\text{dist}[2] = 2$ (через $2 \to 3 \to 4$ или $2 \to 6 \to 4$).

Теперь анализируем шаги маршрута.

Шаг 1: $1 \to 2$. $\text{dist}[1] = 2$, ожидаем шаг в вершину с dist = 1. Среди соседей $1$ (исходящих рёбер): $5$ ($\text{dist}=1$), $2$ ($\text{dist}=2$). Только $5$ — оптимальный. Пользователь идёт в $2$, что не оптимально. Навигатор пересчитывает гарантированно — это forced rebuild: min_rb++, max_rb++.

Шаг 2: $2 \to 3$. $\text{dist}[2] = 2$, ожидаем шаг в dist = 1. Соседи $2$: $3$ ($\text{dist}=1$), $6$ ($\text{dist}=1$). Два оптимальных соседа. Пользователь идёт в $3$ — это оптимально. Но навигатор мог показать $6$, и тогда после фактического выбора $3$ пришлось бы пересчитать. То есть пересчёт возможен, но не гарантирован: max_rb++ (в пессимистическом сценарии), min_rb остаётся (в оптимистическом — навигатор «угадал» $3$).

Шаг 3: $3 \to 4$. $\text{dist}[3] = 1$, ожидаем шаг в dist = 0. Соседи $3$: только $4$. Один оптимальный сосед, пользователь идёт ровно в него — пересчёт исключён. Ни min_rb, ни max_rb не меняются.

Итог: $\text{min\_rb} = 1$, $\text{max\_rb} = 2$. Совпадает с ответом «1 2». ✓

Из этого ручного прогона видно, что на шаге $u \to w$ нужно знать только две вещи — dist[u], dist[w] и количество соседей $x$ вершины $u$ с dist[x] = dist[u] - 1. Эту информацию даёт ровно одно BFS по обратному графу.

---

Идея решения

Алгоритм в одну фразу.

Построить обратный граф $G^R$, запустить BFS из $t$ — получить dist[v] для всех $v$. Затем пройти по маршруту и для каждой пары $(u, w) = (p_i, p_{i+1})$ определить тип шага: «forced rebuild» / «optional rebuild» / «no rebuild».

Почему обратный граф

В исходном графе мы хотим знать «сколько шагов от $v$ до $t$». BFS даёт расстояния от стартовой вершины ко всем остальным. Но запускать BFS из каждого $v$ — это $O(n \cdot (n + m))$, не уложится.

Хитрость стандартная: развернём все рёбра. В графе $G^R$ путь $v \to \ldots \to t$ длины $d$ в $G$ становится путём $t \to \ldots \to v$ длины $d$ в $G^R$. Поэтому BFS из $t$ в $G^R$ даёт dist[v] = длина кратчайшего пути из $v$ в $t$ в исходном графе.

Это работает, потому что на BFS ребро — единичной стоимости, и направление хода роли не играет. Для Дейкстры с весами трюк тот же.

Почему классификация шагов корректна

Рассмотрим шаг $u \to w$ в маршруте.

• Если $\text{dist}[w] \ne \text{dist}[u] - 1$. Шаг не лежит на кратчайшем пути из $u$ в $t$. Какой бы оптимальный путь навигатор ни предложил, его «следующий шаг» — вершина с dist = dist[u] - 1, не $w$. Значит после фактического хода в $w$ навигатор пересчитывает. Это forced: оба счётчика +1.
• Если $\text{dist}[w] = \text{dist}[u] - 1$, и среди соседей $u$ ровно одна вершина с dist = dist[u] - 1. Этот сосед — $w$. Навигатор показывает ровно $w$ как следующий шаг, пользователь туда и едет — пересчёта нет ни в каком сценарии.
• Если $\text{dist}[w] = \text{dist}[u] - 1$, и среди соседей $u$ есть другая вершина $w'$ с dist = dist[u] - 1, $w' \ne w$. Навигатор показывает один из оптимальных шагов; это либо $w$ (повезло, пересчёта нет), либо $w' \ne w$ (после фактического хода в $w$ пересчёт). Пересчёт опционален: min не растёт (повезло), max растёт (не повезло).

Этим анализ исчерпывается. Каждый шаг попадает ровно в один из трёх случаев.

Сложность

• BFS по графу с $n$ вершинами и $m$ рёбрами: $O(n + m)$.
• Проход по маршруту — $K - 1$ шагов, на каждом счётчик соседей $u$. Если хранить только cnt[u] = «сколько соседей $u$ с dist = dist[u] - 1», заранее посчитанный за $O(m)$, шаг — $O(1)$. Итого $O(n + m + K)$.

Альтернативно — на каждом шаге можно посчитать cnt[u] лениво, но запас не нужен: одна предобработка cnt чище и быстрее.

---

Решение: псевдокод

прочитать n, m
построить adj_rev[]  # обратный граф: для u → v добавляем v → u в adj_rev
прочитать k и маршрут p[1..k]

t ← p[k]
dist[1..n] ← бесконечность; dist[t] ← 0
очередь BFS ← {t}
пока очередь не пуста:
    u ← очередь.pop_front()
    для каждой v ∈ adj_rev[u]:
        если dist[v] = бесконечность:
            dist[v] ← dist[u] + 1
            очередь.push_back(v)

# Подсчёт оптимальных соседей в исходном графе (а не обратном)
cnt[1..n] ← 0
для каждого ребра u → v исходного графа:
    если dist[v] = dist[u] - 1:
        cnt[u] += 1

min_rb ← 0
max_rb ← 0
для i от 1 до k - 1:
    u ← p[i]
    w ← p[i+1]
    если dist[w] ≠ dist[u] - 1:
        min_rb += 1
        max_rb += 1
    иначе если cnt[u] >= 2:
        max_rb += 1
вывести min_rb, max_rb

Сложность: $O(n + m + k)$ по времени и памяти.

---

Код решения

Комментарии по реализации.

• Очередь BFS. В Python — deque из collections обязателен: popleft() за $O(1)$ против $O(n)$ у list.pop(0), на $n = 2 \cdot 10^5$ разница катастрофическая. В C++ — queue<int> из STL.
• Маркер «не достигнуто». INF = -1 для непосещённых вершин — работает в любых арифметических операциях, не нужно сравнивать с float('inf') или INT_MAX. Граф связный по условию, после BFS все dist[v] >= 0.
• Тип данных. int достаточно: расстояния не превышают $n \le 2 \cdot 10^5$, счётчики тоже.
• Память. Два массива смежности (fwd и rev) — $O(n + m)$, для $n + m = 4 \cdot 10^5$ это $\sim 8$ Мб, проходит с запасом.
• Быстрый ввод. Python — sys.stdin.buffer.read().split(), единое чтение всего ввода (на $m \le 2 \cdot 10^5$ обычный input() в цикле медленнее в $\sim 5$ раз). C++ — ios::sync_with_stdio(false); cin.tie(nullptr); обязательно.
• Внимание: cnt[u] считается по исходным рёбрам $u \to v$, не по обратным. Легко перепутать.

---

Проверим на примере из условия

Вход:

6 9
1 5
5 4
1 2
2 3
3 4
4 1
2 6
6 4
4 2
4
1 2 3 4

BFS из $t = 4$ по обратному графу. Обратные рёбра (из $v$ в $u$ для исходного $u \to v$):

• $5 \to 1$ (из $1 \to 5$)
• $4 \to 5$ (из $5 \to 4$)
• $2 \to 1$ (из $1 \to 2$)
• $3 \to 2$ (из $2 \to 3$)
• $4 \to 3$ (из $3 \to 4$)
• $1 \to 4$ (из $4 \to 1$)
• $6 \to 2$ (из $2 \to 6$)
• $4 \to 6$ (из $6 \to 4$)
• $2 \to 4$ (из $4 \to 2$)

BFS:

• Слой 0: $\{4\}$. dist[4] = 0.
• Соседи $4$ в обратном графе: $5$ (через $4 \to 5$), $3$ (через $4 \to 3$), $6$ (через $4 \to 6$).
• Слой 1: $\{5, 3, 6\}$. dist[5] = dist[3] = dist[6] = 1.
• Соседи $5$: $1$. Соседи $3$: $2$. Соседи $6$: $2$ (уже в слое 2 будет).
• Слой 2: $\{1, 2\}$. dist[1] = dist[2] = 2.

Итого: dist = [_, 2, 2, 1, 0, 1, 1] (индекс с 1).

Подсчёт cnt[u] (соседи $u$ в исходном графе с dist = dist[u] - 1):

• $u = 1$, dist[1] = 2, target = 1. Соседи $1$: $5$ (dist=1 ✓), $2$ (dist=2 ✗). cnt[1] = 1.
• $u = 2$, dist[2] = 2, target = 1. Соседи $2$: $3$ (dist=1 ✓), $6$ (dist=1 ✓). cnt[2] = 2.
• $u = 3$, dist[3] = 1, target = 0. Соседи $3$: $4$ (dist=0 ✓). cnt[3] = 1.
• $u = 4$, dist[4] = 0 — пропускаем (уже в $t$).
• $u = 5$, dist[5] = 1, target = 0. Соседи $5$: $4$ (dist=0 ✓). cnt[5] = 1.
• $u = 6$, dist[6] = 1, target = 0. Соседи $6$: $4$ (dist=0 ✓). cnt[6] = 1.

Проход по маршруту $1 \to 2 \to 3 \to 4$.

Итог: $\text{min\_rb} = 1$, $\text{max\_rb} = 2$. Ответ: 1 2 ✓.

---

Крайние случаи

1. Маршрут длины 2 ($k = 2$)

Только один шаг $s \to t$. Соседи $s$ — все вершины $v$ с ребром $s \to v$. Если ребро $s \to t$ существует и других соседей с dist = dist[s] - 1 нет — пересчётов 0. Если есть несколько оптимумов — max_rb = 1, min_rb = 0. Если $s \to t$ не на кратчайшем пути (теоретически возможно: $s$ → $t$ напрямую, но кратчайший — через цепочку) — forced rebuild, min_rb = max_rb = 1. Код обрабатывает корректно.

2. $u$ — вершина с dist[u] = 1, и $w = t$

dist[u] = 1, target = 0. Соседи $u$ с dist = 0 — это в точности соседи $u$, ведущие в $t$ (поскольку dist[t] = 0 и она единственная). Если есть только $t$ — cnt[u] = 1, повезло. Если $u$ имеет несколько рёбер, ведущих в вершины с dist = 0, — это может произойти только если в графе несколько копий $t$, что невозможно (вершины уникальны). Значит из вершины $u$ с dist[u] = 1 единственный оптимальный сосед — $t$.

Замечание: формально может быть, что у $u$ есть несколько рёбер в одну и ту же вершину (мульти-граф), но условие задачи запрещает это. Поэтому шаг в $t$ из вершины с dist = 1 всегда «no rebuild».

3. Граница массива

Маршрут гарантированно валиден ($p_i \to p_{i+1}$ — реальное ребро), поэтому dist[w] всегда определена и конечна. Проверка dist[u] == 0 (в $t$) на середине маршрута невозможна, так как $p_k = t$ и других $t$ в маршруте быть не должно (маршрут — обычно простой, но даже если не простой, проблема не возникает: попадаем в $t$, дальше идём, формально допустимо, но обычно не случается).

4. Память

Для $n + m = 4 \cdot 10^5$ суммарно три массива смежности (fwd, rev_g с дублированием рёбер) и dist, cnt, path размера $O(n)$. Общий расход — $O(n + m)$, памяти хватает.

---

Типичные ошибки

1. Запустить BFS из $s$ вместо $t$. Тогда получим dist_from_s[v] = расстояние от $s$ до $v$. Это не то: нам нужно расстояние от каждого $v$ до $t$, а не от $s$. Симптом: на «лёгких» примерах ответ кажется правильным (если $s \to t$ — единственный кратчайший путь), но на деревообразных графах ломается.
2. Забыть развернуть рёбра. Если запустить BFS из $t$ по исходному графу, получим расстояние от $t$ до $v$. На направленном графе это совсем другая величина: рёбра идут не туда, и dist[v] = $\infty$ для большинства $v$ (поскольку из $t$ обычно никуда не уйти, либо уйти не в $s$).
3. Перепутать cnt с количеством рёбер из $u$ вообще. cnt[u] — только количество оптимальных соседей, то есть тех с dist = dist[u] - 1. Соседей у $u$ может быть много, но не все они на кратчайшем пути.
4. Поставить > вместо >= в условии cnt[u] >= 2. Если оптимальный сосед один и это $w$ — пересчёта нет ни в каком сценарии. Если их два или больше — есть шанс пересчитать. cnt[u] >= 2, не > 2.
5. Учесть пересчёт на шаг $u \to w$, где dist[w] = dist[u] - 1 и cnt[u] = 1. Опасная мысль: «может, навигатор показал что-то ещё». Нет: если cnt[u] = 1 и dist[w] = dist[u] - 1, единственный оптимальный сосед $u$ — это $w$. Навигатор обязан показать ровно $w$.
6. Использовать list.pop(0) вместо deque.popleft() в Python. Стандартный list не поддерживает $O(1)$ удаление с начала, и BFS на $n = 2 \cdot 10^5$ улетает в TL. from collections import deque — обязательная привычка для BFS-задач.
7. Объявить dist как int-массив инициализацией всеми нулями вместо «бесконечности». Тогда вершина $t$ и непосещённые вершины не отличаются. На связном графе по условию все dist[v] определены, но в более общем случае — критическая ошибка. Привычка ставить «маркер не посещения» (-1 или INT_MAX) полезная.

---

Анализ сложности

• BFS: $O(n + m)$ по времени, $O(n + m)$ по памяти.
• Подсчёт cnt: $O(m)$, проход по всем рёбрам.
• Проход по маршруту: $O(k)$.
• Итог: $O(n + m + k)$ по времени, $O(n + m)$ по памяти.

При $n, m, k \le 2 \cdot 10^5$ — это $\le 6 \cdot 10^5$ операций. На Python — около $0.3$–$0.5$ секунды, на C++ — десятки миллисекунд.

---

Что ещё полезно потренировать

Задачи на одно BFS как предобработка для множественных запросов. Все — с возраст-нейтральных платформ.

• Multi-source BFS / shortest paths from $K$ sources. Запустить BFS из всех $K$ выделенных вершин одновременно, получив dist[v] = расстояние до ближайшей выделенной. Стандартный приём для задач типа «лесные пожары» / «пожарные машины» / «больницы и пациенты».
• 0-1 BFS (deque-BFS) — обобщение BFS на графы с весами рёбер $\{0, 1\}$. То же $O(n + m)$, но deque с appendleft() для рёбер веса 0 и append() для рёбер веса 1. Полезно на задачах с «бесплатными» переходами (телепорты, повторное использование рельсов).
• Reverse BFS / DFS на DAG для подсчёта числа кратчайших путей. Аналог нашего подхода, но вместо «сколько оптимальных соседей у $u$» — «сколько кратчайших путей через $u$». Ответ — произведение по слоям.
• Codeforces Div.2 D с тегом bfs + shortest paths — десятки задач 1700–2100, где основная трудность — придумать что брать за состояние в BFS. Тренировка на 5–10 таких задачах быстро ставит автоматизм.

Следующий шаг — задачи, где BFS нужно расширить до состояний с дополнительными параметрами (например, BFS на пересечении графа и маленького конечного автомата). Это уже полоса 2100+ и стандартный мост от «чистого BFS» к графовому DP.

---

Итого

• Идея: BFS из $t$ по обратному графу даёт dist[v] = расстояние от $v$ до $t$ в исходном графе.
• Анализ маршрута: для каждого шага $u \to w$ сверяем dist[w] с dist[u] - 1. Если не совпали — forced rebuild. Если совпали и оптимальных соседей у $u$ не один — optional rebuild.
• Сложность: $O(n + m + k)$.
• Главная ошибка: забыть развернуть рёбра или запустить BFS не из той вершины. Сигнал — dist[v] получается «не туда».
• Универсальный приём: одна предобработка $O(n + m)$, далее $K$ запросов по $O(1)$ каждый. Применимо везде, где «много вопросов про кратчайшие пути на одном графе».