Graph Cycle Detection: DFS, Coloring, and Union-Find

Cycle detection is one of the most fundamental graph problems. It shows up everywhere: deadlock detection in operating systems, dependency resolution in build systems, detecting infinite loops in state machines, and validating that a course prerequisite structure is consistent.

The approach differs depending on whether the graph is directed or undirected. In an undirected graph, a simple DFS that tracks the parent of each node is sufficient. In a directed graph, you need the three-color (white/gray/black) approach because an edge to an already-visited node does not necessarily form a cycle.

Why Directed and Undirected Graphs Need Different Approaches

In an undirected graph, every edge goes both ways. If you are doing DFS from node A and reach node B, and B has already been visited, you know there is a cycle as long as B is not the node you just came from (the parent). The parent check is necessary because in an undirected graph, the edge A-B means both A to B and B to A exist.

In a directed graph, visiting an already-visited node does not always mean a cycle. Consider three nodes: A points to B, A points to C, and B points to C. When you DFS from A, you visit B, then C. Back at A, you try C but C is already visited. There is no cycle, just two paths converging on C. To detect a real cycle, you need to know whether C is currently on the DFS recursion stack, not just whether it has been visited at all.

Method 1: Undirected Graph Cycle Detection with DFS + Parent

The simplest approach for undirected graphs. During DFS, pass the parent of each node. If you encounter a neighbor that is already visited and it is not the parent, you have found a cycle.

def has_cycle_undirected(graph):
    """
    Detect cycle in an undirected graph using DFS.
    graph: dict mapping node -> list of neighbors
    Returns True if cycle exists.
    """
    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:
                # Visited neighbor that is not the parent => cycle
                return True
        return False

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

Let us trace through an example to see how this works.

# Graph: 0-1, 1-2, 2-0 (triangle, has cycle)
graph_with_cycle = {
    0: [1, 2],
    1: [0, 2],
    2: [1, 0]
}

# Graph: 0-1, 1-2 (path, no cycle)
graph_no_cycle = {
    0: [1],
    1: [0, 2],
    2: [1]
}

print(has_cycle_undirected(graph_with_cycle))  # True
print(has_cycle_undirected(graph_no_cycle))    # False

Trace for the Triangle Graph

Starting DFS from node 0 with parent -1. Visit 0, then go to neighbor 1 with parent 0. Visit 1, then go to neighbor 0, but 0 is visited and it is the parent, so skip. Go to neighbor 2 with parent 1. Visit 2, then check neighbor 1. Node 1 is visited and it is the parent, so skip. Check neighbor 0. Node 0 is visited and it is NOT the parent (parent is 1). Found a cycle, return True.

Time and Space Complexity

• Time: O(V + E) because we visit every node and edge once
• Space: O(V) for the visited set and recursion stack

Handling Parallel Edges

If the graph can have multiple edges between the same pair of nodes, the simple parent check breaks. With two edges between A and B, traveling from A to B and back to A via the second edge is a valid cycle. To handle this, track the edge index rather than the parent node.

def has_cycle_with_parallel_edges(adj, num_nodes):
    """
    adj: list of (u, v) edges (undirected)
    Handles parallel edges by tracking edge indices.
    """
    # Build adjacency with edge indices
    graph = [[] for _ in range(num_nodes)]
    for idx, (u, v) in enumerate(adj):
        graph[u].append((v, idx))
        graph[v].append((u, idx))

    visited = [False] * num_nodes

    def dfs(node, parent_edge):
        visited[node] = True
        for neighbor, edge_idx in graph[node]:
            if not visited[neighbor]:
                if dfs(neighbor, edge_idx):
                    return True
            elif edge_idx != parent_edge:
                return True
        return False

    for i in range(num_nodes):
        if not visited[i]:
            if dfs(i, -1):
                return True
    return False

Method 2: Directed Graph Cycle Detection with Three-Color DFS

For directed graphs, we use the white-gray-black coloring scheme. Every node starts as white (unvisited). When we begin processing a node, we color it gray (in progress, on the current DFS path). When we finish processing all its descendants, we color it black (done).

A cycle exists if and only if we encounter a gray node during DFS. A gray node means it is on the current recursion path, and reaching it again means we have found a back edge forming a cycle.

def has_cycle_directed(graph):
    """
    Detect cycle in a directed graph using three-color DFS.
    graph: dict mapping node -> list of neighbors (directed edges)
    Returns True if cycle exists.
    """
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {node: WHITE for node in graph}

    def dfs(node):
        color[node] = GRAY
        for neighbor in graph[node]:
            if color[neighbor] == GRAY:
                # Back edge: neighbor is on current path
                return True
            if color[neighbor] == WHITE:
                if dfs(neighbor):
                    return True
        color[node] = BLACK
        return False

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

Finding the Actual Cycle Path

Often you need not just whether a cycle exists but the actual nodes forming it.

