Language Selection
Choose your preferred programming language
Showing: Python
Problem Statement
Given an undirected graph, determine if it contains a cycle. A cycle exists in an undirected graph if we can start from a vertex and return to it by traversing edges without reusing any edge.
Input:
- Number of vertices
n(labeled 0 to n-1) - List of edges where each edge is represented as [u, v]
Output:
- Boolean indicating whether the graph contains a cycle
Constraints:
- 1 ≤ n ≤ 10^4
- 0 ≤ edges.length ≤ 10^4
- No self-loops or multiple edges between same vertices
- Graph may be disconnected
Examples:
Example 1:
Input: n = 5, edges = [[0, 1], [1, 2], [2, 3], [3, 4], [4, 1]]
Output: true
Explanation: There's a cycle: 1 -> 2 -> 3 -> 4 -> 1
Example 2:
Input: n = 4, edges = [[0, 1], [1, 2], [2, 3]]
Output: false
Explanation: The graph is a tree with no cycles
Example 3:
Input: n = 5, edges = [[0, 1], [2, 3], [3, 4], [4, 2]]
Output: true
Explanation: Disconnected graph with cycle in second component: 2 -> 3 -> 4 -> 2
Solutions
Approach 1: DFS-Based Cycle Detection
Use DFS to traverse the graph, keeping track of the parent to avoid considering the edge we came from.
Algorithm:
- Build adjacency list from edges
- For each unvisited vertex, start DFS
- During DFS, if we visit a vertex that’s already visited and is not the parent, we found a cycle
- Return true if cycle found, false otherwise
Python:
def hasCycle(n, edges):
"""
Detect cycle using DFS
Time: O(V + E)
Space: O(V)
"""
# Build adjacency list
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = [False] * n
def dfs(node, parent):
visited[node] = True
for neighbor in graph[node]:
if not visited[neighbor]:
if dfs(neighbor, node):
return True
elif neighbor != parent:
# Found a back edge (cycle)
return True
return False
# Check all components
for i in range(n):
if not visited[i]:
if dfs(i, -1):
return True
return False
def hasCycleIterative(n, edges):
"""
Detect cycle using iterative DFS
Time: O(V + E)
Space: O(V)
"""
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = [False] * n
for start in range(n):
if visited[start]:
continue
stack = [(start, -1)]
while stack:
node, parent = stack.pop()
if visited[node]:
continue
visited[node] = True
for neighbor in graph[node]:
if not visited[neighbor]:
stack.append((neighbor, node))
elif neighbor != parent:
return True
return False
Java:
import java.util.*;
class Solution {
/**
* Detect cycle using DFS
* Time: O(V + E)
* Space: O(V)
*/
public boolean hasCycle(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]);
graph.get(edge[1]).add(edge[0]);
}
boolean[] visited = new boolean[n];
// Check all components
for (int i = 0; i < n; i++) {
if (!visited[i]) {
if (dfs(graph, i, -1, visited)) {
return true;
}
}
}
return false;
}
private boolean dfs(List<List<Integer>> graph, int node, int parent, boolean[] visited) {
visited[node] = true;
for (int neighbor : graph.get(node)) {
if (!visited[neighbor]) {
if (dfs(graph, neighbor, node, visited)) {
return true;
}
} else if (neighbor != parent) {
// Found a back edge (cycle)
return true;
}
}
return false;
}
/**
* Detect cycle using iterative DFS
* Time: O(V + E)
* Space: O(V)
*/
public boolean hasCycleIterative(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]);
graph.get(edge[1]).add(edge[0]);
}
boolean[] visited = new boolean[n];
for (int start = 0; start < n; start++) {
if (visited[start]) continue;
Stack<int[]> stack = new Stack<>();
stack.push(new int[]{start, -1});
while (!stack.isEmpty()) {
int[] current = stack.pop();
int node = current[0];
int parent = current[1];
if (visited[node]) continue;
visited[node] = true;
for (int neighbor : graph.get(node)) {
if (!visited[neighbor]) {
stack.push(new int[]{neighbor, node});
} else if (neighbor != parent) {
return true;
}
}
}
}
return false;
}
}
Go:
// hasCycle - Detect cycle using DFS
// Time: O(V + E)
// Space: O(V)
func hasCycle(n int, edges [][]int) bool {
// Build adjacency list
graph := make([][]int, n)
for _, edge := range edges {
u, v := edge[0], edge[1]
graph[u] = append(graph[u], v)
graph[v] = append(graph[v], u)
}
visited := make([]bool, n)
var dfs func(node, parent int) bool
dfs = func(node, parent int) bool {
visited[node] = true
for _, neighbor := range graph[node] {
if !visited[neighbor] {
if dfs(neighbor, node) {
return true
}
} else if neighbor != parent {
// Found a back edge (cycle)
return true
}
}
return false
}
// Check all components
for i := 0; i < n; i++ {
if !visited[i] {
if dfs(i, -1) {
return true
}
}
}
return false
}
// hasCycleIterative - Detect cycle using iterative DFS
// Time: O(V + E)
// Space: O(V)
func hasCycleIterative(n int, edges [][]int) bool {
graph := make([][]int, n)
for _, edge := range edges {
u, v := edge[0], edge[1]
graph[u] = append(graph[u], v)
graph[v] = append(graph[v], u)
}
visited := make([]bool, n)
for start := 0; start < n; start++ {
if visited[start] {
continue
}
type NodeParent struct {
node, parent int
}
stack := []NodeParent{{start, -1}}
for len(stack) > 0 {
current := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if visited[current.node] {
continue
}
visited[current.node] = true
for _, neighbor := range graph[current.node] {
if !visited[neighbor] {
stack = append(stack, NodeParent{neighbor, current.node})
} else if neighbor != current.parent {
return true
}
}
}
}
return false
}
JavaScript:
/**
* Detect cycle using DFS
* Time: O(V + E)
* Space: O(V)
*/
function hasCycle(n, edges) {
// Build adjacency list
const graph = Array(n).fill().map(() => []);
for (const [u, v] of edges) {
graph[u].push(v);
graph[v].push(u);
}
const visited = new Array(n).fill(false);
function dfs(node, parent) {
visited[node] = true;
for (const neighbor of graph[node]) {
if (!visited[neighbor]) {
if (dfs(neighbor, node)) {
return true;
}
} else if (neighbor !== parent) {
// Found a back edge (cycle)
return true;
}
}
return false;
}
// Check all components
for (let i = 0; i < n; i++) {
if (!visited[i]) {
if (dfs(i, -1)) {
return true;
}
}
}
return false;
}
/**
* Detect cycle using iterative DFS
* Time: O(V + E)
* Space: O(V)
*/
function hasCycleIterative(n, edges) {
const graph = Array(n).fill().map(() => []);
for (const [u, v] of edges) {
graph[u].push(v);
graph[v].push(u);
}
const visited = new Array(n).fill(false);
for (let start = 0; start < n; start++) {
if (visited[start]) continue;
const stack = [[start, -1]];
while (stack.length > 0) {
const [node, parent] = stack.pop();
if (visited[node]) continue;
visited[node] = true;
for (const neighbor of graph[node]) {
if (!visited[neighbor]) {
stack.push([neighbor, node]);
} else if (neighbor !== parent) {
return true;
}
}
}
}
return false;
}
C#:
using System;
using System.Collections.Generic;
public class Solution {
/// <summary>
/// Detect cycle using DFS
/// Time: O(V + E)
/// Space: O(V)
/// </summary>
public bool HasCycle(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]);
graph[edge[1]].Add(edge[0]);
}
bool[] visited = new bool[n];
// Check all components
for (int i = 0; i < n; i++) {
if (!visited[i]) {
if (Dfs(graph, i, -1, visited)) {
return true;
}
}
}
return false;
}
private bool Dfs(List<int>[] graph, int node, int parent, bool[] visited) {
visited[node] = true;
foreach (int neighbor in graph[node]) {
if (!visited[neighbor]) {
if (Dfs(graph, neighbor, node, visited)) {
return true;
}
} else if (neighbor != parent) {
// Found a back edge (cycle)
return true;
}
}
return false;
}
/// <summary>
/// Detect cycle using iterative DFS
/// Time: O(V + E)
/// Space: O(V)
/// </summary>
public bool HasCycleIterative(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]);
graph[edge[1]].Add(edge[0]);
}
bool[] visited = new bool[n];
for (int start = 0; start < n; start++) {
if (visited[start]) continue;
Stack<(int node, int parent)> stack = new Stack<(int, int)>();
stack.Push((start, -1));
while (stack.Count > 0) {
var (node, parent) = stack.Pop();
if (visited[node]) continue;
visited[node] = true;
foreach (int neighbor in graph[node]) {
if (!visited[neighbor]) {
stack.Push((neighbor, node));
} else if (neighbor != parent) {
return true;
}
}
}
}
return false;
}
}
Approach 2: BFS-Based Cycle Detection
Use BFS to detect cycles by tracking parent relationships.
Python:
from collections import deque
def hasCycleBFS(n, edges):
"""
Detect cycle using BFS
Time: O(V + E)
Space: O(V)
"""
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = [False] * n
for start in range(n):
if visited[start]:
continue
queue = deque([(start, -1)])
visited[start] = True
while queue:
node, parent = queue.popleft()
for neighbor in graph[node]:
if not visited[neighbor]:
visited[neighbor] = True
queue.append((neighbor, node))
elif neighbor != parent:
return True
return False
Java:
public boolean hasCycleBFS(int n, int[][] edges) {
/**
* Detect cycle using BFS
* 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]);
graph.get(edge[1]).add(edge[0]);
}
boolean[] visited = new boolean[n];
for (int start = 0; start < n; start++) {
if (visited[start]) continue;
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{start, -1});
visited[start] = true;
while (!queue.isEmpty()) {
int[] current = queue.poll();
int node = current[0];
int parent = current[1];
for (int neighbor : graph.get(node)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.offer(new int[]{neighbor, node});
} else if (neighbor != parent) {
return true;
}
}
}
}
return false;
}
Go:
// hasCycleBFS - Detect cycle using BFS
// Time: O(V + E)
// Space: O(V)
func hasCycleBFS(n int, edges [][]int) bool {
graph := make([][]int, n)
for _, edge := range edges {
u, v := edge[0], edge[1]
graph[u] = append(graph[u], v)
graph[v] = append(graph[v], u)
}
visited := make([]bool, n)
for start := 0; start < n; start++ {
if visited[start] {
continue
}
type NodeParent struct {
node, parent int
}
queue := []NodeParent{{start, -1}}
visited[start] = true
for len(queue) > 0 {
current := queue[0]
queue = queue[1:]
for _, neighbor := range graph[current.node] {
if !visited[neighbor] {
visited[neighbor] = true
queue = append(queue, NodeParent{neighbor, current.node})
} else if neighbor != current.parent {
return true
}
}
}
}
return false
}
JavaScript:
/**
* Detect cycle using BFS
* Time: O(V + E)
* Space: O(V)
*/
function hasCycleBFS(n, edges) {
const graph = Array(n).fill().map(() => []);
for (const [u, v] of edges) {
graph[u].push(v);
graph[v].push(u);
}
const visited = new Array(n).fill(false);
for (let start = 0; start < n; start++) {
if (visited[start]) continue;
const queue = [[start, -1]];
visited[start] = true;
while (queue.length > 0) {
const [node, parent] = queue.shift();
for (const neighbor of graph[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.push([neighbor, node]);
} else if (neighbor !== parent) {
return true;
}
}
}
}
return false;
}
C#:
public bool HasCycleBFS(int n, int[][] edges) {
/// <summary>
/// Detect cycle using BFS
/// 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]);
graph[edge[1]].Add(edge[0]);
}
bool[] visited = new bool[n];
for (int start = 0; start < n; start++) {
if (visited[start]) continue;
Queue<(int node, int parent)> queue = new Queue<(int, int)>();
queue.Enqueue((start, -1));
visited[start] = true;
while (queue.Count > 0) {
var (node, parent) = queue.Dequeue();
foreach (int neighbor in graph[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.Enqueue((neighbor, node));
} else if (neighbor != parent) {
return true;
}
}
}
}
return false;
}
Approach 3: Union-Find (Disjoint Set Union)
Use Union-Find to detect cycles by checking if two vertices of an edge are already in the same set.
Python:
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False # Already in same set
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
return True
def hasCycleUnionFind(n, edges):
"""
Detect cycle using Union-Find
Time: O(E * α(V)) where α is the inverse Ackermann function
Space: O(V)
"""
uf = UnionFind(n)
for u, v in edges:
if not uf.union(u, v):
return True # Cycle detected
return False
Java:
class UnionFind {
private int[] parent;
private int[] rank;
public UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
public boolean union(int x, int y) {
int px = find(x);
int py = find(y);
if (px == py) return false;
if (rank[px] < rank[py]) {
int temp = px;
px = py;
py = temp;
}
parent[py] = px;
if (rank[px] == rank[py]) {
rank[px]++;
}
return true;
}
}
public boolean hasCycleUnionFind(int n, int[][] edges) {
/**
* Detect cycle using Union-Find
* Time: O(E * α(V))
* Space: O(V)
*/
UnionFind uf = new UnionFind(n);
for (int[] edge : edges) {
if (!uf.union(edge[0], edge[1])) {
return true;
}
}
return false;
}
Go:
type UnionFind struct {
parent []int
rank []int
}
func NewUnionFind(n int) *UnionFind {
parent := make([]int, n)
rank := make([]int, n)
for i := 0; i < n; i++ {
parent[i] = i
}
return &UnionFind{parent, rank}
}
func (uf *UnionFind) find(x int) int {
if uf.parent[x] != x {
uf.parent[x] = uf.find(uf.parent[x])
}
return uf.parent[x]
}
func (uf *UnionFind) union(x, y int) bool {
px, py := uf.find(x), uf.find(y)
if px == py {
return false
}
if uf.rank[px] < uf.rank[py] {
px, py = py, px
}
uf.parent[py] = px
if uf.rank[px] == uf.rank[py] {
uf.rank[px]++
}
return true
}
// hasCycleUnionFind - Detect cycle using Union-Find
// Time: O(E * α(V))
// Space: O(V)
func hasCycleUnionFind(n int, edges [][]int) bool {
uf := NewUnionFind(n)
for _, edge := range edges {
if !uf.union(edge[0], edge[1]) {
return true
}
}
return false
}
JavaScript:
class UnionFind {
constructor(n) {
this.parent = Array(n).fill().map((_, i) => i);
this.rank = Array(n).fill(0);
}
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]);
}
return this.parent[x];
}
union(x, y) {
let px = this.find(x);
let py = this.find(y);
if (px === py) return false;
if (this.rank[px] < this.rank[py]) {
[px, py] = [py, px];
}
this.parent[py] = px;
if (this.rank[px] === this.rank[py]) {
this.rank[px]++;
}
return true;
}
}
/**
* Detect cycle using Union-Find
* Time: O(E * α(V))
* Space: O(V)
*/
function hasCycleUnionFind(n, edges) {
const uf = new UnionFind(n);
for (const [u, v] of edges) {
if (!uf.union(u, v)) {
return true;
}
}
return false;
}
C#:
public class UnionFind {
private int[] parent;
private int[] rank;
public UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int Find(int x) {
if (parent[x] != x) {
parent[x] = Find(parent[x]);
}
return parent[x];
}
public bool Union(int x, int y) {
int px = Find(x);
int py = Find(y);
if (px == py) return false;
if (rank[px] < rank[py]) {
int temp = px;
px = py;
py = temp;
}
parent[py] = px;
if (rank[px] == rank[py]) {
rank[px]++;
}
return true;
}
}
public bool HasCycleUnionFind(int n, int[][] edges) {
/// <summary>
/// Detect cycle using Union-Find
/// Time: O(E * α(V))
/// Space: O(V)
/// </summary>
UnionFind uf = new UnionFind(n);
foreach (var edge in edges) {
if (!uf.Union(edge[0], edge[1])) {
return true;
}
}
return false;
}
Key Insights
- Parent Tracking: In undirected graphs, we need to track parent to avoid false positives from bidirectional edges
- Disconnected Components: Must check all components as cycle might exist in any component
- Union-Find Efficiency: Union-Find is particularly efficient for dynamic graphs where edges are added incrementally
- Back Edge Detection: A cycle exists if we find a back edge (edge to an already visited vertex that’s not the parent)
Edge Cases
- Empty graph: No edges, no cycles
- Single vertex: No cycles possible
- Self-loop: Would be a cycle (but constraint says no self-loops)
- Disconnected graph: Cycle might exist in any component
- Tree structure: Exactly n-1 edges for n vertices with no cycles
- Multiple components with cycles: Return true if any component has a cycle
Common Mistakes
- Not tracking parent: In undirected graphs, not tracking parent leads to false positives
- Not checking all components: Missing cycles in disconnected components
- Incorrect visited state management: Not properly tracking visited vertices
- Union-Find rank optimization: Forgetting path compression or union by rank
Follow-up Questions
- Find all cycles: How would you find and return all cycles in the graph?
- Shortest cycle: How would you find the shortest cycle length?
- Remove edge to eliminate cycle: Which edge would you remove to make the graph acyclic?
- Count cycles: How many distinct cycles are in the graph?
- Directed graph: How would the algorithm change for directed graphs?