Detect cycle in a directed graph
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given a directed graph represented by an adjacency list with n vertices and m edges, determine whether the graph contains a cycle. Describe and implement an algorithm that returns true if a cycle exists and false otherwise. Explain the time and space complexity, and discuss both a DFS-based approach using a recursion stack and an approach based on Kahn’s topological sort.
Quick Answer: This question evaluates mastery of graph algorithms and graph theory concepts—specifically directed cycle detection—and assesses the ability to reason about algorithmic correctness and to analyze time and space complexity for competing approaches.
Given a directed graph with `n` vertices labeled `0` to `n-1` and a list of directed `edges` where each edge `[u, v]` means there is a directed edge from `u` to `v`, determine whether the graph contains a cycle.
Return `true` if at least one directed cycle exists, and `false` otherwise.
A directed cycle is a path `v0 -> v1 -> ... -> vk -> v0` of length at least 1 that follows edge directions and returns to its starting vertex. Note that a self-loop (an edge `[u, u]`) counts as a cycle.
**Approach.** The canonical solution is a DFS that colors each vertex WHITE (unvisited), GRAY (on the current recursion stack), or BLACK (fully explored). A cycle exists iff a DFS encounters an edge to a GRAY vertex — a *back edge* into an ancestor still on the stack. An equivalent alternative is Kahn's algorithm (BFS topological sort): repeatedly remove vertices with in-degree 0; if fewer than `n` vertices get removed, the leftover vertices form a cycle.
**Example 1:**
```
Input: n = 4, edges = [[0,1],[1,2],[2,3],[3,1]]
Output: true
Explanation: 1 -> 2 -> 3 -> 1 forms a cycle.
```
**Example 2:**
```
Input: n = 4, edges = [[0,1],[1,2],[2,3]]
Output: false
Explanation: The graph is a simple chain (DAG); no cycle.
```
**Example 3:**
```
Input: n = 1, edges = [[0,0]]
Output: true
Explanation: The self-loop at vertex 0 is a cycle.
```
Constraints
- 0 <= n <= 10^4
- 0 <= m <= 10^5 (m = number of edges)
- Each edge is [u, v] with 0 <= u, v < n
- Self-loops (u == v) are allowed and count as a cycle
- Parallel/duplicate edges may appear
Examples
Input: (4, [[0, 1], [1, 2], [2, 3], [3, 1]])
Expected Output: True
Explanation: 1 -> 2 -> 3 -> 1 is a back edge into the current DFS stack, so a cycle exists.
Input: (4, [[0, 1], [1, 2], [2, 3]])
Expected Output: False
Explanation: A straight chain 0->1->2->3 is a DAG; no back edge is ever found.
Hints
- A directed graph has a cycle iff a DFS finds a back edge — an edge pointing to a vertex that is currently on the recursion stack (still being explored).
- Three-color the vertices: WHITE = unvisited, GRAY = in progress (on the stack), BLACK = finished. Seeing an edge to a GRAY vertex means a cycle.
- Start a DFS from every WHITE vertex so disconnected components are all covered. Don't restart from BLACK vertices.
- Alternative: Kahn's topological sort. Compute in-degrees, repeatedly pop vertices with in-degree 0; if you can't process all n vertices, the remainder contains a cycle.
- Remember the self-loop edge cases: [u, u] is a cycle by itself.