Converging maze: Largest cycle

Question

This question was asked in one interview and i am still hunting for the best solution.

You are given a maze with N cells. Each cell may have multiple entry points but not more than one exit (ie. entry/exit points are unidirectional doors like valves).

The cells are named with an integer value from 0 to N-1.

You need to find the the length of the largest cycle in the maze. Return -1 if there are no cycles.

INPUT FORMAT

• First line has the number of cells N
• Second line has list of N values of the edge[] array. edge[i] contains the cell number that can be reached from of cell ‘i’ in one step. edge[i] is -1 if the ‘i’th cell doesn’t have an exit.

OUTPUT FORMAT

• length of the largest cycle.

Sample input:

23

4 4 1 4 13 8 8 8 0 8 14 9 15 11 -1 10 15 22 22 22 22 22 21

Sample output

6

I have already tried to do this with DFS to find all possible cycles and print the largest cycle size. Please let me know if there is any better solution for the same.

Answer 1

Given a node in the graph, there's a unique maximal path starting from it (since there's at most one exit from any node). It may or may not cycle.

It's easy to find the eventual cycle length starting from a node: keep following exit nodes, recording nodes in a set along the path. Stop when you either find no exit node, or you're about to visit a previously visited node. If there's no exit node there's no cycle, and otherwise you can find the cycle length by starting at the previously visited node, and re-trace the cycle. [You could also use Floyd's algorithm here which would require O(1) rather than O(N) storage, but we're going to use O(N) storage anyway in the next step].

Using this, one can find the maximum cycle in O(N) time: repeat the above algorithm for each node in the graph, but cache results (storing -1 if there's no cycle found). You have to be careful to stop the cycle-finding above if you find a previously cached result along your path, and once you've found a result for a node, you must cache the result for all nodes along the path until you find a node who's result is already cached. The size of the largest cycle is the value of the largest cached value.

This is O(N) runtime: each edge (of which there's at most N) is followed at most 3 times in the graph, and the cache is updated exactly once for each node in the graph. It's uses O(N) additional storage.