Basic Algorithms - Spring 2018

Prompt:

The fellowship has decided upon crossing Moria for the paths in the mountains are occupied by wargs. Unfortunately Gandalf is having a hard time remembering the paths inside the great caves as it has been a long time since he has passed through here.

The fellowship is currently being pursued by hordes of orcs and needs to escape as fast as possible from the dungeons. Gandalf has given you the all important task of identifying the perils ahead. As there are too many orcs pursuing the fellowship, if you return to any room where you have previously been, it will be filled with orcs. Gandalf wants you to identify if there is a path which will lead to your doom (by making you visit some room where you already walked through) so that he may take measures to avoid it (assume the passages are one way for simplicity).