Longest Cycle in a Graph

Problem

LeetCode 2360 — Longest Cycle in a Graph

You are given a directed graph of n nodes where each node has at most one outgoing edge, represented by edges[] where edges[i] is the next node from i, or -1 if none. Return the length of the longest cycle, or -1 if no cycle exists.

Example

edges = [3, 3, 4, 2, 3]

0 → 3 → 2 → 4 → 3  (cycle: 3 → 2 → 4 → 3, length 3)
1 → 3               (enters the already-processed cycle, no new cycle)

output = 3

Approach — Step Tracking (Functional Graph)

Since each node has at most one outgoing edge, following edges from any node creates a single unbranching path — this is called a functional graph. Every connected component is a rho (ρ) shape: a tail leading into a cycle.

Key insight: no branching means no recursion needed — just a while loop. Stamp each node with a global steps counter when first visited. A single visited[] array replaces both the “on current path” check and the “already processed” check:

• visited[node] >= start → node is on the current path → cycle! length = steps - visited[node]
• visited[node] < start → node from a previous traversal → stop, no cycle here
• visited[node] == 0 → unvisited → keep walking

Walkthrough

edges = [3, 3, 4, 2, 3], steps starts at 1

Start node 0, start = 1:
  visit 0 → visited[0]=1, steps=2, follow to 3
  visit 3 → visited[3]=2, steps=3, follow to 2
  visit 2 → visited[2]=3, steps=4, follow to 4
  visit 4 → visited[4]=4, steps=5, follow to 3
  node 3: visited[3]=2 >= start(1) → cycle! length = 5 - 2 = 3

Start node 1, start = 5:
  visit 1 → visited[1]=5, steps=6, follow to 3
  node 3: visited[3]=2 < start(5) → previous traversal, stop

Complexity

• Time: O(n) — each node is stamped exactly once
• Space: O(n) — visited array

Solution

class Solution {
    public int longestCycle(int[] edges) {
        int n = edges.length;
        int[] visited = new int[n];
        int steps = 1;
        int result = -1;

        for (int i = 0; i < n; i++) {
            if (visited[i] != 0) continue;
            int start = steps;
            int node = i;
            while (node != -1 && visited[node] == 0) {
                visited[node] = steps++;
                node = edges[node];
            }
            if (node != -1 && visited[node] >= start) {
                result = Math.max(result, steps - visited[node]);
            }
        }

        return result;
    }
}

Why It Teaches You Something

The “stamp with global timer, compare against traversal start” trick is a clean alternative to Tarjan’s low-link for functional graphs. The SCC insight still holds: every SCC with size > 1 in this graph is exactly a cycle, and the longest such SCC is the answer.

The same pattern solves: