Problem 5: Running MoM

https://open.kattis.com/problems/runningmom

In this problem, you want to find cities for which, upon landing in that city, there is at least one infinitely long sequence of cities that you could take. This is only the case when there is a cycle. Thus, you want to look for cycles!

So, if the city it asks for is contained in one of these cycles, it is "safe", otherwise, you are "trapped".

How do I find cycles in a directed graph?

To do this in a directed graph in O(V+E) (linear) time, we could make use of the following key insight:

If a node is in a cycle, it is it's own descendent.

This is almost trivally true: by definition of being in a cycle, if you follow the arrows far enough, you must eventually get back to the point you started at. We can use this idea to our advantage if we can figure out how to tell when a node is it's own descendent.

DFS is a stack-based algorithm, so we can think of there being 3 states for any node: hasn't been placed on stack yet (not explored), on stack (being explored), and has been popped off stack (exploring complete). Using this schema, we can determine that a node is it's own descendent if we come across it again while it is still being explored! Thus, to find a cycle all you need to do is keep track of what nodes are in which state - unexplored, being explored, done being explored - and note when you come across a node in the second state!

Of course, this problem also requires that we know exactly which nodes are in a cycle. To do that, keep track of each node's parent node so that you can backtrack when find a node that's part of a cycle.

Implementation:

Perform DFS, keeping track of parents and whether or not a node is unexplored, being explored, or is done being explored. If at any point you reach a node that is currently being explored, you have found a cycle! Using your parent nodes, you can backtrack, and save which nodes are in the cycle. These nodes are “safe”.

Dealing with Input:

The other difficult part of this problem to consider how to work with the input. One effective and straightforward way is to simply map the strings to values, and then perform the algorithms on data structures containing integers, as one normally would.