THINK FIRST·CODE LATER

← All labs

Find dependency cycles

Problem

Dependency cycles make modules impossible to change independently. Find one.

Input: lines from to until the end of input (module from depends on to). Modules are words.

Search for a cycle with a depth-first search: visit modules in order of first appearance in the input, and each module's dependencies in input order. When the search reaches a module that is already on the current path, a cycle is found: print it starting and ending at that module, e.g. Cycle: board -> post -> board, and stop.

If there is no cycle print No cycles followed by a topological order — the modules in an order where every module comes after all the modules it depends on — produced by the same DFS (a module is added when all its dependencies are finished), as Build order: a, b, c.

Input:

web board
board post
post repo
repo board

Output:

Cycle: board -> post -> repo -> board

Data for this lab

Your program reads its data from standard input. Download the file, then give it to your program as shown below. Start with data set 1: its expected output is given.

s6-2-data-1.txt

web board
board post
post repo
repo board
What your program must print for s6-2-data-1.txt
Cycle: board -> post -> repo -> board

Run your program first, then open this and compare line by line: your output must contain these lines exactly.

How to give the file to my program

Terminal (macOS, Linux, or Windows Command Prompt), after compiling:

java Main < s6-2-data-1.txt

Windows PowerShell does not understand <:

Get-Content s6-2-data-1.txt | java Main

IntelliJ IDEA: Run → Edit Configurations → Redirect input from. Or simply paste the content of the file into the console when the program waits for input.

Write it here or in your IDE, then paste it. Compile and test it yourself before comparing. Your code stays in your browser — it is never sent to or stored on the server.