Language Selection
Choose your preferred programming language
Showing: Python
Problem Statement
Given a directed graph, determine if it contains a cycle. A cycle exists in a directed graph if there is a path that starts and ends at the same vertex following the direction of edges.
Input:
- Number of vertices
n(labeled 0 to n-1) - List of directed edges where each edge is [from, to]
Output:
- Boolean indicating whether the graph contains a cycle
Constraints:
- 1 ≤ n ≤ 10^4
- 0 ≤ edges.length ≤ 10^4
- Graph may have disconnected components
- Graph may have self-loops or multiple edges
Examples:
Example 1:
Input: n = 4, edges = [[0, 1], [1, 2], [2, 3], [3, 1]]
Output: true
Explanation: There's a cycle: 1 -> 2 -> 3 -> 1
Example 2:
Input: n = 3, edges = [[0, 1], [1, 2]]
Output: false
Explanation: This is a DAG (Directed Acyclic Graph) with no cycles
Example 3:
Input: n = 2, edges = [[0, 1], [1, 0]]
Output: true
Explanation: There's a cycle between vertices 0 and 1
Solutions
Approach 1: DFS with Three Colors
Use three colors to track vertex states: White (unvisited), Gray (visiting), Black (visited).
Algorithm:
- Mark all vertices as White initially
- For each White vertex, start DFS
- During DFS:
- Mark vertex as Gray when entering
- If we encounter a Gray vertex, we found a cycle
- Mark vertex as Black when leaving
- Return true if cycle found, false otherwise
Python:
def hasCycleDirected(n, edges):
"""
Detect cycle using DFS with colors
Time: O(V + E)
Space: O(V)
"""
# Build adjacency list
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
# 0: White (unvisited), 1: Gray (visiting), 2: Black (visited)
color = [0] * n
def dfs(node):
if color[node] == 1: # Gray - found a back edge
return True
if color[node] == 2: # Black - already processed
return False
color[node] = 1 # Mark as Gray
for neighbor in graph[node]:
if dfs(neighbor):
return True
color[node] = 2 # Mark as Black
return False
# Check all components
for i in range(n):
if color[i] == 0:
if dfs(i):
return True
return False
def hasCycleDirectedPath(n, edges):
"""
Detect cycle and return the cycle path if exists
Time: O(V + E)
Space: O(V)
"""
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
color = [0] * n
path = []
cycle = []
def dfs(node):
nonlocal cycle
if color[node] == 1: # Found cycle
# Extract cycle from path
idx = path.index(node)
cycle = path[idx:] + [node]
return True
if color[node] == 2:
return False
color[node] = 1
path.append(node)
for neighbor in graph[node]:
if dfs(neighbor):
return True
color[node] = 2
path.pop()
return False
for i in range(n):
if color[i] == 0:
if dfs(i):
return True, cycle
return False, []
Java:
import java.util.*;
class Solution {
/**
* Detect cycle using DFS with colors
* Time: O(V + E)
* Space: O(V)
*/
public boolean hasCycleDirected(int n, int[][] edges) {
// Build adjacency list
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
}
// 0: White, 1: Gray, 2: Black
int[] color = new int[n];
// Check all components
for (int i = 0; i < n; i++) {
if (color[i] == 0) {
if (dfs(graph, i, color)) {
return true;
}
}
}
return false;
}
private boolean dfs(List<List<Integer>> graph, int node, int[] color) {
if (color[node] == 1) return true; // Gray - cycle detected
if (color[node] == 2) return false; // Black - already processed
color[node] = 1; // Mark as Gray
for (int neighbor : graph.get(node)) {
if (dfs(graph, neighbor, color)) {
return true;
}
}
color[node] = 2; // Mark as Black
return false;
}
/**
* Detect cycle with path tracking
* Time: O(V + E)
* Space: O(V)
*/
public class CycleResult {
boolean hasCycle;
List<Integer> cyclePath;
CycleResult(boolean hasCycle, List<Integer> cyclePath) {
this.hasCycle = hasCycle;
this.cyclePath = cyclePath;
}
}
public CycleResult hasCycleDirectedWithPath(int n, int[][] edges) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
}
int[] color = new int[n];
List<Integer> path = new ArrayList<>();
List<Integer> cycle = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (color[i] == 0) {
if (dfsWithPath(graph, i, color, path, cycle)) {
return new CycleResult(true, cycle);
}
}
}
return new CycleResult(false, new ArrayList<>());
}
private boolean dfsWithPath(List<List<Integer>> graph, int node,
int[] color, List<Integer> path, List<Integer> cycle) {
if (color[node] == 1) {
int idx = path.indexOf(node);
cycle.clear();
cycle.addAll(path.subList(idx, path.size()));
cycle.add(node);
return true;
}
if (color[node] == 2) return false;
color[node] = 1;
path.add(node);
for (int neighbor : graph.get(node)) {
if (dfsWithPath(graph, neighbor, color, path, cycle)) {
return true;
}
}
color[node] = 2;
path.remove(path.size() - 1);
return false;
}
}
Go:
// hasCycleDirected - Detect cycle using DFS with colors
// Time: O(V + E)
// Space: O(V)
func hasCycleDirected(n int, edges [][]int) bool {
// Build adjacency list
graph := make([][]int, n)
for _, edge := range edges {
graph[edge[0]] = append(graph[edge[0]], edge[1])
}
// 0: White, 1: Gray, 2: Black
color := make([]int, n)
var dfs func(node int) bool
dfs = func(node int) bool {
if color[node] == 1 { // Gray - cycle detected
return true
}
if color[node] == 2 { // Black - already processed
return false
}
color[node] = 1 // Mark as Gray
for _, neighbor := range graph[node] {
if dfs(neighbor) {
return true
}
}
color[node] = 2 // Mark as Black
return false
}
// Check all components
for i := 0; i < n; i++ {
if color[i] == 0 {
if dfs(i) {
return true
}
}
}
return false
}
type CycleResult struct {
HasCycle bool
Path []int
}
// hasCycleDirectedWithPath - Detect cycle with path tracking
// Time: O(V + E)
// Space: O(V)
func hasCycleDirectedWithPath(n int, edges [][]int) CycleResult {
graph := make([][]int, n)
for _, edge := range edges {
graph[edge[0]] = append(graph[edge[0]], edge[1])
}
color := make([]int, n)
path := []int{}
cycle := []int{}
var dfs func(node int) bool
dfs = func(node int) bool {
if color[node] == 1 {
// Find cycle start in path
for i, v := range path {
if v == node {
cycle = append([]int{}, path[i:]...)
cycle = append(cycle, node)
return true
}
}
}
if color[node] == 2 {
return false
}
color[node] = 1
path = append(path, node)
for _, neighbor := range graph[node] {
if dfs(neighbor) {
return true
}
}
color[node] = 2
path = path[:len(path)-1]
return false
}
for i := 0; i < n; i++ {
if color[i] == 0 {
if dfs(i) {
return CycleResult{true, cycle}
}
}
}
return CycleResult{false, []int{}}
}
JavaScript:
/**
* Detect cycle using DFS with colors
* Time: O(V + E)
* Space: O(V)
*/
function hasCycleDirected(n, edges) {
// Build adjacency list
const graph = Array(n).fill().map(() => []);
for (const [u, v] of edges) {
graph[u].push(v);
}
// 0: White, 1: Gray, 2: Black
const color = new Array(n).fill(0);
function dfs(node) {
if (color[node] === 1) return true; // Gray - cycle detected
if (color[node] === 2) return false; // Black - already processed
color[node] = 1; // Mark as Gray
for (const neighbor of graph[node]) {
if (dfs(neighbor)) {
return true;
}
}
color[node] = 2; // Mark as Black
return false;
}
// Check all components
for (let i = 0; i < n; i++) {
if (color[i] === 0) {
if (dfs(i)) {
return true;
}
}
}
return false;
}
/**
* Detect cycle with path tracking
* Time: O(V + E)
* Space: O(V)
*/
function hasCycleDirectedWithPath(n, edges) {
const graph = Array(n).fill().map(() => []);
for (const [u, v] of edges) {
graph[u].push(v);
}
const color = new Array(n).fill(0);
const path = [];
let cycle = [];
function dfs(node) {
if (color[node] === 1) {
const idx = path.indexOf(node);
cycle = [...path.slice(idx), node];
return true;
}
if (color[node] === 2) return false;
color[node] = 1;
path.push(node);
for (const neighbor of graph[node]) {
if (dfs(neighbor)) {
return true;
}
}
color[node] = 2;
path.pop();
return false;
}
for (let i = 0; i < n; i++) {
if (color[i] === 0) {
if (dfs(i)) {
return { hasCycle: true, path: cycle };
}
}
}
return { hasCycle: false, path: [] };
}
C#:
using System;
using System.Collections.Generic;
public class Solution {
/// <summary>
/// Detect cycle using DFS with colors
/// Time: O(V + E)
/// Space: O(V)
/// </summary>
public bool HasCycleDirected(int n, int[][] edges) {
// Build adjacency list
List<int>[] graph = new List<int>[n];
for (int i = 0; i < n; i++) {
graph[i] = new List<int>();
}
foreach (var edge in edges) {
graph[edge[0]].Add(edge[1]);
}
// 0: White, 1: Gray, 2: Black
int[] color = new int[n];
// Check all components
for (int i = 0; i < n; i++) {
if (color[i] == 0) {
if (Dfs(graph, i, color)) {
return true;
}
}
}
return false;
}
private bool Dfs(List<int>[] graph, int node, int[] color) {
if (color[node] == 1) return true; // Gray - cycle detected
if (color[node] == 2) return false; // Black - already processed
color[node] = 1; // Mark as Gray
foreach (int neighbor in graph[node]) {
if (Dfs(graph, neighbor, color)) {
return true;
}
}
color[node] = 2; // Mark as Black
return false;
}
public class CycleResult {
public bool HasCycle { get; set; }
public List<int> Path { get; set; }
public CycleResult(bool hasCycle, List<int> path) {
HasCycle = hasCycle;
Path = path;
}
}
/// <summary>
/// Detect cycle with path tracking
/// Time: O(V + E)
/// Space: O(V)
/// </summary>
public CycleResult HasCycleDirectedWithPath(int n, int[][] edges) {
List<int>[] graph = new List<int>[n];
for (int i = 0; i < n; i++) {
graph[i] = new List<int>();
}
foreach (var edge in edges) {
graph[edge[0]].Add(edge[1]);
}
int[] color = new int[n];
List<int> path = new List<int>();
List<int> cycle = new List<int>();
for (int i = 0; i < n; i++) {
if (color[i] == 0) {
if (DfsWithPath(graph, i, color, path, cycle)) {
return new CycleResult(true, cycle);
}
}
}
return new CycleResult(false, new List<int>());
}
private bool DfsWithPath(List<int>[] graph, int node, int[] color,
List<int> path, List<int> cycle) {
if (color[node] == 1) {
int idx = path.IndexOf(node);
cycle.Clear();
for (int i = idx; i < path.Count; i++) {
cycle.Add(path[i]);
}
cycle.Add(node);
return true;
}
if (color[node] == 2) return false;
color[node] = 1;
path.Add(node);
foreach (int neighbor in graph[node]) {
if (DfsWithPath(graph, neighbor, color, path, cycle)) {
return true;
}
}
color[node] = 2;
path.RemoveAt(path.Count - 1);
return false;
}
}
Approach 2: Using Recursion Stack
Track vertices in the current recursion stack to detect back edges.
Python:
def hasCycleRecStack(n, edges):
"""
Detect cycle using recursion stack
Time: O(V + E)
Space: O(V)
"""
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
visited = [False] * n
rec_stack = [False] * n
def dfs(node):
visited[node] = True
rec_stack[node] = True
for neighbor in graph[node]:
if not visited[neighbor]:
if dfs(neighbor):
return True
elif rec_stack[neighbor]:
return True
rec_stack[node] = False
return False
for i in range(n):
if not visited[i]:
if dfs(i):
return True
return False
Java:
public boolean hasCycleRecStack(int n, int[][] edges) {
/**
* Detect cycle using recursion stack
* Time: O(V + E)
* Space: O(V)
*/
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
}
boolean[] visited = new boolean[n];
boolean[] recStack = new boolean[n];
for (int i = 0; i < n; i++) {
if (!visited[i]) {
if (dfsRecStack(graph, i, visited, recStack)) {
return true;
}
}
}
return false;
}
private boolean dfsRecStack(List<List<Integer>> graph, int node,
boolean[] visited, boolean[] recStack) {
visited[node] = true;
recStack[node] = true;
for (int neighbor : graph.get(node)) {
if (!visited[neighbor]) {
if (dfsRecStack(graph, neighbor, visited, recStack)) {
return true;
}
} else if (recStack[neighbor]) {
return true;
}
}
recStack[node] = false;
return false;
}
Go:
// hasCycleRecStack - Detect cycle using recursion stack
// Time: O(V + E)
// Space: O(V)
func hasCycleRecStack(n int, edges [][]int) bool {
graph := make([][]int, n)
for _, edge := range edges {
graph[edge[0]] = append(graph[edge[0]], edge[1])
}
visited := make([]bool, n)
recStack := make([]bool, n)
var dfs func(node int) bool
dfs = func(node int) bool {
visited[node] = true
recStack[node] = true
for _, neighbor := range graph[node] {
if !visited[neighbor] {
if dfs(neighbor) {
return true
}
} else if recStack[neighbor] {
return true
}
}
recStack[node] = false
return false
}
for i := 0; i < n; i++ {
if !visited[i] {
if dfs(i) {
return true
}
}
}
return false
}
JavaScript:
/**
* Detect cycle using recursion stack
* Time: O(V + E)
* Space: O(V)
*/
function hasCycleRecStack(n, edges) {
const graph = Array(n).fill().map(() => []);
for (const [u, v] of edges) {
graph[u].push(v);
}
const visited = new Array(n).fill(false);
const recStack = new Array(n).fill(false);
function dfs(node) {
visited[node] = true;
recStack[node] = true;
for (const neighbor of graph[node]) {
if (!visited[neighbor]) {
if (dfs(neighbor)) {
return true;
}
} else if (recStack[neighbor]) {
return true;
}
}
recStack[node] = false;
return false;
}
for (let i = 0; i < n; i++) {
if (!visited[i]) {
if (dfs(i)) {
return true;
}
}
}
return false;
}
C#:
public bool HasCycleRecStack(int n, int[][] edges) {
/// <summary>
/// Detect cycle using recursion stack
/// Time: O(V + E)
/// Space: O(V)
/// </summary>
List<int>[] graph = new List<int>[n];
for (int i = 0; i < n; i++) {
graph[i] = new List<int>();
}
foreach (var edge in edges) {
graph[edge[0]].Add(edge[1]);
}
bool[] visited = new bool[n];
bool[] recStack = new bool[n];
for (int i = 0; i < n; i++) {
if (!visited[i]) {
if (DfsRecStack(graph, i, visited, recStack)) {
return true;
}
}
}
return false;
}
private bool DfsRecStack(List<int>[] graph, int node,
bool[] visited, bool[] recStack) {
visited[node] = true;
recStack[node] = true;
foreach (int neighbor in graph[node]) {
if (!visited[neighbor]) {
if (DfsRecStack(graph, neighbor, visited, recStack)) {
return true;
}
} else if (recStack[neighbor]) {
return true;
}
}
recStack[node] = false;
return false;
}
Approach 3: Topological Sort (Kahn’s Algorithm)
A directed graph has a cycle if and only if it cannot be topologically sorted.
Python:
from collections import deque
def hasCycleKahn(n, edges):
"""
Detect cycle using Kahn's algorithm
Time: O(V + E)
Space: O(V)
"""
graph = [[] for _ in range(n)]
in_degree = [0] * n
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
queue = deque([i for i in range(n) if in_degree[i] == 0])
processed = 0
while queue:
node = queue.popleft()
processed += 1
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
# If we couldn't process all vertices, there's a cycle
return processed != n
Java:
public boolean hasCycleKahn(int n, int[][] edges) {
/**
* Detect cycle using Kahn's algorithm
* Time: O(V + E)
* Space: O(V)
*/
List<List<Integer>> graph = new ArrayList<>();
int[] inDegree = new int[n];
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
inDegree[edge[1]]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (inDegree[i] == 0) {
queue.offer(i);
}
}
int processed = 0;
while (!queue.isEmpty()) {
int node = queue.poll();
processed++;
for (int neighbor : graph.get(node)) {
inDegree[neighbor]--;
if (inDegree[neighbor] == 0) {
queue.offer(neighbor);
}
}
}
return processed != n;
}
Go:
// hasCycleKahn - Detect cycle using Kahn's algorithm
// Time: O(V + E)
// Space: O(V)
func hasCycleKahn(n int, edges [][]int) bool {
graph := make([][]int, n)
inDegree := make([]int, n)
for _, edge := range edges {
graph[edge[0]] = append(graph[edge[0]], edge[1])
inDegree[edge[1]]++
}
queue := []int{}
for i := 0; i < n; i++ {
if inDegree[i] == 0 {
queue = append(queue, i)
}
}
processed := 0
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
processed++
for _, neighbor := range graph[node] {
inDegree[neighbor]--
if inDegree[neighbor] == 0 {
queue = append(queue, neighbor)
}
}
}
return processed != n
}
JavaScript:
/**
* Detect cycle using Kahn's algorithm
* Time: O(V + E)
* Space: O(V)
*/
function hasCycleKahn(n, edges) {
const graph = Array(n).fill().map(() => []);
const inDegree = new Array(n).fill(0);
for (const [u, v] of edges) {
graph[u].push(v);
inDegree[v]++;
}
const queue = [];
for (let i = 0; i < n; i++) {
if (inDegree[i] === 0) {
queue.push(i);
}
}
let processed = 0;
while (queue.length > 0) {
const node = queue.shift();
processed++;
for (const neighbor of graph[node]) {
inDegree[neighbor]--;
if (inDegree[neighbor] === 0) {
queue.push(neighbor);
}
}
}
return processed !== n;
}
C#:
public bool HasCycleKahn(int n, int[][] edges) {
/// <summary>
/// Detect cycle using Kahn's algorithm
/// Time: O(V + E)
/// Space: O(V)
/// </summary>
List<int>[] graph = new List<int>[n];
int[] inDegree = new int[n];
for (int i = 0; i < n; i++) {
graph[i] = new List<int>();
}
foreach (var edge in edges) {
graph[edge[0]].Add(edge[1]);
inDegree[edge[1]]++;
}
Queue<int> queue = new Queue<int>();
for (int i = 0; i < n; i++) {
if (inDegree[i] == 0) {
queue.Enqueue(i);
}
}
int processed = 0;
while (queue.Count > 0) {
int node = queue.Dequeue();
processed++;
foreach (int neighbor in graph[node]) {
inDegree[neighbor]--;
if (inDegree[neighbor] == 0) {
queue.Enqueue(neighbor);
}
}
}
return processed != n;
}
Key Insights
- Three-Color DFS: White-Gray-Black coloring elegantly tracks vertex states during DFS
- Recursion Stack: Detecting back edges to vertices in current path indicates cycles
- Topological Sort: A DAG can be topologically sorted; presence of cycle prevents this
- Directed vs Undirected: In directed graphs, we don’t need parent tracking unlike undirected graphs
Edge Cases
- Empty graph: No edges means no cycles
- Self-loop: Single edge from vertex to itself is a cycle
- Disconnected graph: Must check all components
- Single vertex: No cycle possible without edges
- Strongly connected component: All vertices in SCC form cycles
Common Mistakes
- Confusing with undirected graph: Not recognizing that directed cycles require following edge directions
- Not resetting recursion stack: Forgetting to mark vertices as not in stack after DFS
- Missing disconnected components: Only checking from vertex 0
- Incorrect color transitions: Not following White → Gray → Black properly
Follow-up Questions
- Find all cycles: How would you enumerate all simple cycles?
- Shortest cycle: Find the shortest cycle in the graph
- Strongly Connected Components: How to find all SCCs using cycle detection?
- Remove edges to make DAG: Minimum edges to remove to eliminate all cycles
- Longest path in DAG: If no cycle, find the longest path