Disjoint Sets

Track which elements belong to the same group, and merge groups - in nearly $O(1)$ per operation.

Disjoint Sets

Union-Find

find

walk up to root

Fast Find

goal: near O(1) per call

Path Compression

rewire nodes to root on return

union

merge two groups

Fast Union

goal: keep tree shallow

Union by Rank

attach shorter under taller

Optimal

O(α(n)) amortized per operation

Learn

The Idea - the one question DSU answers, the forest of parent pointers, the four arrays, the invariants, and the five things DSU flatly refuses to do. Start here if "union-find" has ever felt like an incantation rather than a structure.
Find & Union - both operations, path compression and union by rank/size taken separately, why the two together are effectively constant, and a sandbox for switching either off. This is the page to actually internalize.
Metadata on the Roots - count, size, and the general rule for hanging any mergeable value on a representative. Where most of the actual answers come from.
Recognising the Pattern - the trigger phrases, DSU versus BFS/DFS, encoding non-integer elements, virtual nodes, running time backwards, and the Kruskal skeleton. The half that is hard: noticing.
Variants - parity DSU, weighted DSU, rollback DSU, and when each earns its extra field. Read once the plain structure is automatic.

What do I reach for

The question asks for	Reach for	Cost
"are these two connected / related / equal"	`find(a) == find(b)`	`O(a(n))`
"how many groups / provinces / circles"	`dsu.count` after absorbing every edge	`O(E a(n))`
"the largest group", "how big is `x`'s group"	`size` metadata, read as `size[find(x)]` - Metadata	`O(1)` per query
"which edge closes a cycle / is redundant"	the first `union` that returns `False` - the return value	`O(E a(n))`
"is this a valid tree"	`len(edges) == n - 1` and every `union` returns `True`	`O(E a(n))`
"cheapest way to connect everything"	Kruskal: sort, then union - sort then union	`O(E log E)`
"the earliest moment everything is connected"	sort events by time, union until `count == 1`	`O(E log E)`
"these two must be in DIFFERENT groups"	parity DSU, or the 2n trick - Variants	`O(a(n))`
"a is twice b, b is 3x c, what is a/c"	weighted DSU - Variants	`O(a(n))`
"after each REMOVAL, how many components"	run the events backwards - reverse time	`O(E a(n))`
the same, but each query depends on the last answer	rollback DSU - Variants	`O(log n)` per op
the path or the distance between two things	not DSU - use BFS/DFS	`O(V + E)`
"can `a` reach `b`" on a directed graph	not DSU - use SCC	`O(V + E)`

The bug checklist

Every trap on the learn pages, in the order they tend to bite. If a DSU solution is wrong and you do not know why, read down this list.

#	Check	Symptom when wrong
1	Does `find` assign the compressed parent - `self.parent[x] = self.find(...)`?	Correct answers, zero speedup, timeout only on the large test.
2	Does `union` attach the two roots, not the two arguments?	A group silently splits. Counts drift; nothing errors.
3	Is `count -= 1` inside the "roots differ" branch?	Component count too low by the number of duplicate edges.
4	Is `size` read as `size[find(x)]`, never as a bare `size[x]`?	Plausible-but-small sizes. Passes small inputs.
5	Is the DSU sized for the real element count (`2 * len(pairs)` when interning)?	`IndexError`, or a needlessly enormous array.
6	Grid flattening: is it `r * cols + c` and not `r * rows + c`?	Cells collide on non-square grids; unrelated groups merge.
7	Is the relation genuinely symmetric? Is the graph directed?	You compute weak connectivity and never find out.
8	Does `any(...)` / `all(...)` short-circuit before every edge was absorbed?	The boolean is right and `dsu.count` afterwards is wrong.
9	Are you bucketing members by `find(i)` rather than `parent[i]`?	A component splits into several groups in the final pass.
10	Does the problem remove anything? Did you reverse the event order?	You start looking for a split operation that does not exist.
11	Parity / weighted DSU: is the update between the recursion and the rewiring?	Connectivity stays correct; only the side/ratio answers are wrong.
12	Rollback DSU: is path compression off?	Rollback restores a state that was never true.
13	Recursive `find` on a 10^5-node chain - could it exceed ~1000 frames?	`RecursionError`. Use the iterative path-halving form.

Implementation

The version to write from memory. Explained line by line in Find & Union.

Time: O(α(n))
Space: O(n)

find and union - amortized $O(\alpha(n))$ . $\alpha$ is the inverse Ackermann function; bounded by 4 for any $n$ up to $10^{600}$ . Treat it as constant.
__init__ - $O(n)$ to allocate parent, rank, and size.
getSizes - $O(n)$ one pass over all elements.
Space - $O(n)$ for the three arrays.

class DisjointSets:
    def __init__(self, size):
        self.parent = list(range(size))  # each element is its own root initially
        self.rank = [0] * size  # upper bound on tree height per root
        self.size = [1] * size  # component size (1 per node initially)
        self.count = size  # number of disjoint components
 
    def find(self, element):
        if self.parent[element] == element:
            return element
        # path compression: flatten the chain to the root on the way back
        self.parent[element] = self.find(self.parent[element])
        return self.parent[element]
 
    def union(self, a, b):
        root_a = self.find(a)
        root_b = self.find(b)
        if root_a != root_b:
            # union by rank: attach shorter tree under taller to keep height small
            if self.rank[root_a] > self.rank[root_b]:
                self.parent[root_b] = root_a
                self.size[root_a] += self.size[root_b]
            elif self.rank[root_a] < self.rank[root_b]:
                self.parent[root_a] = root_b
                self.size[root_b] += self.size[root_a]
            else:
                self.parent[root_b] = root_a
                self.size[root_a] += self.size[root_b]
                self.rank[root_a] += 1  # only grows when both trees have equal rank
            self.count -= 1
            return True  # merged: two components became one
        return False  # already connected: no merge happened
 
    def getCount(self):
        return self.count
 
    def getSize(self, a):
        return self.size[self.find(a)]
 
    def getSizes(self):
        for i in range(len(self.parent)):
            if self.parent[i] == i:
                yield self.parent[i], self.size[i]

Practice

Problems - the connectivity, cycle-detection and grouping set.
Matrices - the islands family done with DSU instead of flood fill.

Learn​

What do I reach for​

The bug checklist​

Implementation​

Practice​

Learn

What do I reach for

The bug checklist

Implementation

Practice