def find_cycle_directed(graph):
    """
    Find and return the actual cycle in a directed graph.
    Returns a list of nodes forming the cycle, or empty list.
    """
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {node: WHITE for node in graph}
    parent = {node: None for node in graph}
    cycle = []

    def dfs(node):
        color[node] = GRAY
        for neighbor in graph[node]:
            if color[neighbor] == GRAY:
                # Reconstruct cycle
                path = [neighbor, node]
                current = node
                while parent[current] != neighbor:
                    current = parent[current]
                    path.append(current)
                path.reverse()
                cycle.extend(path)
                return True
            if color[neighbor] == WHITE:
                parent[neighbor] = node
                if dfs(neighbor):
                    return True
        color[node] = BLACK
        return False

    for node in graph:
        if color[node] == WHITE:
            if dfs(node):
                return cycle
    return cycle

Example with Directed Graphs

# Has cycle: A -> B -> C -> A
directed_cycle = {
    'A': ['B'],
    'B': ['C'],
    'C': ['A', 'D'],
    'D': []
}

# No cycle: DAG
dag = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}

print(has_cycle_directed(directed_cycle))  # True
print(has_cycle_directed(dag))             # False

print(find_cycle_directed(directed_cycle))  # ['A', 'B', 'C']

Why Two Colors Are Not Enough for Directed Graphs

Consider a diamond-shaped DAG: A points to B and C, both B and C point to D. If we only track visited/not-visited, when we DFS from A to B to D, D gets marked visited. Then we backtrack to A, go to C, and reach D. D is visited but there is no cycle. With three colors, D would be BLACK when we reach it from C, and we only report a cycle when we hit a GRAY node.

Method 3: Union-Find for Undirected Graphs

Union-Find (Disjoint Set Union) provides an elegant cycle detection for undirected graphs. The idea is simple: process each edge. If both endpoints are already in the same connected component, adding this edge creates a cycle.

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])  # Path compression
        return self.parent[x]

    def union(self, x, y):
        """
        Returns False if x and y are already in the same set (cycle).
        Returns True if successfully merged.
        """
        root_x = self.find(x)
        root_y = self.find(y)

        if root_x == root_y:
            return False  # Cycle detected

        # Union by rank
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
        return True


def has_cycle_union_find(num_nodes, edges):
    """
    Detect cycle in undirected graph using Union-Find.
    edges: list of (u, v) tuples
    """
    uf = UnionFind(num_nodes)
    for u, v in edges:
        if not uf.union(u, v):
            return True
    return False

Example

# Triangle: 0-1, 1-2, 2-0
edges_cycle = [(0, 1), (1, 2), (2, 0)]
print(has_cycle_union_find(3, edges_cycle))  # True

# Path: 0-1, 1-2
edges_no_cycle = [(0, 1), (1, 2)]
print(has_cycle_union_find(3, edges_no_cycle))  # False

Trace for Triangle

Process edge (0, 1): find(0) = 0, find(1) = 1, different roots, union them. Process edge (1, 2): find(1) = 0 (or 1, depends on union direction), find(2) = 2, different roots, union them. Process edge (2, 0): find(2) leads to same root as find(0). Same root means cycle detected, return True.

Time and Space Complexity

• Time: O(E * alpha(V)) which is nearly O(E) because the inverse Ackermann function alpha grows incredibly slowly
• Space: O(V) for the parent and rank arrays

Comparing the Three Methods

Method	Graph Type	Time	Space	Extra Info
DFS + Parent	Undirected	O(V + E)	O(V)	Simplest approach
Three-Color DFS	Directed	O(V + E)	O(V)	Only correct method for directed
Union-Find	Undirected	O(E * alpha(V))	O(V)	Good for edge-list input

When to Use Each Method

DFS + Parent is the go-to choice for undirected graphs when you already have an adjacency list. It is simple, fast, and easy to modify to return the actual cycle.

Three-Color DFS is the only correct choice for directed graphs. The two-color visited/not-visited approach will give false positives on DAGs. This method naturally extends to topological sort (just collect nodes as they turn black).

Union-Find is best when the input is an edge list and you are already using Union-Find for other purposes (like Kruskal’s MST). It avoids building an adjacency list. It also works well in online scenarios where edges are added one at a time and you need to check for cycles after each addition.

Iterative DFS for Large Graphs

Recursive DFS can cause stack overflow for very deep graphs. Here is an iterative version of the three-color approach.

def has_cycle_directed_iterative(graph):
    """
    Iterative three-color DFS for directed graphs.
    Avoids recursion stack overflow on deep graphs.
    """
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {node: WHITE for node in graph}

    for start in graph:
        if color[start] != WHITE:
            continue

        stack = [(start, iter(graph[start]))]
        color[start] = GRAY

        while stack:
            node, neighbors = stack[-1]
            try:
                neighbor = next(neighbors)
                if color[neighbor] == GRAY:
                    return True
                if color[neighbor] == WHITE:
                    color[neighbor] = GRAY
                    stack.append((neighbor, iter(graph[neighbor])))
            except StopIteration:
                color[node] = BLACK
                stack.pop()

    return False

