Сеть VK — n узлов (дата-центры и точки обмена трафиком), номера от 0 до n − 1. Линк links[i] = [u, v] соединяет узлы u и v в обе стороны. Между двумя узлами бывает несколько линков: их тянут по разным трассам как резерв.
Линк критичный, если после его обрыва какие-то два узла, связанные до обрыва, теряют связь. Верните номера критичных линков по возрастанию.
В работе: План резервирования: какие оптические трассы дублировать первыми, чтобы обрыв одной не отрезал регион.
Пример 1
n = 5 links = [[0, 1], [1, 2], [2, 0], [1, 3], [3, 4]]
[3, 4]
Треугольник 0–1–2 переживёт обрыв любого линка, а линки 3 и 4 — единственный путь к узлам 3 и 4.
Пример 2
n = 2 links = [[0, 1], [0, 1]]
[]
Два линка по разным трассам: обрыв одного не страшен.
Ограничения
- 1 ≤ n ≤ 10⁵
- 0 ≤ число линков ≤ 2·10⁵
- бывают петли и кратные линки
- сеть может быть несвязной
- Лимит — 3 с на тест (3000 мс).
print() и console.log() уходят в консоль.
def critical_links(n, links):
Источник: наша задача на данных VK. Условие пересказано своими словами.
Ожидаемый ответ не нужен: покажем, что вернула функция.
Здесь появится результат отправки.