Language Selection
Choose your preferred programming language
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
Note: on Windows, CPython’s default C stack can overflow at around 3,500-4,000 frames even with a raised recursion limit, so the recursive Python hasCycle can crash on a long path (up to 10^4 vertices here). Use the iterative version (hasCycleIterative) for inputs that deep.
Python:
import sys
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
# Recursion depth can reach n on a long path
sys.setrecursionlimit(max(sys.getrecursionlimit(), n + 100))
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) {
// Explicit stack of frames {node, parent, next neighbor index} replaces recursion,
// so a long path cannot overflow the call stack; neighbors are visited in the same order
Deque<int[]> stack = new ArrayDeque<>();
visited[node] = true;
stack.push(new int[]{node, parent, 0});
while (!stack.isEmpty()) {
int[] frame = stack.peek();
List<Integer> neighbors = graph.get(frame[0]);
if (frame[2] == neighbors.size()) {
stack.pop();
continue;
}
int neighbor = neighbors.get(frame[2]++);
if (!visited[neighbor]) {
visited[neighbor] = true;
stack.push(new int[]{neighbor, frame[0], 0});
} else if (neighbor != frame[1]) {
// 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) {
// Explicit stack of frames [node, parent, next neighbor index] replaces recursion,
// so a long path cannot overflow the call stack; neighbors are visited in the same order
visited[node] = true;
const stack = [[node, parent, 0]];
while (stack.length > 0) {
const frame = stack[stack.length - 1];
const neighbors = graph[frame[0]];
if (frame[2] === neighbors.length) {
stack.pop();
continue;
}
const neighbor = neighbors[frame[2]++];
if (!visited[neighbor]) {
visited[neighbor] = true;
stack.push([neighbor, frame[0], 0]);
} else if (neighbor !== frame[1]) {
// 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) {
// Explicit stack of frames {node, parent, next neighbor index} replaces recursion,
// so a long path cannot overflow the call stack; neighbors are visited in the same order
Stack<int[]> stack = new Stack<int[]>();
visited[node] = true;
stack.Push(new int[] { node, parent, 0 });
while (stack.Count > 0) {
int[] frame = stack.Peek();
List<int> neighbors = graph[frame[0]];
if (frame[2] == neighbors.Count) {
stack.Pop();
continue;
}
int neighbor = neighbors[frame[2]++];
if (!visited[neighbor]) {
visited[neighbor] = true;
stack.Push(new int[] { neighbor, frame[0], 0 });
} else if (neighbor != frame[1]) {
// 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;
}
}
C++:
#include <array>
#include <stack>
#include <utility>
#include <vector>
class Solution {
public:
// Detect cycle using DFS
// Time: O(V + E), Space: O(V)
bool hasCycle(int n, const std::vector<std::vector<int>>& edges) {
std::vector<std::vector<int>> graph = buildGraph(n, edges);
std::vector<bool> visited(n, false);
// Check all components
for (int i = 0; i < n; ++i) {
if (!visited[i] && dfs(graph, i, -1, visited)) {
return true;
}
}
return false;
}
// Detect cycle using iterative DFS
// Time: O(V + E), Space: O(V)
bool hasCycleIterative(int n, const std::vector<std::vector<int>>& edges) {
std::vector<std::vector<int>> graph = buildGraph(n, edges);
std::vector<bool> visited(n, false);
for (int start = 0; start < n; ++start) {
if (visited[start]) continue;
std::stack<std::pair<int, int>> stack; // (node, parent)
stack.push({start, -1});
while (!stack.empty()) {
auto [node, parent] = stack.top();
stack.pop();
if (visited[node]) continue;
visited[node] = true;
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
stack.push({neighbor, node});
} else if (neighbor != parent) {
return true;
}
}
}
}
return false;
}
private:
// Build adjacency list
static std::vector<std::vector<int>> buildGraph(int n,
const std::vector<std::vector<int>>& edges) {
std::vector<std::vector<int>> graph(n);
for (const auto& edge : edges) {
graph[edge[0]].push_back(edge[1]);
graph[edge[1]].push_back(edge[0]);
}
return graph;
}
bool dfs(const std::vector<std::vector<int>>& graph, int node, int parent,
std::vector<bool>& visited) {
// Explicit stack of frames {node, parent, next neighbor index} replaces recursion,
// so a long path cannot overflow the call stack; neighbors are visited in the same order
std::vector<std::array<int, 3>> stack;
visited[node] = true;
stack.push_back({node, parent, 0});
while (!stack.empty()) {
std::array<int, 3>& frame = stack.back();
const std::vector<int>& neighbors = graph[frame[0]];
if (frame[2] == static_cast<int>(neighbors.size())) {
stack.pop_back();
continue;
}
int neighbor = neighbors[frame[2]++];
if (!visited[neighbor]) {
visited[neighbor] = true;
int current = frame[0]; // copy first: push_back may invalidate frame
stack.push_back({neighbor, current, 0});
} else if (neighbor != frame[1]) {
// Found a back edge (cycle)
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:
import java.util.*;
class Solution {
/**
* Detect cycle using BFS
* Time: O(V + E)
* Space: O(V)
*/
public boolean hasCycleBFS(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;
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#:
using System.Collections.Generic;
public class Solution {
/// <summary>
/// Detect cycle using BFS
/// Time: O(V + E)
/// Space: O(V)
/// </summary>
public bool HasCycleBFS(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;
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;
}
}
C++:
#include <queue>
#include <utility>
#include <vector>
class Solution {
public:
// Detect cycle using BFS
// Time: O(V + E), Space: O(V)
bool hasCycleBFS(int n, const std::vector<std::vector<int>>& edges) {
std::vector<std::vector<int>> graph(n);
for (const auto& edge : edges) {
graph[edge[0]].push_back(edge[1]);
graph[edge[1]].push_back(edge[0]);
}
std::vector<bool> visited(n, false);
for (int start = 0; start < n; ++start) {
if (visited[start]) continue;
std::queue<std::pair<int, int>> queue; // (node, parent)
queue.push({start, -1});
visited[start] = true;
while (!queue.empty()) {
auto [node, parent] = queue.front();
queue.pop();
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.push({neighbor, node});
} else if (neighbor != parent) {
// Visited vertex that is not the parent: cycle
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;
}
}
class Solution {
/**
* Detect cycle using Union-Find
* Time: O(E * α(V))
* Space: O(V)
*/
public boolean hasCycleUnionFind(int n, int[][] edges) {
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 class Solution {
/// <summary>
/// Detect cycle using Union-Find
/// Time: O(E * α(V))
/// Space: O(V)
/// </summary>
public bool HasCycleUnionFind(int n, int[][] edges) {
UnionFind uf = new UnionFind(n);
foreach (var edge in edges) {
if (!uf.Union(edge[0], edge[1])) {
return true;
}
}
return false;
}
}
C++:
#include <numeric>
#include <utility>
#include <vector>
class UnionFind {
public:
explicit UnionFind(int n) : parent(n), rank(n, 0) {
std::iota(parent.begin(), parent.end(), 0);
}
int find(int x) {
// Path compression; union by rank keeps the depth O(log n)
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
bool unite(int x, int y) {
int px = find(x);
int py = find(y);
if (px == py) return false; // Already in same set
// Union by rank: attach the shorter tree under the taller one
if (rank[px] < rank[py]) {
std::swap(px, py);
}
parent[py] = px;
if (rank[px] == rank[py]) {
++rank[px];
}
return true;
}
private:
std::vector<int> parent;
std::vector<int> rank;
};
class Solution {
public:
// Detect cycle using Union-Find
// Time: O(E * α(V)), Space: O(V)
bool hasCycleUnionFind(int n, const std::vector<std::vector<int>>& edges) {
UnionFind uf(n);
for (const auto& edge : edges) {
if (!uf.unite(edge[0], edge[1])) {
return true; // Cycle detected
}
}
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?