Ctrl K

Новость по цепочке звонков

Сложная
В компании people человек с номерами от 0 до people - 1. Человек 0 узнал новость и в момент времени 0 рассказал её человеку first_friend. Дальше люди созваниваются: calls[i] = [x, y, t] значит, что x и y разговаривают в момент t. Если на момент разговора хоть один из двоих знает новость, после разговора её знают оба. Один человек может участвовать в нескольких разговорах в один и тот же момент. Новость распространяется мгновенно: узнав её в момент t, человек успевает передать её дальше в других разговорах того же момента t. Верните номера всех, кто знает новость после всех разговоров, в любом порядке.
Пример 1
people=5, calls=[[1, 4, 3], [2, 3, 1], [4, 2, 6]], first_friend=1 → [0, 1, 2, 4]

Сначала новость знают 0 и 1. В момент 1 звонят 2 и 3 — оба не в курсе. В момент 3 человек 1 рассказывает 4, в момент 6 человек 4 рассказывает 2. Человек 3 говорил с 2 раньше, чем тот узнал, поэтому остаётся в неведении.

Пример 2
people=4, calls=[[2, 3, 5], [0, 2, 5]], first_friend=1 → [0, 1, 2, 3]

Оба разговора идут в момент 5. Человек 0 рассказывает 2, и тот в тот же момент успевает передать новость 3.

Пример 3
people=3, calls=[[1, 2, 2]], first_friend=2 → [0, 1, 2]
Ограничения
  • 2 ≤ people ≤ 10⁵
  • 1 ≤ len(calls) ≤ 10⁵
  • calls[i] = [x, y, t], 0 ≤ x, y ≤ people - 1, x ≠ y
  • 1 ≤ t ≤ 10⁵
  • 1 ≤ first_friend ≤ people - 1
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиЛишняя связь в дереве с корнем СложнаяПартнёры рядом СложнаяКого вылечить первым СложнаяКого отключить от сети СложнаяРасстояния до кольцевой Сложная
загружаем Python…
Вход
people=5, calls=[[1, 4, 3], [2, 3, 1], [4, 2, 6]], first_friend=1
Ожидается
[0, 1, 2, 4]

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