Last Updated: 2 Apr, 2021
Largest Cycle
Easy
Asked in companies
You are given a maze consisting of N cells numbered from 0 to N - 1 and an array ‘arr’ of N integers in which arr[i] contains the cell number that can be reached from ‘i’th cell in one step. You are supposed to find the length of the largest cycle in the maze, given that each cell has less than or equal to 1 exit but can have multiple entry points.
Note:
The maze may contain self-cycles.
arr[i] = -1 means the ‘i’th cell doesn’t have an exit.
Input Format:
The first line of input contains an integer ‘T’, denoting the number of test cases. The test cases follow.
The first line of each test case contains integer ‘N’, which denotes the number of cells in the maze.
The second line contains N integers, denoting the elements of the array ‘arr’.
Output Format:
For each test case, print the length of the largest cycle in the maze and -1 if there are no cycles.
Print the output of each test case in a separate line.
Constraints:
1<= T <= 50
1 <= N <= 10,000
-1 <= arr[i] <= N-1
Where ’T’ is the number of test cases, and N denotes the number of cells in the maze and arr[i] is the cell that can be reached from ‘i’th cell.
Time Limit: 1 sec
Approaches
The idea is to do a depth-first search to find all the cycles which are formed and calculate the length of the largest cycle. We are treating the array as a graph of directed edges. Whenever we get into any of the cells in the cycle, using dfs we will visit all the subsequent cells in the cycle. Out of all the cycles, we will return the cycle of maximum length.
The steps are as follows:
- Initialize a boolean array ‘visited’ of size N with 0 at all the indexes initially which denotes whether a particular cell is visited or not.
- Initialize an integer ‘res’ to 0, which denotes the largest cycle in the maze.
- Define a recursive function ‘dfs’ with arguments ‘arr’, ‘positions’, ‘currentCell’, ‘totalLengthCovered’, array ‘visited’, an integer ‘res’ which denotes the given array ‘arr’, a hash map which is used to store the order in which vertices are visited, the current cell for the recursive call, the total number of cells visited in the current recursive call, array to know whether a particular cell is visited or not, and final answer ‘res’.
- If the current cell is already visited in any of the previous recursive calls, then return from the function.
- If there is no exit from the current cell, then mark the cell as visited and return from the function.
- If the current cell is visited in the same recursive call i.e. it is present in the hash map, mark it as visited, take ‘res’ as a maximum of ‘res’ and ‘totalLengthCovered’ - positions[i].
- Insert current cell into the hash map (current cell as the key and total length covered in the current recursion as the value).
- Recursively call for the connected cell to the current cell and increment the total length covered.
- After the recursive call, mark the current cell visited in the array ‘visited’.
- Iterate from i = 0 to N-1:
- If the ith cell is not visited:
- Declare a hash map ‘positions’ that is used to store the order in which the vertices are visited.
- Call the recursive function ‘dfs’ with arguments ‘arr’, ‘positions’, ‘i’, 0, ‘visited’, ‘res’.
- If the ith cell is not visited:
- If ‘res’ is equal to 0, it means that there is no cycle, return -1.
- Otherwise, return ‘res’ as the final answer.