Cycle DetectionCycle detection

01Why it exists

Reach for it when you see:Circular dependencies, deadlock, mutual waiting, checking whether something is a DAG, whether adding this edge creates a cycle, whether a graph is a tree, looping back to yourself.

02The core idea

A cycle is a walk that leaves a node, follows edges, and comes back to where it started. DFS is a natural fit for finding one, because the call stack is exactly the path from the start node to the node you are on. For directed graphs, use three colours: white means not yet visited, grey means entered but not yet left (still on the stack), and black means every outgoing edge has been checked. When you are at u and look at the edge u → v, a grey v is still on the current path, so walking the path from v down to u and then taking u → v brings you back around. That edge is called a back edge. A single visited flag is not enough: in a diamond like A → B → D and A → C → D, D has already been visited when you reach it the second time, yet the graph has no cycle. The distinction between black and grey is what rules out that false alarm.

Why "has a cycle" is equivalent to "DFS hits a grey node". When you hit a grey v, every step on the stack from v to u is a real edge, and adding u → v closes a cycle, so there are no false positives. In the other direction, suppose the graph does have a cycle, and let v be the first node on it to be visited. At that moment every other node on the cycle is white and reachable by following the cycle, so all of them get visited before dfs(v) returns. In particular, when u — the node just before v on the cycle — checks u → v, v is still on the stack and therefore grey, so there are no false negatives either. The same argument explains why a black node can simply be skipped: every cycle is caught while its first node is still grey.

Undirected graphs cannot reuse this as-is, because every edge runs both ways: after you walk from u to v, v immediately sees u sitting right behind it. The DFS version skips the edge it just came in on and treats every other visited neighbour as a cycle. Do that exclusion by edge index, not by parent node, or you will miss the cycle formed by two parallel u – v edges. The union-find version adds edges one at a time: if both ends share a find root, a path between them already exists, so this edge closes a cycle the moment it is added. It only needs the edge list, which suits situations where edges arrive one by one. But union-find does not work on directed graphs: given A → B, A → C, B → C, B and C are already in the same set when the third edge arrives, and yet that graph has no directed cycle. Undirected graphs also allow a counting check: a forest has exactly V − number of connected components edges, so any graph with more than that must contain a cycle.

Complexity: in three-colour DFS each node goes white to grey and grey to black once, and each directed edge is checked once, for O(V+E) time. The colour array is O(V) and recursion can reach depth O(V) in the worst case (one long chain), so space is O(V), not counting the adjacency list you were given. Undirected DFS looks at each edge once from each end, which is still O(V+E). The union-find version with path compression and union by size is O(V + E·α(V)) — linear for all practical purposes. When you only need a yes or no, you can stop at the first cycle. Three mistakes are common: running DFS only from node 0 and missing the disconnected parts; hitting Python's default recursion limit of 1000, which means going iterative on large graphs, or switching to Kahn's in-degree method from Topological Sort, where a sort that places fewer than V nodes means there is a cycle; and forgetting that when every node has exactly one outgoing edge (a linked list, or the sequence x → f(x)), Fast & Slow Pointers finds the cycle in O(1) space.

03The algorithm

1. 1First decide whether the graph is directed or undirected. The DFS version turns the input into an adjacency list; the union-find version only needs the edge list.
2. 2Directed: set every entry of color to white and call dfs(s) on every node s that is still white. Do not start from node 0 alone.
3. 3dfs(u): colour u grey and push it onto the path. For each edge u → v: grey means you found a cycle; white means recurse, and if the child call found a cycle, pass it straight back up; black means skip. Once every outgoing edge is checked, colour u black and pop it off the path.
4. 4To report the cycle itself: when you hit a grey v, take the stretch of the path from v to the end and append v again — those are the nodes on the cycle.
5. 5Undirected: set parent[i] = i and process each (u, v) in turn. find(u) == find(v) means a cycle; otherwise union them. If you use DFS instead, record the index of the edge you used to reach each node, skip that one edge, and treat every other visited neighbour as a cycle.
6. 6With tens of thousands of nodes, avoid deep recursion: simulate the stack explicitly, or use Kahn's in-degree method and check whether a topological sort can place every node.

04Interactive demo

