Ctrl K

Уязвимые кабели сети

Сложная
В дата-центре count серверов с номерами от 0 до count - 1. Кабель cables[i] = [a, b] напрямую соединяет серверы a и b, данные по нему идут в обе стороны. Сейчас любой сервер может достучаться до любого другого — напрямую или через цепочку серверов. Кабель называется уязвимым, если после его обрыва найдутся два сервера, которые больше не могут связаться друг с другом. Верните все уязвимые кабели в виде пар [a, b]. Порядок пар в ответе и порядок серверов внутри пары не важны.
Пример 1
count=5, cables=[[0, 1], [1, 2], [2, 0], [2, 3], [3, 4]] → [[3, 4], [2, 3]]

Серверы 0, 1, 2 соединены кольцом — любой кабель кольца можно потерять. А без [2, 3] или [3, 4] серверы 3 и 4 отрезаны. Пары можно вернуть в любом порядке, например [[3, 4], [2, 3]].

Пример 2
count=4, cables=[[0, 1], [1, 2], [2, 3], [3, 0]] → []

Все четыре сервера стоят в кольце: при обрыве любого кабеля сеть остаётся связной.

Пример 3
count=3, cables=[[1, 0], [1, 2]] → [[1, 2], [0, 1]]
Ограничения
  • 2 ≤ count ≤ 10⁵
  • count − 1 ≤ len(cables) ≤ 10⁵
  • 0 ≤ a, b < count, a ≠ b
  • Любые два сервера соединены не более чем одним кабелем
  • Сеть связна
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиПорядок букв по словарю СложнаяСамый длинный подъём по карте СложнаяМаршрут по всем посадочным СложнаяШарик и лунка СложнаяЛишняя связь в дереве с корнем Сложная
загружаем Python…
Вход
count=5, cables=[[0, 1], [1, 2], [2, 0], [2, 3], [3, 4]]
Ожидается
[[3, 4], [2, 3]]

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 62 теста на сервере, включая скрытые.