# Length of largest cycle

• Problem statement: 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 following :

The length of the largest cycle in the maze. Return -1 if there are no cycles.

Note: Aim for O(N) solution.

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.

• Hi,

I don't the get the question completely. What you mean by length... is it the perimeter?

The perimeter should be 2pir. Where r can be found from the diameter and the diameter will have the relationship with the maze dimensions.

• You have to find length of largest cycle in directed graph.Can you help

• Is this a real interview question with google other than ACM question? If this is an ACM question, please don't post here.

• @daiyl0320 yes its a real interview question asked to one of my friend in google.

• Actually the graph is not a general directed graph, but a functional graph. This changes the problem completely, because in the first case there is no polynomial solution (otherwise you could identify if the graph admits a Hamiltonian cycle in polynomial time).

You can run a DFS, and every time you identify a back edge check the size of the cycle it closes. You have O(N) time and memory. Was there any memory constraint specified?

• Instead of DFS, I use the idea of slow-fast node searching when we do in linkedlist. Hope the answer helps.

``````public int findLengthOfLargestCycle(int n, int[] cells){
int m = cells.length;
if(m != n) return 0;
int max = Integer.MIN_VALUE;
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
// slow fast node visiting
for(int i = 0; i < n; i ++){
if(map.containsKey(cells[i])) continue;
int slow = i, fast = i;
while(fast != -1 && cells[fast] != -1){
slow = cells[slow];
fast = cells[cells[fast]];
if(slow == fast) break;
if(slow == -1 || fast == -1) break;
if(map.containsKey(slow) || map.containsKey(fast)) break;
}
if(slow == -1 || fast == -1) continue;
if(map.containsKey(slow) || map.containsKey(fast)) continue;
slow = i;
int len = 0;
while(slow != fast){
slow = cells[slow];
len ++;
}
map.put(i, len);
max = Math.max(max, len);
}
return max == Integer.MAX_VALUE ? -1 : max;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.