Longest cycle in a graph

Depth-First Search Breadth-First Search Graph Theory Topological Sort

50.5% acceptance

Feb 25, 2026

2542

You are given a directed graph of n nodes numbered from 0 to n - 1, where each node has at most one outgoing edge. The graph is represented with a given 0-indexed array edges of size n, indicating that there is a directed edge from node i to node edges[i]. If there is no outgoing edge from node i, then edges[i] == -1. Return the length of the longest cycle in the graph. If no cycle exists, return -1. A cycle is a path that starts and ends at the same node.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn longest_cycle(edges: Vec<i32>) -> i32 {
    let n = edges.len();
    let mut dist: Vec<i64> = vec![-1; n];
    let mut ans = -1i32;
    let mut timer = 0i64;
    for start in 0..n {
      if dist[start] != -1 { continue; }
      let t = timer;
      let mut cur = start as i32;
      while cur != -1 {
        let u = cur as usize;
        if dist[u] != -1 {
          if dist[u] >= t {
            ans = ans.max((timer - dist[u]) as i32);
          }
          break;
        }
        dist[u] = timer;
        timer += 1;
        cur = edges[u];
      }
    }
    ans
  }
}