Longest Cycle in a Graph

Problem#

A directed graph where each node has at most one outgoing edge — edges[i] is the next node from i, or -1. Return the length of the longest cycle, or -1 if no cycle exists.

Examples#

edges = [3,3,4,2,3] → 3
edges = [2,-1,3,1] → -1

Constraints#

n == edges.length, 2 <= n <= 10^5, -1 <= edges[i] < n, edges[i] != i.

Approach#

Each node has at most one outgoing edge, so the graph is a forest of “rho” shapes: tails leading into cycles. Walk forward from each unvisited node, tagging visit timestamps. If we hit a node visited in the current walk, the cycle length is currentTime - startTime. If we hit a previously visited node, stop.

Solution#

class Solution {
public:
    int longestCycle(vector<int>& edges) {
        int n = edges.size();
        vector<int> visitTime(n, 0);
        int timer = 1, best = -1;
        for (int start = 0; start < n; ++start) {
            if (visitTime[start]) continue;
            int u = start, startTime = timer;
            while (u != -1 && !visitTime[u]) {
                visitTime[u] = timer++;
                u = edges[u];
            }
            if (u != -1 && visitTime[u] >= startTime) {
                best = max(best, timer - visitTime[u]);
            }
        }
        return best;
    }
};

func longestCycle(edges []int) int {
    n := len(edges)
    visitTime := make([]int, n)
    timer, best := 1, -1
    for start := 0; start < n; start++ {
        if visitTime[start] != 0 {
            continue
        }
        u, startTime := start, timer
        for u != -1 && visitTime[u] == 0 {
            visitTime[u] = timer
            timer++
            u = edges[u]
        }
        if u != -1 && visitTime[u] >= startTime {
            if length := timer - visitTime[u]; length > best {
                best = length
            }
        }
    }
    return best
}

from typing import List

class Solution:
    def longestCycle(self, edges: List[int]) -> int:
        n = len(edges)
        visit_time = [0] * n
        timer, best = 1, -1
        for start in range(n):
            if visit_time[start]:
                continue
            u, start_time = start, timer
            while u != -1 and not visit_time[u]:
                visit_time[u] = timer
                timer += 1
                u = edges[u]
            if u != -1 and visit_time[u] >= start_time:
                length = timer - visit_time[u]
                if length > best:
                    best = length
        return best

function longestCycle(edges) {
    const n = edges.length;
    const visitTime = new Array(n).fill(0);
    let timer = 1, best = -1;
    for (let start = 0; start < n; start++) {
        if (visitTime[start]) continue;
        let u = start;
        const startTime = timer;
        while (u !== -1 && !visitTime[u]) {
            visitTime[u] = timer++;
            u = edges[u];
        }
        if (u !== -1 && visitTime[u] >= startTime) {
            best = Math.max(best, timer - visitTime[u]);
        }
    }
    return best;
}

class Solution {
    public int longestCycle(int[] edges) {
        int n = edges.length;
        int[] visitTime = new int[n];
        int timer = 1, best = -1;
        for (int start = 0; start < n; start++) {
            if (visitTime[start] != 0) continue;
            int u = start, startTime = timer;
            while (u != -1 && visitTime[u] == 0) {
                visitTime[u] = timer++;
                u = edges[u];
            }
            if (u != -1 && visitTime[u] >= startTime) {
                best = Math.max(best, timer - visitTime[u]);
            }
        }
        return best;
    }
}

function longestCycle(edges: number[]): number {
    const n = edges.length;
    const visitTime: number[] = new Array(n).fill(0);
    let timer = 1, best = -1;
    for (let start = 0; start < n; start++) {
        if (visitTime[start]) continue;
        let u = start;
        const startTime = timer;
        while (u !== -1 && !visitTime[u]) {
            visitTime[u] = timer++;
            u = edges[u];
        }
        if (u !== -1 && visitTime[u] >= startTime) {
            best = Math.max(best, timer - visitTime[u]);
        }
    }
    return best;
}

Editorial#

The functional-graph structure means each node belongs to at most one cycle. The “current walk started at timestamp startTime” trick distinguishes a cycle in the current chain (cycle length = current timer minus the revisited node’s timestamp) from a tail merging into a previously explored cycle.

Complexity#

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

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#