Задачник Базовый курс EN

Порядок выполнения модулей

обход порядок зависимостей стек рекурсия компиляторы

Страница загружает один модуль JavaScript, а он тянет за собой остальные. По спецификации ECMAScript модуль выполняется после модулей, которые он импортирует, и они выполняются в том порядке, в каком записаны его строки import. Каждый модуль выполняется один раз. Если модули импортируют друг друга по кругу, браузер не ждёт модуль, который уже начал выполнять, и идёт дальше.

Точнее, браузер поступает так. Чтобы выполнить модуль a, он помечает его как начатый, затем по порядку для каждого импорта b: если b ещё не начат, выполняет b тем же способом, а если начат — пропускает. Когда импорты кончились, выполняет код самого a. Напечатайте модули в том порядке, в каком выполнится их код. Один из тестов — модули этого сайта: что выполнит браузер, если страница загрузит движок символьной математики.

Вход

В первой строке число n — сколько модулей (1 ≤ n ≤ 100 000). Дальше n строк, по одной на модуль: имя, число k его импортов и k имён в порядке строк import в файле. Имена — строки до 60 символов без пробелов; каждый упомянутый модуль описан своей строкой; всего импортов не больше 200 000. В последней строке — имя модуля, который загружает страница.

Выход

Имена модулей, которые выполнятся, в порядке выполнения, по одному в строке.

Примеры

Пример 1

Вход

7
solve.js 6 rational.js ast.js print.js simplify.js expand.js poly.js
poly.js 4 rational.js ast.js expand.js print.js
expand.js 4 rational.js ast.js simplify.js poly.js
simplify.js 2 rational.js ast.js
print.js 2 rational.js ast.js
ast.js 1 rational.js
rational.js 0
solve.js

Выход

rational.js
ast.js
print.js
simplify.js
poly.js
expand.js
solve.js

Пример 2

Вход

5
main 3 a b a
a 1 c
b 2 c main
c 1 a
lonely 1 main
main

Выход

c
a
b
main

Ограничения

Время · Python: 4000 мс
Время · Go: 1000 мс
Память: 256 МБ
Проверка: 10 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Перечитайте правило браузера и сравните его с обходом в глубину. Когда именно выполняется код модуля: при входе в него или при выходе?

2Подсказка 2

Рекурсивное решение пишется в шесть строк. Сколько уровней рекурсии понадобится в тесте, где сто тысяч модулей выстроены в цепочку?

3Подсказка 3

Если вместо рекурсии положить в стек все импорты модуля сразу, модули достанутся не в том порядке. Что нужно хранить в стеке, чтобы он повторял рекурсию шаг в шаг?

4Идея

Правило браузера — это поиск в глубину из модуля страницы, где соседи перебираются в порядке строк import, а модуль печатается в момент выхода из него: обратный порядок обхода, post-order. «Начат» — это серый или чёрный цвет, поэтому круговой импорт к серому модулю просто пропускается, как в спецификации.

5Разбор

Рекурсия переводится на свой стек так: в стеке лежат пары «модуль, номер следующего импорта». На каждом шаге смотрим на верхнюю пару. Если импорты кончились — печатаем модуль и снимаем пару. Иначе сдвигаем номер и, если очередной импорт ещё не начат, помечаем его и кладём пару «импорт, 0». Ровно это и делает рекурсия: пара — это кадр стека вызовов с номером строки, на которой он остановился.

Почему не годится стек модулей. Цикл «достать модуль, положить все его импорты, отметить их» обходит те же модули, но импорт, который лежит в стеке давно, может быть достан позже модулей, которые его импортируют. В первом примере так expand.js выполнился бы раньше poly.js, а в движке математики этого сайта при загрузке index.js модуль simplify.js выполнился бы раньше evaluate.js, который он импортирует. Это wrong.py; в статье есть сцена, где видно все такие нарушения.

В примере с кругом c выполняется первым, хотя импортирует a, а a ещё не выполнен: браузер дошёл до c из a и не стал ждать. Поэтому при круговых импортах один из модулей обязательно видит другой недоделанным.

5+Решение

6Сложность

Каждый модуль кладётся в стек один раз, каждый импорт просматривается один раз: O(n + m), где m — число импортов. Плюс словарь имён.

7Типичные ошибки

Стек модулей вместо стека кадров. Порядок получается не тот — wrong.py, падает на первом примере.
Печать при входе. Это порядок, в котором браузер начинает модули, а не выполняет их.
Пометка только при выходе. Тогда круговой импорт уводит в бесконечную рекурсию: модуль, который уже начат, нужно пропускать сразу.
Глубина рекурсии. На цепочке из ста тысяч модулей рекурсивное решение на Python без sys.setrecursionlimit падает с RecursionError.
Сортировка импортов. Порядок строк import важен: от него зависит ответ.

Алгоритмы задачи

GRA Алгоритм Поиск в глубину Идёт вглубь, отмечает вход и выход каждой вершины и по ним находит циклы за O(V + E). O(V + E) 2 задачи