Войти Регистрация
Алгоритмы

97. Развернуть меньше всего конвейеров

Сложная

На складе n узлов, номера от 0 до n − 1. Конвейер [u, v] везёт короба от узла u к узлу v и только в эту сторону.

Любую ленту можно перенастроить на обратный ход, это одна переналадка. Короб ставят на узел 0 (приёмка), он должен попасть на узел n − 1 (отгрузка). Верните наименьшее число переналадок или -1, если узлы не связаны даже без учёта направлений.

В работе: Перестройка потоков на сортировочном центре, когда одну линию закрыли на ремонт.

Пример 1

Ввод
n = 4
belts = [[0, 1], [2, 1], [2, 3]]
Вывод
1

Ленту 2 → 1 разворачиваем, дальше 2 → 3 по ходу — одна переналадка.

Пример 2

Ввод
n = 5
belts = [[0, 1], [1, 2], [3, 4]]
Вывод
-1

Узлы 3 и 4 не связаны с приёмкой.

Ограничения

  • 2 ≤ n ≤ 3·10⁵
  • 0 ≤ число конвейеров ≤ 10⁶
  • Лимит — 3 с на тест (3000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def min_reversals(n, belts):
Графы0-1 BFSцельO(n)

Источник: наша задача на данных Wildberries. Условие пересказано своими словами.