Ctrl K

Узел с самым тяжёлым входом

Средняя
Есть ориентированный граф из n узлов с номерами от 0 до n - 1. Из каждого узла выходит ровно одна стрелка: из узла i она ведёт в узел points_to[i]. Вес узла — сумма номеров всех узлов, стрелки из которых ведут в него. Если в узел не ведёт ни одна стрелка, его вес равен 0. Верните номер узла с наибольшим весом. Если таких несколько, верните наименьший номер.
Пример 1
points_to=[3, 3, 0, 1] → 1

В 3 ведут узлы 0 и 1 — вес 1. В 0 ведёт 2 — вес 2. В 1 ведёт 3 — вес 3. Больше всех у узла 1.

Пример 2
points_to=[1, 0, 1] → 1

Вес узла 1 — 0 + 2 = 2, вес узла 0 — 1. Ответ 1.

Пример 3
points_to=[3, 0, 0, 1] → 0

Вес узла 0 — 1 + 2 = 3, вес узла 1 — 3, вес узла 3 — 0. Узлы 0 и 1 делят первое место, берём меньший номер: 0.

Ограничения
  • n == len(points_to)
  • 2 ≤ n ≤ 10⁵
  • 0 ≤ points_to[i] < n
  • points_to[i] ≠ i
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиСнять фишки с общей линией СредняяВидео друзей на заданном расстоянии СредняяЧто можно приготовить СредняяОткрытые комнаты от холла СредняяРаскрыть шаблон с переменными Средняя
загружаем Python…
Вход
points_to=[3, 3, 0, 1]
Ожидается
1

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