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

102. Хабы, без которых доставка рвётся

Сложная

Сеть Авито Доставки — n узлов (сортировочные хабы и пункты приёма), номера от 0 до n − 1. Маршрут roads[i] = [u, v] — регулярный рейс между узлами в обе стороны.

Узел слабый, если при его закрытии какие-то два других узла, связанные раньше, теряют связь. Верните номера слабых узлов по возрастанию.

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

Пример 1

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

Через узел 1 треугольник 0–1–2 связан с остальными, через 3 — треугольник 3–4–5.

Пример 2

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

В кольце любой узел можно обойти.

Ограничения

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

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