Longest Cycle in a Graph

hard graph dfs topological sort

Problem

In a directed graph where each node has at most one outgoing edge (encoded by edges[i], or -1), return the length of the longest cycle, or -1 if none exists.

Inputedges = [3,3,4,2,3]

Output3

Cycle 2 → 4 → 3 → 2 has length 3.

edges (comma; -1 = none)

def longest_cycle(edges):
    n = len(edges)
    time = [0] * n
    ans, clock = -1, 1
    for start in range(n):
        if time[start]: continue
        cur, t0 = start, clock
        while cur != -1 and time[cur] == 0:
            time[cur] = clock
            clock += 1
            cur = edges[cur]
        if cur != -1 and time[cur] >= t0:
            ans = max(ans, clock - time[cur])
    return ans

function longestCycle(edges) {
  const n = edges.length;
  const time = new Array(n).fill(0);
  let ans = -1, clock = 1;
  for (let start = 0; start < n; start++) {
    if (time[start]) continue;
    let cur = start, t0 = clock;
    while (cur !== -1 && time[cur] === 0) {
      time[cur] = clock++;
      cur = edges[cur];
    }
    if (cur !== -1 && time[cur] >= t0) {
      ans = Math.max(ans, clock - time[cur]);
    }
  }
  return ans;
}

class Solution {
    public int longestCycle(int[] edges) {
        int n = edges.length;
        int[] time = new int[n];
        int ans = -1, clock = 1;
        for (int start = 0; start < n; start++) {
            if (time[start] != 0) continue;
            int cur = start, t0 = clock;
            while (cur != -1 && time[cur] == 0) {
                time[cur] = clock++;
                cur = edges[cur];
            }
            if (cur != -1 && time[cur] >= t0)
                ans = Math.max(ans, clock - time[cur]);
        }
        return ans;
    }
}

int longestCycle(vector<int>& edges) {
    int n = edges.size();
    vector<int> time(n, 0);
    int ans = -1, clock = 1;
    for (int start = 0; start < n; start++) {
        if (time[start]) continue;
        int cur = start, t0 = clock;
        while (cur != -1 && time[cur] == 0) {
            time[cur] = clock++;
            cur = edges[cur];
        }
        if (cur != -1 && time[cur] >= t0)
            ans = max(ans, clock - time[cur]);
    }
    return ans;
}

Explanation

This is a functional graph: every node has at most one outgoing edge, so from any node you just keep following the single arrow. That means cycles are easy to spot if you remember when you visited each node.

We give every node a time stamp using a global clock that only moves forward. Starting from an unvisited node, we walk forward stamping each node we hit, until we either fall off the graph (-1) or land on a node we have already stamped.

The trick is the check time[cur] >= t0. Here t0 is the clock value when the current walk began. If the node we re-hit was stamped during this same walk, we just closed a cycle, and its length is clock - time[cur] (now minus when we first entered that node).

If instead the node was stamped in an earlier walk, its time is below t0, so it is not part of our current cycle and we skip it. Each node gets visited only once overall, keeping it O(n).

Example: edges = [3,3,4,2,3]. Walking from node 2 we stamp 2, 4, 3, then re-enter 2 within the same walk. The cycle length comes out to 3, which is the answer.

Time: O(n) Space: O(n)