Juspay OA 2023 - Largest Sum Cycle in a Maze

Problem Description:

You are given a maze with N cells. Each cell may have multiple entry points but not more than one exit (i.e., entry/exit points are unidirectional doors like valves). You need to find the sum of the largest sum cycle in the maze.

• Each cell is labeled with an integer from 0 to N-1.
• You are provided with an array Edge[] where Edge[i] represents the cell number that can be reached from cell i in one step. If Edge[i] is -1, that means the i-th cell doesn't have an exit.
• A cycle is a path where a node can eventually lead back to itself. The sum of a cycle is the sum of the node numbers involved in that cycle.

Note: If a node has no incoming edges, its weight is considered to be 0.

Input Format:

• The first line contains an integer N, the number of cells.
• The second line contains N integers representing the Edge[] array where Edge[i] contains the cell number that can be reached from cell i in one step. If Edge[i] is -1, it means cell i doesn't have an exit.

Output Format:

• Output the sum of the largest cycle in the maze. If no cycle is present, print -1.

Constraints:

• 1 <= N <= 10^5

Sample Input:

23
4 4 1 4 13 8 8 8 0 8 14 9 15 11 -1 10 15 22 22 22 22 22 21

Sample Output:

6

Explanation:

In this example, the graph is created from the Edge[] array. You need to find cycles in the graph and calculate the sum of the node numbers in the largest cycle.