Length of largest cycle


  • 0
    A

    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.


  • 0
    R

    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.


  • 0
    A

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


  • 0
    D

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


  • 0
    A

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


  • 0
    C

    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?


  • 0
    A

    @csacademy.com no other constraint.


  • 0

    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;
    }
    

Log in to reply
 

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