Union Find

Track which things are connected, with near-constant merges.

Medium5 problems

How do I recognise this pattern?

Connections are added incrementally and you must answer connectivity as they arrive.
Counting connected components after a series of merges.
Detecting whether an edge would close a cycle in an undirected graph.
Kruskal's minimum spanning tree.
Equivalence relations: accounts to merge, equations to check for consistency.

When it is the wrong tool

Connections are removed as well as added — union-find cannot split a set.
You need the actual path between two nodes, not just whether one exists.
The graph is static and fully known; a single DFS pass is simpler.

What is it?

A disjoint-set structure maintains a collection of groups under two operations: find which group an element belongs to, and merge two groups. With path compression and union by rank both run in near-constant amortised time, which makes it the right tool when connectivity changes as you go.

The core idea

Each set is a tree identified by its root. Path compression flattens the tree during lookups, so the structure gets faster the more it is queried.

Template

The shape, not a solution. Adapt the condition and the state to the problem in front of you.

Python

1class UnionFind:2    def __init__(self, n):3        self.parent = list(range(n))4        self.rank = [0] * n5        self.count = n   # number of disjoint sets6 7    def find(self, x):8        # Path compression: re-point every node on the way to the root.9        while self.parent[x] != x:10            self.parent[x] = self.parent[self.parent[x]]11            x = self.parent[x]12        return x13 14    def union(self, a, b):15        root_a, root_b = self.find(a), self.find(b)16        if root_a == root_b:17            return False   # already together; this edge closes a cycle18 19        # Union by rank keeps the trees shallow.20        if self.rank[root_a] < self.rank[root_b]:21            root_a, root_b = root_b, root_a22        self.parent[root_b] = root_a23        if self.rank[root_a] == self.rank[root_b]:24            self.rank[root_a] += 125 26        self.count -= 127        return True

Common mistakes

Comparing `a == b` instead of `find(a) == find(b)`, which tests element identity rather than group membership.
Skipping path compression or union by rank, degrading to O(n) per operation on a degenerate chain.
Assigning `parent[b] = a` rather than linking the roots, which silently corrupts the structure.
Forgetting to decrement the component count only when a merge actually happened.

Problems using Union Find

Problem	Difficulty	Role
Is There a Route?#95	Easy	Primary
Count the Reefs#97	Medium	Related
Study Circles#100	Medium	Primary

Union Find — Tech Epitome