Ctrl K

Дойдёт ли сообщение

Лёгкая
В офисе n компьютеров с номерами от 0 до n - 1. Некоторые пары соединены кабелем: каждый элемент links[i] = [u, v] означает кабель между компьютерами u и v, по которому данные идут в обе стороны. Между двумя компьютерами не больше одного кабеля, и ни один кабель не соединяет компьютер сам с собой. Верните True, если сообщение может дойти от компьютера start до компьютера target, передаваясь по кабелям через любые промежуточные компьютеры, и False иначе.
Пример 1
n=5, links=[[0, 3], [3, 4], [1, 2]], start=0, target=4 → True

Сообщение идёт по цепочке 0 → 3 → 4.

Пример 2
n=5, links=[[0, 3], [3, 4], [1, 2]], start=4, target=2 → False

Компьютеры 0, 3, 4 и компьютеры 1, 2 — две отдельные группы, между ними нет ни одного кабеля.

Пример 3
n=2, links=[], start=1, target=1 → True

Начальный и целевой компьютер совпадают — путь пустой, но он есть.

Ограничения
  • 1 ≤ n ≤ 2·10⁵
  • 0 ≤ len(links) ≤ 2·10⁵
  • links[i] = [u, v], 0 ≤ u, v ≤ n - 1, u ≠ v
  • Повторяющихся кабелей нет
  • 0 ≤ start, target ≤ n - 1
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиСкладываются ли связи в дерево СредняяСколько изолированных групп в сети СредняяЦепочки отношений СредняяГруппы связанных серверов СредняяЛишний кабель Средняя
загружаем Python…
Вход
n=5, links=[[0, 3], [3, 4], [1, 2]], start=0, target=4
Ожидается
True

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