Longest Cycle in a Graph - Solution & Explanation
Problem Statement
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.length2 <= n <= 105-1 <= edges[i] < nedges[i] != i
Approach Overview
Problem Overview: You are given a directed graph where each node has at most one outgoing edge. The task is to find the length of the longest cycle in the graph. If no cycle exists, return -1. Because each node points to at most one neighbor, the graph behaves like multiple chains that may eventually form cycles.
Approach 1: Brute Force Traversal from Every Node (O(n^2) time, O(n) space)
Start a traversal from every node and follow outgoing edges until you either reach a visited node or a dead end (-1). Maintain a map or array storing the step index when each node was first seen in the current traversal. If you revisit a node from the same traversal path, a cycle exists and its length equals the difference between the current step and the stored step. Reset tracking for the next start node. This works but repeats large portions of the graph many times.
Approach 2: DFS with Cycle Detection (O(n) time, O(n) space)
Use Depth-First Search with visitation states to detect cycles efficiently. Track three states for each node: unvisited, visiting, and processed. While performing DFS, store the depth or timestamp when you first enter each node. If you reach a node currently marked visiting, you discovered a cycle and its length equals currentDepth - entryDepth[node]. Mark nodes as processed after finishing their path so they are never revisited again. Because every node has at most one outgoing edge, each node is explored once, giving linear time.
Approach 3: Topological Pruning + Cycle Counting (O(n) time, O(n) space)
Another efficient strategy removes nodes that cannot be part of any cycle. Compute indegree for each node in the graph. Push all nodes with indegree 0 into a queue and repeatedly remove them, updating the indegree of their neighbors. This topological sort style pruning eliminates all acyclic chains. The remaining nodes must belong to cycles. Traverse each remaining component and count its cycle length, keeping the maximum.
Recommended for interviews: DFS with cycle detection is the most common solution. It demonstrates strong understanding of graph traversal, visitation states, and cycle detection. The topological pruning approach is also optimal and shows deeper graph reasoning. Brute force helps explain the intuition but does not scale to large inputs.
Approach 1: DFS with Cycle Detection
This approach involves using Depth First Search (DFS) to traverse the graph nodes by starting at each unvisited node. As we explore, we track the nodes in the current path to detect cycles. Whenever we reach a previously visited node that is part of the current path, a cycle is detected, and its length is computed. We keep track of the longest cycle found during the traversal.
The C solution utilizes DFS to detect cycles. Using arrays for tracking visited nodes and recursion stack during traversal, we calculate the cycle length whenever a cycle is detected by re-entering a node part of the current path.
Complexity
Time Complexity: O(n), where n is the number of nodes. We visit each node and edge once.
Space Complexity: O(n), required for the recursion stack and visited nodes array.
Approach 2: Traverse Starting Points
We can traverse each node in the range [0,..,n-1]. If a node has not been visited, we start from this node and search for adjacent nodes until we encounter a cycle or a node that has already been visited. If we encounter a cycle, we update the answer.
The time complexity is O(n) and the space complexity is O(n), where n is the number of nodes.
Similar problems:
Complexity Comparison
| Approach | Complexity |
|---|---|
| DFS with Cycle Detection | Time Complexity: O(n), where n is the number of nodes. We visit each node and edge once. |
| Traverse Starting Points | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Traversal from Each Node | O(n^2) | O(n) | Useful for understanding cycle detection before optimizing |
| DFS with Cycle Detection | O(n) | O(n) | General optimal solution; common interview expectation |
| Topological Pruning + Cycle Counting | O(n) | O(n) | When identifying cycle-only components after removing acyclic nodes |
Video Solution
Longest Cycle in a Graph | Leetcode - 2360 | DFS | Explanation ➕ Live Coding Trash • codestorywithMIK • 15,712 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Longest Cycle in a Graph easy or hard?
Longest Cycle in a Graph Python/Java solution
How to solve Longest Cycle in a Graph in O(n)?
What is the best approach for Longest Cycle in a Graph?
Is Longest Cycle in a Graph asked at Google/Amazon/Meta?
What data structure is used in Longest Cycle in a Graph?
What is the time complexity of Longest Cycle in a Graph?
Ready to solve this problem?
Practice Longest Cycle in a Graph with our built-in code editor and test cases.
Practice on FleetCode