Union-Find (Disjoint Set) — answering 'are these connected' fast

Checking whether two nodes are in the same connected group with BFS/DFS means re-traversing the whole graph on every query — Union-Find answers the same question in nearly constant time, at the cost of only ever merging groups, never splitting them.

Intermediate

4 min read

The question Union-Find is built to answer, fast and repeatedly

# "Are node A and node B in the same connected group?" — asked MANY times,
# as the graph itself is being built up incrementally, edge by edge

BFS or DFS (from the graphs lesson) can answer "is A connected to B" by traversing the whole graph from A, checking whether B is reached — correct, but O(V + E) every single time the question is asked. Union-Find (also called Disjoint Set Union, or DSU) is a specialized structure built for exactly this question, asked repeatedly, especially while the graph is being constructed incrementally (edges added one at a time) rather than existing complete from the start — the two operations it supports, union (merge two groups) and find (which group does this node belong to), are both close to O(1) after a couple of real, standard optimizations.

The core idea: every node points toward a group "representative"

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))  # initially, every node is its OWN representative
 
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # PATH COMPRESSION — flatten the chain as we go
        return self.parent[x]
 
    def union(self, a, b):
        root_a, root_b = self.find(a), self.find(b)
        if root_a != root_b:
            self.parent[root_a] = root_b  # merge one group's representative under the other's

Every node has a parent pointer; following parent pointers repeatedly eventually reaches a node that points to itself — the group's representative. Two nodes are in the same group exactly when find returns the same representative for both. union doesn't merge two groups' actual members directly — it just repoints one group's representative to point at the other's, which implicitly merges every member of both groups in one O(1) pointer change.

Path compression: why `find` gets fast after the first call

# Without path compression: find() walks the FULL chain every single time,
# which can degrade to O(n) if unions happen to build a long chain
 
# With path compression (the `self.parent[x] = self.find(...)` line above):
# every node visited during a find() gets repointed DIRECTLY to the root —
# so every FUTURE find() on any of those nodes is now O(1)

Without path compression, repeated union calls can build a long chain of parent pointers, degrading find toward O(n) in the worst case — exactly the same kind of structural degradation a naive, unbalanced binary search tree can suffer from. Path compression fixes this opportunistically: every time find walks a chain to reach the root, it rewires every node it passed through to point directly at that root, so the chain never gets walked in full more than once — after enough calls, nearly every find becomes an O(1) direct lookup.

The real, common use: counting connected components as edges are added

def count_components(n, edges):
    uf = UnionFind(n)
    for a, b in edges:
        uf.union(a, b)
    return len({uf.find(i) for i in range(n)})  # how many DISTINCT representatives remain

Counting how many separate connected groups exist after processing a list of edges — a real, common pattern (detecting friend-group clusters, checking whether a network is fully connected, or finding which cities are reachable from which others) — is exactly the shape Union-Find handles cleanly: process every edge with union, then count the number of distinct representatives left. Doing the same thing with repeated BFS/DFS calls (one full traversal per component) works, but is genuinely less direct for this specific "how many groups, and which nodes are in which" question.

What Union-Find genuinely can't do: it only merges, never splits

# Union-Find has NO operation for "these two nodes are no longer connected" —
# once two groups are merged, there's no way to undo that merge and split
# them back apart within the standard structure

Union-Find is a one-directional structure: union merges groups, and there's no corresponding "split" operation to undo a merge — once two nodes are reported as connected, they stay connected for the rest of the structure's lifetime, regardless of what happens to the underlying graph. This makes it the right tool specifically for problems where connections only ever get added (building up a network, processing edges in Kruskal's minimum-spanning-tree algorithm) — not for a graph where edges can also be removed, which needs a genuinely different approach entirely.