Largest Cycle in Maze Problem Statement

Given a maze represented by 'N' cells numbered from 0 to N-1, and an array arr of 'N' integers where arr[i] denotes the cell number that can be reached from the 'i'-th cell in one step, identify the length of the largest cycle in the maze.

Note that each cell may have ≤ 1 exit but can have multiple entry points. Cells may have self-cycles (a cycle of length 1). If arr[i] = -1, it means the 'i'-th cell has no exit.

Example:

Input:

T = 2
N = 5
arr = [2, -1, 0, 4, 5]
N = 6
arr = [-1, 0, 1, 2, 3, -1]

Output:

3
-1

Explanation:

In the first test case, there is a cycle 0 - 2 - 0 with length 3. In the second test case, there are no cycles.

Constraints:

1 ≤ T ≤ 50

1 ≤ N ≤ 10,000

-1 ≤ arr[i]

Question

Largest Cycle in Maze Problem Statement

Given a maze represented by 'N' cells numbered from 0 to N-1, and an array arr of 'N' integers where arr[i] denotes the cell number that can be reached from the 'i'-th cell in one step, identify the length of the largest cycle in the maze.

Note that each cell may have ≤ 1 exit but can have multiple entry points. Cells may have self-cycles (a cycle of length 1). If arr[i] = -1, it means the 'i'-th cell has no exit.

Example:

Input:

T = 2
N = 5
arr = [2, -1, 0, 4, 5]
N = 6
arr = [-1, 0, 1, 2, 3, -1]

Output:

3
-1

Explanation:

In the first test case, there is a cycle 0 -> 2 -> 0 with length 3. In the second test case, there are no cycles.

Constraints:

1 ≤ T ≤ 50
1 ≤ N ≤ 10,000
-1 ≤ arr[i] < N-1

Note:

For each test case, output the length of the largest cycle in the maze or -1 if no cycles exist. Print the output for each test case on a new line.

Accepted Answer

Identify the length of the largest cycle in a maze represented by cells and an array of integers.

Iterate through each cell and find the cycle length using DFS or Floyd's Tortoise and Hare algorithm.
Handle self-cycles and cells with no exit by checking arr[i] = i and arr[i] = -1 respectively.
Output the length of the largest cycle found or -1 if no cycles exist.