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

98. Порядок сборки модулей без разночтений

Сложная

Мини-приложение VK собирается из n модулей с номерами от 0 до n − 1. Зависимость [a, b] значит: модуль a собирается раньше модуля b.

Чтобы две сборки давали одинаковый лог, из всех допустимых порядков берём лексикографически минимальный: на каждом шаге — модуль с наименьшим номером среди тех, чьи зависимости уже собраны. Верните этот порядок или пустой список, если зависимости зациклены.

В работе: Сборщик фронтенда: одинаковый порядок модулей в двух сборках — одинаковый хеш бандла и тёплый кэш CDN.

Пример 1

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

0 ждёт 1, 1 ждёт 2 и 3. Сначала 2 (меньший из готовых), затем 3, 1, 0.

Пример 2

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

Цикл 0 → 1 → 2 → 0 — порядка нет.

Ограничения

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

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