Войти Регистрация
Алгоритмы

103. Счета в кольцах переводов

Сложная

За сутки по n счетам (номера от 0 до n − 1) прошли переводы transfers[i] = [a, b]: со счёта a на счёт b. Повторы бывают, перевод самому себе (между своими вкладами под одним номером) тоже.

Счёт попадает в проверку антифрода, если с него можно уйти цепочкой переводов и вернуться на него же. Верните номера таких счетов по возрастанию.

В работе: Антифрод: кольца переводов — типичный признак обнала и накрутки оборотов по счёту.

Пример 1

Ввод
n = 6
transfers = [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4], [5, 5]]
Вывод
[0, 1, 2, 5]

Кольцо 0 → 1 → 2 → 0 и петля на счёте 5. Со счетов 3 и 4 не вернуться.

Пример 2

Ввод
n = 3
transfers = [[0, 1], [1, 2]]
Вывод
[]

Цепочка без возврата.

Ограничения

  • 1 ≤ n ≤ 10⁵
  • 0 ≤ число переводов ≤ 3·10⁵
  • Лимит — 3 с на тест (3000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def ring_accounts(n, transfers):
ГрафыСильно связные компонентыКосарайюИтеративный DFSцельO(n)

Источник: наша задача на данных Т-Банка. Условие пересказано своими словами.