Largest Cycle

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’.

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

In the first test case, there are 5 cells in the maze. ‘i’th cell - exit cell of ‘i’th cell 0 - -1 1 - 2 2 - 3 3 - 4 4 - 1 This maze consists of 1 cycle 1 -> 2 -> 3 -> 4 -> 1 (length = 4). So, the maximum length of the cycle is 4. In the second test case, there are 10 cells in the maze. ‘i’th cell - exit cell of ‘i’th cell 0 - 2 1 - 4 2 - 0 3 - 5 4 - 6 5 - 3 6 - 7 7 - 8 8 - 9 9 - 1 This maze contains 3 cycles 0 -> 2 ->0 (length = 0), 1 -> 4 -> 6 -> 7 -> 8 ->9 -> 1 (length = 6), and 3 -> 5 -> 3 (length = 2). So, the maximum length of the cycle is 6.

DFS

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 ‘res’ is equal to 0, it means that there is no cycle, return -1.
Otherwise, return ‘res’ as the final answer.

Time Complexity

O(N), where N is the number of cells in the maze.

As the time complexity of a Depth-first Search is O(V+E), where V is the number of vertices and E is the number of edges in the graph. Here the number of vertices is N, and the number of edges is at most N. Hence the overall time complexity is O(N).

Space Complexity

O(N), where N is the number of cells in the maze.

We are using a visited array of size N and a positions array of size N. Hence, the overall space complexity is O(N).

Problem statement

Sample Input 1:

Sample Output 1:

Explanation for Sample Input 1:

Sample Input 2:

Sample Output 2: