An import cycle
The Go compiler refuses to build a program if packages import each other in a loop, and prints import cycle not allowed together with the loop itself. You are writing the same check for a JavaScript project: given a list of imports, find any cycle, a chain of modules where each imports the next and the last imports the first again.
One of the tests is all 2929 imports between the 1260 JavaScript modules of this site.
Input
The first line holds the number m of imports (1 ≤ m ≤ 100,000). Then m lines of the form a b: module a imports module b. Module names are strings of up to 60 characters without spaces; there are at most 100,000 modules. A module can import itself, and the same line can repeat.
Output
If there are no cycles, print NO. Otherwise print YES on the first line and the cycle on the second: k + 1 names separated by spaces, where the first equals the last and each module imports the one after it (1 ≤ k; a module importing itself is the cycle a a). Any cycle will do.
Examples
Example 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
Example 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
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 10 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
A traversal that remembers only “been there or not” will say “cycle” on the second sample, which has no cycle. What in that sample misleads it?
2Hint 2
A vertex you have come to a second time may already be fully dealt with: two paths simply lead to it. Or it may still be “open”: you are inside it now, deeper in the recursion. Which of the cases means a cycle?
3The idea
Depth-first search with three colours: white, the module has not been seen; grey, entered and not yet left (it is on the stack); black, left. There is a cycle if and only if the search finds an import into a grey module. The grey modules are exactly the stack, so the cycle itself is the piece of the stack from that module to the current one plus the edge found.
4Walkthrough
Give the modules numbers in order of appearance and build the lists of imports. Run depth-first search from each still white module. To avoid hitting the recursion depth on a chain of a hundred thousand modules, keep a stack of one's own of pairs “module, iterator over its imports”: take the next neighbour of the top module, and when the neighbours run out, colour the module black and pop it.
On meeting a grey neighbour v, print the stack from v to the top and v once more. Why this edge means a cycle: the grey v lies on the stack below the current module u, so u was reached from v along imports, and the edge u → v closes the loop. Why without a grey neighbour there is no cycle: if there is a cycle, take the module in it that the search entered first. At the moment of entry all the other modules of the cycle are white, and by the white-path lemma each of them becomes its descendant; when the search reaches the last module of the cycle, the edge back to the first leads into a grey module.
A self-import a a is caught by the same rule: a is grey when we look at its own edge.
4+Solution
5Complexity
Each module enters the stack once, each import is looked at once: O(n + m). The dictionary of names adds O(m) expected time.
6Common mistakes
- “Been there, so it is a cycle.” A diamond, two modules importing the same third one, is taken for a cycle. This is
wrong.py, and the second sample already catches it; in this site's code there are more than two thousand such false alarms, while there is one real cycle. - Recursion without headroom. In the test with a chain of a hundred thousand modules, recursive search in Python crashes with
RecursionErrorat the standard limit of a thousand calls. A stack of one's own orsys.setrecursionlimithelps. - An unfinished cycle. The first module must be printed again at the end, otherwise the loop is not closed.
- Searching from one module only. A cycle can live in a part of the project that cannot be reached from the first module: the search must be started from every white module.