Both modes use the same six nodes A–F and seven edges each. "Directed · three-colour DFS" starts at A and checks outgoing edges in insertion order: a yellow outline means grey (on the call stack, mirrored in the list on the right) and a solid blue node is the one being processed. Watch E → B hit a grey B and the whole ring B → D → E → B turn yellow; a little later F → E hits a finished, black E (dashed) and that is not a cycle. "Undirected · union-find" adds edges one at a time: blue lines join the forest, and a blue cell in the parent array marks a root. When D – E and B – D come in, both ends are already in one set, so only those two cycle-closing edges are marked yellow.

05Code

Python has three functions: three-colour DFS that finds a directed cycle and returns the nodes on it, union-find that answers whether an undirected graph has a cycle, and an undirected DFS version that excludes the edge it came in on by index, which handles parallel edges correctly. The examples use the same graph as the interactive demo, with A–F numbered 0–5. The C++ version implements the first two.

WHITE, GRAY, BLACK = 0, 1, 2


def find_directed_cycle(n, edges):
    """Directed graph: three-colour DFS. Returns the nodes on the cycle (first == last), or None."""
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
    color = [WHITE] * n
    path = []                                # the current call stack

    def dfs(u):
        color[u] = GRAY                      # entering: u is on the path
        path.append(u)
        for v in adj[u]:
            if color[v] == GRAY:             # back edge: v is still on the path
                return path[path.index(v):] + [v]
            if color[v] == WHITE:
                cycle = dfs(v)
                if cycle:
                    return cycle
        path.pop()
        color[u] = BLACK                     # leaving: nothing reachable from u comes back
        return None

    for s in range(n):                       # the graph may be disconnected, so start from every white node
        if color[s] == WHITE:
            cycle = dfs(s)
            if cycle:
                return cycle
    return None


def has_undirected_cycle(n, edges):
    """Undirected graph: union-find. If both ends are already in one set, this edge closes a cycle."""
    parent = list(range(n))
    size = [1] * n

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]    # path halving
            x = parent[x]
        return x

    for u, v in edges:
        ru, rv = find(u), find(v)
        if ru == rv:
            return True
        if size[ru] < size[rv]:              # hang the smaller tree under the larger one
            ru, rv = rv, ru
        parent[rv] = ru
        size[ru] += size[rv]
    return False


def has_undirected_cycle_dfs(n, edges):
    """Undirected graph, DFS version: a visited neighbour reached by an edge other than the one we came in on means a cycle."""
    adj = [[] for _ in range(n)]
    for i, (u, v) in enumerate(edges):
        adj[u].append((v, i))
        adj[v].append((u, i))
    seen = [False] * n

    def dfs(u, via):                         # via: index of the edge we used to reach u
        seen[u] = True
        for v, i in adj[u]:
            if i == via:                     # compare edge indices, not parents, so parallel edges are not missed
                continue
            if seen[v] or dfs(v, i):
                return True
        return False

    return any(not seen[s] and dfs(s, -1) for s in range(n))


if __name__ == "__main__":
    # the same graph as the interactive demo, with A..F numbered 0..5
    directed = [(0, 1), (0, 5), (1, 2), (1, 3), (3, 4), (4, 1), (5, 4)]
    print(find_directed_cycle(6, directed))                      # [1, 3, 4, 1], i.e. B → D → E → B
    print(find_directed_cycle(4, [(0, 1), (0, 2), (1, 3), (2, 3)]))  # None (diamond: 3 is reached twice, but there is no cycle)
    undirected = [(0, 1), (1, 2), (0, 5), (2, 3), (5, 4), (3, 4), (1, 3)]
    print(has_undirected_cycle(6, undirected))                   # True (the 6th edge, D – E, closes a cycle)
    print(has_undirected_cycle(6, undirected[:5]))               # False (the first 5 edges form a tree)
    print(has_undirected_cycle_dfs(6, undirected[:5]))           # False
    print(has_undirected_cycle_dfs(2, [(0, 1), (0, 1)]))         # True (two parallel edges are a cycle too)

06Practice

• LeetCode 207Course Schedule (switch to three-colour DFS and print the cycle)Medium
• LeetCode 802Find Eventual Safe States (the nodes that turn black are the safe ones)Medium
• LeetCode 1559Detect Cycles in 2D Grid (undirected DFS that skips the edge it came in on)Medium
• LeetCode 457Circular Array Loop (every node has exactly one outgoing edge)Medium
• LeetCode 685Redundant Connection II (directed version: in-degree 2 or a cycle)Hard
• LeetCode 2360Longest Cycle in a Graph (measure the cycle's length)Hard