Cycle Detection in Kruskal’s MST

One practical use of Union-Find cycle detection is in Kruskal’s minimum spanning tree algorithm. You sort edges by weight and add them one by one, skipping any edge that would create a cycle.

def kruskal_mst(num_nodes, edges):
    """
    Kruskal's MST using Union-Find for cycle detection.
    edges: list of (weight, u, v)
    Returns list of edges in MST and total weight.
    """
    edges.sort()  # Sort by weight
    uf = UnionFind(num_nodes)
    mst = []
    total_weight = 0

    for weight, u, v in edges:
        if uf.union(u, v):
            mst.append((u, v, weight))
            total_weight += weight
            if len(mst) == num_nodes - 1:
                break

    return mst, total_weight


# Example
edges = [(4, 0, 1), (8, 0, 7), (1, 1, 2), (2, 1, 7),
         (7, 2, 3), (4, 2, 5), (6, 3, 4), (9, 3, 5)]
mst, weight = kruskal_mst(8, edges)
print(f"MST weight: {weight}")
print(f"MST edges: {mst}")

Detecting All Cycles (Not Just One)

Sometimes you need to find all cycles in a graph, not just detect whether one exists.

def find_all_cycles_undirected(graph):
    """
    Find all fundamental cycles in an undirected graph.
    Uses DFS and back edges to identify cycle bases.
    """
    visited = set()
    parent = {}
    cycles = []

    def dfs(node, par):
        visited.add(node)
        parent[node] = par

        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor, node)
            elif neighbor != par and neighbor in visited:
                # Found a back edge, reconstruct cycle
                cycle = [neighbor]
                current = node
                while current != neighbor:
                    cycle.append(current)
                    current = parent[current]
                cycle.append(neighbor)
                cycles.append(cycle)

    for node in graph:
        if node not in visited:
            dfs(node, -1)

    return cycles

Common Interview Problems

Problem 1: Course Schedule (LeetCode 207)

Given n courses and prerequisites, determine if you can finish all courses. This is cycle detection in a directed graph.

def can_finish(num_courses, prerequisites):
    """
    Returns True if all courses can be finished.
    prerequisites[i] = [a, b] means b must be taken before a.
    """
    graph = [[] for _ in range(num_courses)]
    for course, prereq in prerequisites:
        graph[prereq].append(course)

    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * num_courses

    def has_cycle(node):
        color[node] = GRAY
        for neighbor in graph[node]:
            if color[neighbor] == GRAY:
                return True
            if color[neighbor] == WHITE and has_cycle(neighbor):
                return True
        color[node] = BLACK
        return False

    for i in range(num_courses):
        if color[i] == WHITE and has_cycle(i):
            return False
    return True


# Example
print(can_finish(4, [[1, 0], [2, 1], [3, 2]]))  # True (no cycle)
print(can_finish(2, [[0, 1], [1, 0]]))           # False (cycle)

Problem 2: Redundant Connection (LeetCode 684)

Find the edge that, if removed, makes the graph a tree. This is the last edge that creates a cycle.

def find_redundant_connection(edges):
    """
    Find the last edge that creates a cycle in an undirected graph.
    """
    n = len(edges)
    uf = UnionFind(n + 1)

    for u, v in edges:
        if not uf.union(u, v):
            return [u, v]
    return []


# Example
print(find_redundant_connection([[1,2],[1,3],[2,3]]))  # [2, 3]

Practice Problems

1. Course Schedule (LeetCode 207) - Direct cycle detection in directed graph
2. Course Schedule II (LeetCode 210) - Topological sort with cycle check
3. Redundant Connection (LeetCode 684) - Union-Find cycle detection
4. Redundant Connection II (LeetCode 685) - Directed graph, harder variant
5. Graph Valid Tree (LeetCode 261) - Check if graph forms a valid tree (no cycle + connected)
6. Detect Cycles in 2D Grid (LeetCode 1559) - Cycle detection on a matrix
7. Find Eventual Safe States (LeetCode 802) - Three-color DFS variant

Key Takeaways

Cycle detection boils down to three ideas. For undirected graphs, track the parent during DFS and flag any visited non-parent neighbor. For directed graphs, use the white/gray/black coloring and look for back edges to gray nodes. For edge-list inputs or online edge insertion, Union-Find gives you near-constant-time cycle checks per edge.

The three-color DFS for directed graphs is especially important because it forms the foundation of topological sorting. If you can detect that a directed graph has no cycle, you can produce a topological order, which unlocks dependency resolution, task scheduling, and compilation order problems.