Specification of Topological sort with Python

Your program must take a list of dependent tasks and either output a valid order in which to perform them or the single word cycle.

Your program will accept a number of lines of textual input (via standard input). There are no command line arguments you must always read from standard input. Do not open a named file. Instead, always read from standard input.

The text input will contain a non-zero but even number of lines. Every two lines represent a pair of tasks. The first line gives the name of the task, the second line gives the name of the task that it depends on. This text input is also called the task list.

The task list will contain only standard ASCII characters (no UTF-8 Unicode or special accents). The goal is to rest programming and program language concepts, not your internationalization abilities.

Each task name starts at the beginning of the line and extends all the way up to (but not including) the end of that line. So, the newline or carriage return characters or are not part of the task list name.

Example task list:

learn OCaml read the OCaml tutorial do assignment 1 learn OCaml

The interpretation is that in order to learn OCaml one must first read the OCaml tutorial and that in order to do assignment 1 one must first learn OCaml. Desired output for this example:

read the OCaml tutorial learn OCaml do assignment 1

If the task list contains a cycle of any size, then your program should output exactly and only the word cycle. Example cyclic input:

get a job have experience have experience work on a job work on a job get a job

Even if the task list contains a few non-cyclic parts, any single cycle forces you to output only the word cycle.

Always output to standard output only. Do not write anything to standard error.

There is no fixed limit on the number of lines in the task list (although it is not zero and it is even).

Two tasks with the same name are really just the same task. Use standard string equality.

Duplicated pairs of tasks are not allowed. For example:

learn OCaml read the OCaml tutorial do assignment 1 learn OCaml learn OCaml read the OCaml tutorial

is not valid input because the pair learn OCaml/read the OCaml tutorial appears twice. Program behavior if the task contains duplicate pair is undefined. You will not be tested on it.

Your program may not cause any other file I/O to be performed, such as creating a temporary file to keep track of some intermediate sorting results or writing to standard error (or even causing the interpreter to write a warning to standard error). You do not need any such temporary files or standard error printing to solve this problem.

If there are multiple outstanding unconstrained tasks, then your program should output them in ascending ASCII alphabetical order. That is, if you ever have two or more tasks, each of which has no remaining dependencies, then output the one that comes firs ASCII-alphabetically. (This constraint makes your program deterministic; for any given input there is only one correct output.) Example:

learn OCaml understand higher-order functions learn OCaml read the OCaml tutorial do assignment 1 learn OCaml

Because r comes before u, your output should be:

read the OCaml tutorial understand higher-order functions learn OCaml do assignment 1

To put it another way, consider this task list:

B A C D C E

Which yields a dependency graph like this:

A D E | \ / B C

The proper ordering for this set of tasks is A B D E C. Note that B comes before D and E, even though B depends on A. This is because, once A is finished, B is free to go and it comes first alphabetically. You may want to consider this requirement when you pick your sorting algorithm. Given this requirement the answer A D E B C is incorrect and will receive no credit.

This problem is just topological sort not-so-cleverly disguised.

For exercise 1 you must turn in a python file

You must also submit these files:

1.) testcase.list - a valid task list that you made up