Цикл импортов
Компилятор Go отказывается собирать программу, если пакеты импортируют друг друга по кругу, и печатает import cycle not allowed вместе с самим кругом. Вы пишете такую же проверку для проекта на JavaScript: дан список импортов, найдите любой цикл — цепочку модулей, где каждый импортирует следующий, а последний снова импортирует первый.
Один из тестов — все 2929 импортов между 1260 модулями JavaScript этого сайта.
Вход
В первой строке число m — сколько импортов (1 ≤ m ≤ 100 000). Дальше m строк вида a b: модуль a импортирует модуль b. Имена модулей — строки до 60 символов без пробелов; модулей не больше 100 000. Модуль может импортировать сам себя, одна и та же строка может повторяться.
Выход
Если циклов нет, выведите NO. Иначе в первой строке YES, во второй — цикл: k + 1 имя через пробел, где первое совпадает с последним и каждый модуль импортирует следующий за ним (1 ≤ k; модуль, импортирующий сам себя, — цикл a a). Подойдёт любой цикл.
Примеры
Пример 1
19 solve.js rational.js solve.js ast.js solve.js print.js solve.js simplify.js solve.js expand.js solve.js poly.js poly.js rational.js poly.js ast.js poly.js expand.js poly.js print.js expand.js rational.js expand.js ast.js expand.js simplify.js expand.js poly.js simplify.js rational.js simplify.js ast.js print.js rational.js print.js ast.js ast.js rational.js
YES expand.js poly.js expand.js
Пример 2
18 solve.js rational.js solve.js ast.js solve.js print.js solve.js simplify.js solve.js expand.js solve.js poly.js poly.js rational.js poly.js ast.js poly.js print.js expand.js rational.js expand.js ast.js expand.js simplify.js expand.js poly.js simplify.js rational.js simplify.js ast.js print.js rational.js print.js ast.js ast.js rational.js
NO
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Обход, который помнит только «был или не был», скажет «цикл» на втором примере, где цикла нет. Что в этом примере сбивает его с толку?
2Подсказка 2
Вершина, в которую вы пришли второй раз, может быть уже полностью разобрана — до неё просто ведут два пути. А может быть ещё «открыта»: вы сейчас внутри неё, глубже по рекурсии. Какой из случаев означает цикл?
3Идея
Поиск в глубину с тремя цветами: белый — модуль не видели, серый — вошли и ещё не вышли (он на стеке), чёрный — вышли. Цикл есть тогда и только тогда, когда поиск находит импорт в серый модуль. Серые модули — это ровно стек, поэтому сам цикл — кусок стека от этого модуля до текущего плюс найденное ребро.
4Разбор
Назначаем модулям номера в порядке появления и строим списки импортов. Запускаем поиск в глубину из каждого ещё белого модуля. Чтобы не упереться в глубину рекурсии на цепочке из ста тысяч модулей, держим свой стек пар «модуль, итератор по его импортам»: берём следующего соседа верхнего модуля, а когда соседи кончились — красим модуль в чёрный и снимаем со стека.
Встретили серого соседа v — выводим стек от v до вершины и ещё раз v. Почему это ребро означает цикл: серый v лежит на стеке ниже текущего модуля u, значит, от v по импортам дошли до u, а ребро u → v замыкает круг. Почему без серого соседа цикла нет: если цикл есть, возьмём в нём модуль, в который поиск вошёл первым. В момент входа все остальные модули цикла белые, и по лемме о белом пути каждый из них станет его потомком; когда поиск дойдёт до последнего модуля цикла, ребро обратно в первый приведёт в серый модуль.
Самоимпорт a a ловится тем же правилом: a серый, когда смотрим на его собственное ребро.
4+Решение
5Сложность
Каждый модуль входит в стек один раз, каждый импорт просматривается один раз: O(n + m). Словарь имён — ещё O(m) ожидаемого времени.
6Типичные ошибки
- «Уже был — значит цикл». Ромб — два модуля импортируют один и тот же третий — будет принят за цикл. Это
wrong.py, и его ловит уже второй пример; в коде этого сайта таких ложных тревог больше двух тысяч, а настоящий цикл один. - Рекурсия без запаса. В тесте с цепочкой из ста тысяч модулей рекурсивный поиск в Python упадёт с
RecursionErrorпри стандартном пределе в тысячу вызовов. Помогает свой стек илиsys.setrecursionlimit. - Цикл не до конца. Вывести нужно и первый модуль в конце, иначе круг не замкнут.
- Поиск только из одного модуля. Цикл может жить в части проекта, до которой из первого модуля не дойти: запускать поиск нужно из каждого белого модуля.