Detect a Cycle in a Graph: Directed and Undirected

Cycle detection is asked in interviews at Google, Meta, Amazon, and anywhere that tests graphs. The classic application is deadlock detection in operating systems and dependency validation in build systems. The approach differs significantly between directed and undirected graphs.

Undirected Graph: Union-Find

For undirected graphs, a cycle exists if adding an edge connects two nodes that are already in the same connected component.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        # Path compression
        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 connected — adding this edge creates a cycle
        # Union by rank
        if self.rank[px]  bool:
    """
    Detect cycle in undirected graph.
    n: number of nodes (0-indexed)
    edges: list of (u, v) pairs
    Time: O(E * alpha(V)) where alpha is inverse Ackermann (nearly O(1))
    """
    uf = UnionFind(n)
    for u, v in edges:
        if not uf.union(u, v):
            return True  # Cycle detected
    return False

Undirected Graph: DFS with Parent Tracking

def has_cycle_undirected_dfs(graph: dict) -> bool:
    """
    DFS-based cycle detection for undirected graph.
    Key: track parent to avoid treating the edge we came from as a back edge.
    """
    visited = set()

    def dfs(node, parent):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                if dfs(neighbor, node):
                    return True
            elif neighbor != parent:
                # Found a visited node that isn't our parent — back edge = cycle
                return True
        return False

    # Handle disconnected graphs
    for node in graph:
        if node not in visited:
            if dfs(node, -1):
                return True
    return False

Directed Graph: DFS with Three-Color Marking

For directed graphs, we need to distinguish between:

Unvisited nodes (WHITE)
Nodes in the current DFS path (GRAY) — a back edge to GRAY means a cycle
Fully processed nodes (BLACK) — safe, no cycle through these

def has_cycle_directed(graph: dict) -> bool:
    """
    Three-color DFS for cycle detection in directed graph.
    Also the foundation for topological sort.
    Time: O(V + E), Space: O(V)
    """
    # 0 = WHITE (unvisited), 1 = GRAY (in stack), 2 = BLACK (done)
    color = {node: 0 for node in graph}

    def dfs(node):
        color[node] = 1  # GRAY: currently being processed

        for neighbor in graph[node]:
            if color[neighbor] == 1:
                return True  # Back edge to node in current path = cycle
            if color[neighbor] == 0:
                if dfs(neighbor):
                    return True

        color[node] = 2  # BLACK: fully processed, no cycle through here
        return False

    for node in graph:
        if color[node] == 0:
            if dfs(node):
                return True
    return False

# Example: Course schedule (LeetCode 207)
def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool:
    """
    Can you complete all courses given prerequisites?
    This is equivalent to: does the prerequisite graph have a cycle?
    """
    graph = {i: [] for i in range(num_courses)}
    for course, prereq in prerequisites:
        graph[prereq].append(course)

    return not has_cycle_directed(graph)

Directed Graph: Kahn’s Algorithm (BFS-based)

from collections import deque

def has_cycle_directed_bfs(n: int, edges: list[tuple]) -> bool:
    """
    Kahn's algorithm: if topological sort processes all V nodes, no cycle exists.
    Indegree of 0 = no prerequisites = safe to process next.
    """
    graph = [[] for _ in range(n)]
    indegree = [0] * n

    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1

    # Start with all nodes that have no incoming edges
    queue = deque([i for i in range(n) if indegree[i] == 0])
    processed = 0

    while queue:
        node = queue.popleft()
        processed += 1
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    # If we couldn't process all nodes, some are stuck in a cycle
    return processed != n

When to Use Which Approach

Graph type	Preferred method	When to use alternative
Undirected	Union-Find	DFS if you need the actual cycle path
Directed	DFS three-color	Kahn’s if you also need topological order
Very large, edges streamed	Union-Find (undirected)	DFS requires building full adjacency list first

Complexity

Union-Find: O(E · α(V)) ≈ O(E) with path compression and union by rank
DFS three-color: O(V + E) time, O(V) space
Kahn’s algorithm: O(V + E) time, O(V) space

Practice Problems

LeetCode 207: Course Schedule (directed cycle detection)
LeetCode 261: Graph Valid Tree (undirected, using Union-Find)
LeetCode 684: Redundant Connection (first edge that creates a cycle)
LeetCode 802: Find Eventual Safe States (nodes not in any cycle)