# Longest Cycle in a Graph
**Difficulty:** HARD
[External](https://leetcode.com/problems/longest-cycle-in-a-graph)
Canonical: https://scaleengineer.com/dsa/problems/longest-cycle-in-a-graph
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Topological Sort](https://scaleengineer.com/algorithms/topological-sort)
**Data structures:** Graph
**Companies:** [Juspay](https://scaleengineer.com/companies/juspay)
---
## Problem
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:**

![](https://assets.glich.co/dsa/longest-cycle-in-a-graph/image0.png) 

**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:**

![](https://assets.glich.co/dsa/longest-cycle-in-a-graph/image1.png) 

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

**Constraints:**

* `n == edges.length`
* `2 <= n <= 105`
* `-1 <= edges[i] < n`
* `edges[i] != i`

# Approaches
## Brute-Force Traversal from Each Node
This approach involves iterating through every node in the graph and, for each one, starting a new traversal to detect a cycle. It keeps track of the path taken from the starting node. If a node is encountered that has already been seen in the current path, a cycle is detected, and its length is calculated. This process is repeated for all nodes to ensure the longest cycle is found.
**Time:** O(N^2), where N is the number of nodes. The outer loop runs N times. For each iteration, the inner `while` loop can traverse up to N nodes in the worst case (e.g., a graph that is one long cycle). · **Space:** O(N), where N is the number of nodes. In each iteration of the outer loop, the `pathMap` can store up to N entries in the worst-case scenario of a single path or cycle involving all nodes.
**Pros:** Simple to conceptualize and implement.; Guaranteed to find the correct longest cycle length.
**Cons:** Highly inefficient due to redundant computations. The same paths and cycles are traversed multiple times from different starting nodes.; For larger graphs, this approach will be too slow and will likely exceed the time limit on platforms like LeetCode.
### Explanation
The brute-force algorithm systematically checks for cycles starting from every single node. For each node `i`, it traces the path of outgoing edges, recording each visited node and its distance from `i` in a hash map. If the traversal encounters a node that's already in the hash map for the current path, it signifies a cycle. The length of the cycle is the difference between the current distance and the distance stored when the node was first visited. The maximum length found across all starting nodes is the result.

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

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

        for (int i = 0; i < n; i++) {
            // For each starting node, we trace its path.
            Map<Integer, Integer> pathMap = new HashMap<>();
            int dist = 0;
            int currentNode = i;

            while (currentNode != -1) {
                if (pathMap.containsKey(currentNode)) {
                    // Cycle detected.
                    int cycleLength = dist - pathMap.get(currentNode);
                    maxLength = Math.max(maxLength, cycleLength);
                    break;
                }
                
                pathMap.put(currentNode, dist);
                currentNode = edges[currentNode];
                dist++;
            }
        }
        return maxLength;
    }
}
```
### Algorithm
- Initialize a variable `maxLength` to -1.
- Iterate through each node `i` from `0` to `n-1` to use as a starting point for a traversal.
- For each starting node `i`:
  - Create a `HashMap` called `pathMap` to store visited nodes and their distances in the current traversal.
  - Initialize `distance = 0` and `currentNode = i`.
  - Start a `while` loop that continues as long as `currentNode` is valid (not -1).
  - Inside the loop, check if `currentNode` is already in `pathMap`.
    - If yes, a cycle is found. Calculate its length as `distance - pathMap.get(currentNode)`. Update `maxLength` if this cycle is longer. Then, break the inner loop.
    - If no, add `currentNode` and its `distance` to `pathMap`.
  - Move to the next node by setting `currentNode = edges[currentNode]` and increment `distance`.
- After checking all nodes as starting points, return `maxLength`.

## 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.
**Time:** 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:** 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:** 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.
### Explanation
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.

```java
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;
    }
}
```
### 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`.

# Solutions
### Java

```java
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;
  }
}

```

### Python

```python
class Solution:
    def longestCycle(self, edges: List[int]) -> int: n = len(edges) vis = [False] * n ans = - 1 for i in range(n): if vis[i]: continue j = i cycle = [] while j != - 1 and not vis[j]: vis[j] = True cycle . append(j) j = edges[j] if j == - 1: continue m = len(cycle) k = next((k for k in range(m) if cycle[k] == j), inf) ans = max(ans, m - k) return ans

```

### CPP

```cpp
class Solution {
public:
  int longestCycle(vector<int> &edges) {
    int n = edges.size();
    vector<bool> vis(n);
    int ans = -1;
    for (int i = 0; i < n; ++i) {
      if (vis[i]) {
        continue;
      }
      int j = i;
      vector<int> cycle;
      for (; j != -1 && !vis[j]; j = edges[j]) {
        vis[j] = true;
        cycle.push_back(j);
      }
      if (j == -1) {
        continue;
      }
      for (int k = 0; k < cycle.size(); ++k) {
        if (cycle[k] == j) {
          ans = max(ans, (int)cycle.size() - k);
          break;
        }
      }
    }
    return ans;
  }
};

```