Union-FindUnion-find

01Why it exists

Reach for it when you see:Whether two things are in the same group, edges added dynamically, how many connected components there are, whether adding this edge closes a cycle, merging only and never splitting.

02The core idea

Union-find maintains a collection of disjoint sets and supports just two operations: find(x) returns the representative of the set containing x, and union(a, b) merges two sets. It represents a forest with a single parent array: each set is a tree, the root is its representative, and parent[root] = root. find walks up the parent links to the root; union hangs the root of one tree underneath the root of another.

In the naive version a tree can grow into a chain, making find O(n). Two optimisations flatten it to near-constant time. Path compression: on the way back out of find, point every node along the path directly at the root, so the next query takes a single step. Union by size (or by rank): always hang the smaller tree under the larger one, which caps the height at log n. Together they give O(m · α(n)) for m operations, where α is the inverse Ackermann function — never above 5 for any n you will ever meet, so treat it as constant.

Its limitation is worth remembering: it merges, it never splits. Problems that require removing an edge ("is it still connected once this link is cut?") are usually turned around: start with none of the edges present and add them back from the last step in reverse. It also only answers whether two nodes are connected, never how to get from one to the other — for a path you still need BFS or DFS.

One feature that often goes unnoticed: union returning false means the two ends were already in the same group, which is to say that this edge closes a cycle. Cycle detection in an undirected graph, edge selection in Kruskal's algorithm, and checking whether a set of edges forms a tree all rely on that signal.

03The algorithm

1. 1Initialise parent[i] = i, size[i] = 1, and the group count count = n.
2. 2find(x): while parent[x] ≠ x, recurse to find the root of parent[x] and point parent[x] straight at that root (path compression).
3. 3union(a, b): find both roots. If they are equal, return false; otherwise hang the smaller root under the larger one, update size, and do count −= 1.
4. 4connected(a, b) is just find(a) == find(b), and the number of connected components is count.
5. 5When the nodes are not integers, map them to 0..n−1 with a hash table first. When edges have to be removed, consider processing the queries offline in reverse.

04Interactive demo

Eight nodes with a sequence of union and find operations. Watch how the parent array changes, how the trees grow, and which nodes get re-linked directly to the root when path compression fires.

05Code

A complete implementation with path compression and union by size, plus its two most common uses: counting connected components and detecting a cycle in an undirected graph. The C++ version uses iterative path halving to avoid recursion.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))     # everyone starts out as their own root
        self.size = [1] * n              # size of each tree, used when merging
        self.count = n                   # how many groups there are right now

    def find(self, x):
        """Find the root. Path compression: on the way back, hang every node on the path straight off the root"""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, a, b):
        """Merge two groups. False means they were already one group (that signal detects cycles)"""
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.size[ra] < self.size[rb]:    # union by size: hang the smaller tree under the larger
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.count -= 1
        return True

    def connected(self, a, b):
        return self.find(a) == self.find(b)


# Usage: counting connected components (the heart of LeetCode 547 Number of Provinces)
uf = UnionFind(8)
for a, b in [(0, 1), (2, 3), (1, 3), (4, 5), (6, 7), (5, 7)]:
    uf.union(a, b)
print(uf.count)                 # 2 groups: {0,1,2,3} and {4,5,6,7}
print(uf.connected(0, 4))       # False

# Cycle detection on an undirected graph: if both ends are already one group, this edge closes a cycle
def has_cycle(n, edges):
    uf = UnionFind(n)
    return any(not uf.union(a, b) for a, b in edges)

06Practice

• LeetCode 547Number of ProvincesMedium
• LeetCode 684Redundant Connection (cycle detection)Medium
• LeetCode 200Number of Islands (worth redoing with union-find)Medium
• LeetCode 721Accounts Merge (the nodes are strings)Medium
• LeetCode 1584Min Cost to Connect All Points (the setup for Kruskal)Medium
• LeetCode 1319Number of Operations to Make Network ConnectedMedium