Longest Cycle in a Graph

HARD

Description

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.

Example 1:

Input: edges = [3,3,4,2,3]
Output: 3
Explanation: The longest cycle in the graph is the cycle: 2 -> 4 -> 3 -> 2.
The length of this cycle is 3, so 3 is returned.

Example 2:

Input: edges = [2,-1,3,1]
Output: -1
Explanation: There are no cycles in this graph.

Constraints:

n == edges.length
2 <= n <= 10⁵
-1 <= edges[i] < n
edges[i] != i

Approaches

Checkout 2 different approaches to solve Longest Cycle in a Graph. Click on different approaches to view the approach and algorithm in detail.

Optimized Traversal with Visited Set (DFS)

This optimized approach avoids re-processing nodes by using a global visited array. It iterates through each node, and if a node hasn't been visited yet, it starts a traversal (akin to a Depth First Search). During the traversal, it keeps track of the current path and distances. If a cycle is found, its length is calculated. If the path leads to an already visited node, the traversal stops, as that part of the graph has been checked. This ensures each node is processed only once.

Algorithm

Initialize maxLength = -1.
Create a global boolean visited array of size n to track nodes that have been part of any completed traversal, initialized to false.
Iterate through each node i from 0 to n-1.
If visited[i] is false:
- Start a new traversal from i.
- Use a HashMap, distMap, to store (node, distance) for the current path only.
- Initialize dist = 0 and currentNode = i.
- Traverse the path as long as currentNode is valid:
  - If currentNode is in distMap, a cycle is found. Calculate its length (dist - distMap.get(currentNode)), update maxLength, and break the inner traversal.
  - If visited[currentNode] is true, the path has merged into an already explored component. No new cycle can be found, so break the inner traversal.
  - Otherwise, add (currentNode, dist) to distMap.
  - Move to the next node: currentNode = edges[currentNode] and increment dist.
- After the traversal from i is complete (due to cycle, visited node, or -1), mark all nodes in distMap as globally visited by setting visited[node] = true.
Return maxLength.

This method is an efficient, DFS-like traversal. We maintain a global visited array to ensure that each node is processed at most once. We iterate from node 0 to n-1. If a node i has not been visited, we begin a traversal. We use a local HashMap to store the nodes in the current path and their distances from the starting node i.

If during this traversal we encounter a node that is already in our local map, we've found a cycle. We calculate its length and update our maximum. If we encounter a node that is in the global visited array, it means we've merged with a path that has already been fully explored, so we can stop the current traversal. After a traversal from a starting node i concludes, we mark all nodes visited in that path in the global visited array to prevent redundant work.

import java.util.HashMap;
import java.util.Map;

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

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                Map<Integer, Integer> distMap = new HashMap<>();
                int dist = 0;
                int currentNode = i;

                while (currentNode != -1) {
                    if (distMap.containsKey(currentNode)) {
                        int cycleLength = dist - distMap.get(currentNode);
                        maxLength = Math.max(maxLength, cycleLength);
                        break; 
                    }
                    if (visited[currentNode]) {
                        // Path merges into an already processed component.
                        break;
                    }
                    
                    distMap.put(currentNode, dist);
                    currentNode = edges[currentNode];
                    dist++;
                }
                
                // Mark all nodes in the current path as visited to avoid re-processing.
                for (int node : distMap.keySet()) {
                    visited[node] = true;
                }
            }
        }
        return maxLength;
    }
}

Complexity Analysis

Time Complexity: O(N), where N is the number of nodes. Each node is visited a constant number of times. The outer loop runs N times, but the inner `while` loop's work is amortized across all nodes, as each node is marked `visited` after being processed once.Space Complexity: O(N), where N is the number of nodes. This is for the `visited` array and the `distMap`. In the worst case, `distMap` can hold up to N nodes (a single path or cycle).

Pros and Cons

Pros:

Highly efficient, with a linear time complexity.
Avoids redundant computations by ensuring each node is processed only once.
Optimal solution for the given constraints.

Cons:

Slightly more complex to implement than the brute-force approach due to the need to manage both a global visited state and a local path state.

Code Solutions

Checking out 3 solutions in different languages for Longest Cycle in a Graph. Click on different languages to view the code.

class Solution {
public
  int longestCycle(int[] edges) {
    int n = edges.length;
    boolean[] vis = new boolean[n];
    int ans = -1;
    for (int i = 0; i < n; ++i) {
      if (vis[i]) {
        continue;
      }
      int j = i;
      List<Integer> cycle = new ArrayList<>();
      for (; j != -1 && !vis[j]; j = edges[j]) {
        vis[j] = true;
        cycle.add(j);
      }
      if (j == -1) {
        continue;
      }
      for (int k = 0; k < cycle.size(); ++k) {
        if (cycle.get(k) == j) {
          ans = Math.max(ans, cycle.size() - k);
          break;
        }
      }
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Longest Cycle in a Graph

Algorithms:

Depth-First SearchBreadth-First SearchTopological Sort

Data Structures:

Graph

Companies:

Juspay |