The longest cycle problem requires identifying the cycle in a directed graph. By analyzing indegree and topological ordering, DFS or BFS can be used. If no cycle exists, the answer is -1.
Problem Statement
You are given a directed graph with n nodes labeled 0 to n - 1, where each node has at most one outgoing edge. The graph is represented by an array of edges of length n, where edges[i] indicates the node to which node i points. If node i has no outgoing edge, edges[i] == -1.
Your task is to 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 without repetition of any other nodes in between.
Examples
Example 1
Input: edges = [3,3,4,2,3]
Output: 3
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
There are no cycles in this graph.
Constraints
- n == edges.length
- 2 <= n <= 105
- -1 <= edges[i] < n
- edges[i] != i
Solution Approach
Graph Indegree and Topological Ordering
This approach focuses on identifying nodes with an indegree of 0 and progressively processing them in topological order. This helps detect cycles by tracing back nodes that point to already-visited nodes, indicating a cycle.
Depth-First Search (DFS)
DFS is used to traverse through the graph, marking nodes as visited and backtracking when encountering a cycle. By tracking the nodes' visitation states, the longest cycle can be identified.
Breadth-First Search (BFS)
BFS can be used as an alternative to DFS by exploring the graph level by level. This is useful for identifying cycles in broader search spaces, providing a methodical check for longer cycles.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity depends on the traversal algorithm used. For DFS or BFS, it is O(n), where n is the number of nodes. Space complexity depends on the space used for marking visited nodes and storing cycle data, which is also O(n).
What Interviewers Usually Probe
- Candidate's understanding of graph traversal techniques like DFS or BFS and their ability to detect cycles.
- How well the candidate can optimize space and time complexity while dealing with graph traversal.
- Ability to connect the graph indegree and topological ordering patterns to detect cycles efficiently.
Common Pitfalls or Variants
Common pitfalls
- Confusing cycle detection with simple path finding.
- Overlooking the need for revisiting nodes that are part of a potential cycle.
- Incorrectly handling the case where no cycle exists and returning invalid results.
Follow-up variants
- Graphs with multiple cycles or no cycles.
- Graphs where some nodes point to themselves.
- Optimizing for graphs with extremely large sizes, requiring efficient traversal.
How GhostInterview Helps
- GhostInterview provides a step-by-step approach to understanding graph traversal techniques.
- It helps identify where cycles occur and how to detect them effectively with minimal computation.
- GhostInterview helps solidify understanding of graph patterns by working through specific examples like this one.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the key pattern for solving the Longest Cycle in a Graph problem?
The key pattern involves using graph indegree and topological ordering to detect cycles in a directed graph.
How does Depth-First Search (DFS) work for this problem?
DFS works by visiting nodes and backtracking when a cycle is found, marking nodes as visited to avoid revisiting them.
What is the time complexity for solving this problem?
The time complexity is O(n), where n is the number of nodes in the graph, as each node is visited once during traversal.
Can this problem be solved using Breadth-First Search (BFS)?
Yes, BFS can also be used by exploring nodes level by level, checking for cycles as nodes are revisited.
What should I do if no cycle exists in the graph?
If no cycle is found, the answer should be -1, indicating the absence of a cycle.
Need direct help with Longest Cycle in a Graph instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Longest Cycle in a Graph from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Solve Number of Increasing Paths in a Grid by turning cell comparisons into a DAG and counting paths with topological DP.
Open problem page#2192 All Ancestors of a Node in a Directed Acyclic GraphSolve the All Ancestors of a Node in a Directed Acyclic Graph problem using graph traversal techniques like BFS, DFS, and topological sort.
Open problem page#1462 Course Schedule IVDetermine if one course is a prerequisite of another using graph indegree tracking and topological ordering efficiently.
Open problem page