Cycle Detection in an Undirected Graph

Cycle Detection in an Undirected Graph asks a simple-sounding question — does the graph contain a loop? — and it is the cleanest place to learn union-find (disjoint-set union), a structure that answers "are these two things already connected?" almost instantly.

The slow way first

You could run DFS from every unvisited node, tracking the parent you came from, and flag a cycle whenever you reach an already-visited node that is not your parent. That works in O(n + e), but it needs you to build an adjacency list and manage a recursion stack and a visited set.

The question to ask: as I add edges one at a time, can I cheaply tell whether the two endpoints are already linked? If they are, the new edge closes a loop. A union-find structure answers exactly that.

The idea: merge groups, watch for a clash

Give every node its own group. Walk the edge list once. For each edge (u, v):

• Find the root (representative) of u and the root of v.
• If the roots are the same, u and v are already in one group — adding this edge makes a cycle. Return True.
• If the roots differ, merge the two groups (point one root at the other) and keep going.

If you survive every edge with no clash, there is no cycle.

The key insight: a cycle appears the moment an edge connects two nodes that were already reachable from each other. Union-find tracks reachability as you build the graph.

Walk through it

Step through the animation. The first three edges each join two separate groups, so they merge cleanly and the parent array fills in. When we reach the final edge (1, 3), both endpoints already trace back to root 0 — the edge turns red, and we return True.

Pseudocode

parent[x] = x for every node          # each node is its own group
define find(x):
    while parent[x] != x:             # follow pointers to the root
        x = parent[x]
    return x
for each edge (u, v):
    ru, rv = find(u), find(v)
    if ru == rv:                      # same group already
        return True                   # this edge closes a cycle
    parent[rv] = ru                   # merge the two groups
return False                          # no cycle found

The Python solution

def has_cycle(n, edges):
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            x = parent[x]
        return x
    for u, v in edges:
        ru, rv = find(u), find(v)
        if ru == rv:
            return True
        parent[rv] = ru
    return False

• parent = list(range(n)) makes each node its own root: node i starts pointing at itself.
• find(x) walks the parent pointers up to the root that represents x's group.
• For each edge we compute ru and rv, the roots of both endpoints.
• Lines 9 - 10 are the heart of it: if ru == rv, the endpoints already share a group, so the edge closes a cycle and we return True.
• Otherwise parent[rv] = ru merges the two groups by pointing one root at the other.

Complexity

The find here is plain (no path compression), so a single call can cost O(n) in a degenerate chain; adding path compression and union-by-rank drives the amortized cost to near-constant alpha(n). Either way the space is O(n) for the parent array.

When this pattern shows up

Practice