Problem I
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 |