Largest Sum Cycle – Complete C# Tutorial with Graph Concepts and Dry Run

1. Problem Understanding

The problem gives us an array called edge[], where every index represents a node (cell) in a directed graph.

Each node can have at most one outgoing edge.

Our task is to:

• Identify all cycles in the graph.
• Calculate the sum of node indices belonging to each cycle.
• Return the maximum cycle sum.
• If there is no cycle, return -1.

Example:

Input:  edge = [1, 2, 0, -1]
Output: 3

Let's understand the array:

This represents:

0 → 1 → 2 → 0

We return to node 0, so a cycle exists.

Cycle sum:

0 + 1 + 2 = 3

Node 3 has no outgoing edge because its value is -1.

2. Understanding the Graph Concept

Before implementing the solution, let's understand what a directed graph is.

A graph contains:

• Vertices (Nodes): The individual cells.
• Edges: Connections between nodes.
• Directed edges: Connections that have a specific direction.

For example:

Directed graph

0

1

2

2 → 0 closes the cycle

The directed path returns to its starting node.

A cycle occurs when we follow the outgoing edges and eventually reach a node that is already part of the current path.

For this problem, we don't need a general graph adjacency list because each node has only one outgoing edge. The given array itself represents the graph.

3. What Algorithm Should We Use?

We can solve this problem using Graph Traversal with Visited Tracking and Path Indexing.

We maintain three important things:

1. A visited array.
2. A path index array.
3. A variable to store the maximum cycle sum.

Let's understand why each one is required.

A. Visited Array

bool[] visited = new bool[n];

This array tells us whether a node has already been visited.

For example:

visited = [true, true, true, false]

This means:

• Node 0 is visited.
• Node 1 is visited.
• Node 2 is visited.
• Node 3 is not visited.

Why do we need it?

Without visited, we might process the same nodes repeatedly, resulting in unnecessary work.

B. Path Index Array

int[] pathIndex = new int[n];

Array.Fill(pathIndex, -1);

This is the most important part of our cycle detection logic.

pathIndex[] stores the position of each node in the current traversal path.

Consider:

path = [0, 1, 2]

The corresponding path indices are:

Suppose we reach node 1 again.

Since:

pathIndex[1] = 1

We know that the cycle starts at position 1.

Therefore, the cycle is:

1 → 2 → 0 → 1

For our example, if the path were [0, 1, 2] and the next node were 0, the cycle would start at position 0.

C. Maximum Sum

int maxSum = -1;

This stores the highest cycle sum found so far.

We initialize it to -1 because the problem requires returning -1 when no cycle exists.

4. Cycle Detection – Understanding the Main Logic

This is the most important code:

while (current != -1 && !visited[current])

The loop runs while:

• The current node is not -1.
• The current node has not already been visited.

Inside the loop:

visited[current] = true;

pathIndex[current] = path.Count;

path.Add(current);

current = edge[current];

Let's understand each statement.

Step 1:

visited[current] = true;

Mark the current node as visited.

Step 2:

pathIndex[current] = path.Count;

Store the current node's position in the traversal path.

Step 3:

path.Add(current);

Add the current node to our path.

Step 4:

current = edge[current];

Move to the next node using the outgoing edge.

This continues until we reach -1 or a previously visited node.

5. Complete C# Code

Here is the complete implementation using the same method signature provided in the question.

class Solution {
    public int largestSumCycle(int[] edge) {

        int n = edge.Length;

        // Track visited nodes
        bool[] visited = new bool[n];

        // Store the position of each node in the current path
        int[] pathIndex = new int[n];

        Array.Fill(pathIndex, -1);

        int maxSum = -1;

        // Start traversal from every unvisited node
        for (int i = 0; i < n; i++) {

            if (visited[i])
                continue;

            List<int> path = new List<int>();

            int current = i;

            // Traverse until no edge or an already visited node
            while (current != -1 && !visited[current]) {

                visited[current] = true;

                pathIndex[current] = path.Count;

                path.Add(current);

                current = edge[current];
            }

            // Check whether the current node belongs
            // to the current traversal path
            if (current != -1 && pathIndex[current] != -1) {

                int sum = 0;

                // Calculate only the cycle nodes
                for (int j = pathIndex[current]; j < path.Count; j++) {

                    sum += path[j];
                }

                maxSum = Math.Max(maxSum, sum);
            }

            // Reset path index for the next traversal
            foreach (int node in path) {

                pathIndex[node] = -1;
            }
        }

        return maxSum;
    }
}