Problem AY
Import Spaghetti
As you sit down and think, you decide that the first thing to do is to eliminate the cycles in the dependency graph. So you start by finding a shortest dependency cycle.
Input
The first line of input contains a number $n$, $1 \le n \le 500$, the number of files. Then follows one line with $n$ distinct names of files. Each name is a string with at least $1$ and at most $8$ lower case letters ‘a’ to ‘z’. Then follow $n$ sections, one section per file name, in the order they were given on the second line. Each section starts with one line containing the name of the file and an integer $k$, followed by $k$ lines, each starting with “import”.
Each “import” line is a comma-space separated line of dependencies. No file imports the same file more than once, and every file imported is listed in the second line of the input. Comma-space separated means that every line will start with “import”, then have a list of file names separated by “, ” (see sample inputs for examples). Each import statement is followed by at least one file name.
Output
If the code base has no cyclic dependencies, output “SHIP IT”. Otherwise, output a line containing the names of files in a shortest cycle, in the order of the cycle (i.e., the $i$th file listed must import the $(i+1)$st file listed, and the last file listed must import the first). If there are many shortest cycles, any one will be accepted.
Sample Input 1 | Sample Output 1 |
---|---|
4 a b c d a 1 import d, b, c b 2 import d import c c 1 import c d 0 |
c |
Sample Input 2 | Sample Output 2 |
---|---|
5 classa classb myfilec execd libe classa 2 import classb import myfilec, libe classb 1 import execd myfilec 1 import libe execd 1 import libe libe 0 |
SHIP IT |
Sample Input 3 | Sample Output 3 |
---|---|
5 classa classb myfilec execd libe classa 2 import classb import myfilec, libe classb 1 import execd myfilec 1 import libe execd 1 import libe, classa libe 0 |
classa classb execd |