Disjoint Sets

Why this data structure exists

Many problems evolve by merging groups and asking connectivity questions:

• •Social networks: do two users belong to the same community after a sequence of friend links?
• •Graph algorithms: does adding an edge create a cycle?
• •Clustering: merge clusters and query membership.

A naive approach stores each set explicitly (like a list). Then:

• •Union might require relabeling many elements (slow).
• •Find might require searching (slow).

Union-Find is designed for exactly this pattern: lots of operations, interleaving unions and queries, where we want each operation to be almost constant time.

The core abstraction: a disjoint partition

We maintain a collection of sets S₁, S₂, … such that:

• •Every element belongs to exactly one set.
• •Sets are non-overlapping: Sᵢ ∩ Sⱼ = ∅ for i ≠ j.
• •Their union is the whole universe U: ⋃ᵢ Sᵢ = U.

This is a partition of U.

The key idea: each set has a representative (root)

Instead of storing full sets, we store parent pointers that form a forest of rooted trees.

• •Each element x has a pointer parent[x].
• •If parent[x] = x, then x is a root.
• •Each root represents one set.

The representative (root) is a canonical “name” for the set. Two elements are in the same set iff they have the same root.

Formally, define:

• •find(x) = the root you reach by following parent pointers from x.
• •x and y are connected ⇔ find(x) = find(y).

What operations we support

We typically implement three operations:

1) make-set(x)

• •Create a new singleton set {x}.
• •parent[x] = x.

2) find(x)

• •Return the representative root of x’s set.

3) union(a, b)

• •Merge the sets containing a and b.
• •After union, all elements that were in either set are now in one set.

Data stored (common variant)

We’ll use these arrays:

• •parent[x]: index/pointer to x’s parent; root points to itself.
• •rank[x] (or size[x]): heuristic info to keep trees shallow.

Rank is an estimate of tree height; size is exact set size. Either supports good performance when used correctly.

A small picture in words

Suppose we have elements 1..7. Initially each is its own root.

After unions, we might have:

• •parent[1]=2, parent[2]=2 (2 is root)
• •parent[3]=2
• •parent[4]=5, parent[5]=5 (5 is root)
• •parent[6]=5
• •parent[7]=7 (alone)

Then:

• •find(1)=2, find(3)=2 ⇒ same set
• •find(4)=5, find(7)=7 ⇒ different sets

Union-Find’s entire job is to maintain this forest efficiently as it changes.

Why find() is the heart of Union-Find

Every union needs to know which sets it is merging, and every connectivity query needs to know whether two elements share a set. Both tasks reduce to a single primitive:

Find the representative root.

Without optimizations, find(x) just walks up parent pointers:

• •x → parent[x] → parent[parent[x]] → … until a root r where parent[r] = r.

That is correct—but could be slow if trees get tall.

Correctness invariant

Union-Find maintains this invariant:

• •The parent pointers form a forest of directed edges toward roots.
• •Each connected component (tree) has exactly one root r with parent[r] = r.
• •The set represented by r is exactly the nodes in that tree.

As long as union() only links root to root, and never creates cycles, the forest remains valid.

Baseline find implementation

Pseudocode (conceptually):

• •find(x):
• •while parent[x] ≠ x:
• •x = parent[x]
• •return x

This runs in O(h), where h is the height of x’s tree. If h becomes O(n), find becomes O(n) and everything collapses.

Path compression: the “secret sauce” for find

Motivation: If we frequently call find(x), it’s wasteful to traverse the same long path over and over.

Path compression flattens the tree during find:

• •After computing the root r, we rewire every node visited to point directly to r.

In a recursive form:

find(x):

• •if parent[x] = x: return x
• •parent[x] = find(parent[x])
• •return parent[x]

Now, the next time we call find on any of those nodes, it returns quickly.

What path compression does (and does not do)

• •It does not change which elements are in which set.
• •It does change the internal shape of the tree, usually making it much shallower.

Important subtlety: path compression alone already helps a lot, but to get the famous near-constant bound we pair it with a good union rule (next section).

A step-by-step mental model

Suppose we have a chain:

• •1 → 2 → 3 → 4 → 5 (root)

Calling find(1) without compression visits 1,2,3,4,5.

With path compression, after find(1):

• •1 → 5
• •2 → 5
• •3 → 5
• •4 → 5
• •5 → 5

Now find(2) is essentially O(1).

Complexity intuition (amortized)

Path compression can make one find operation do extra work (rewiring pointers), but that work pays off later.

Over a long sequence of operations, the total cost is tiny per operation. The formal result (when combined with union by rank/size) is:

• •m operations on n elements cost O(m α(n))

where α(n) is the inverse Ackermann function.

For any realistic n (even n ≈ 10²⁰), α(n) ≤ 5. So in practice, Union-Find behaves like constant time.

Implementation detail: iterative path compression

Some environments avoid recursion. You can still compress paths iteratively in two passes:

1) Walk up to find the root.

2) Walk again and set each visited node’s parent to the root.

Both are common; recursive is compact, iterative avoids stack depth issues.

Why union() needs a strategy

A union operation merges two sets. Internally, that means we take two roots r₁ and r₂ and make one the parent of the other.

If we do this carelessly (e.g., always parent[r₂] = r₁), we can create tall trees:

• •union(1,2), union(2,3), union(3,4), … can form a chain.

Tall trees make find slow.

So union must be disciplined: always attach the “smaller” or “shallower” tree under the “bigger” or “deeper” one.

Union by size

Store size[root] = number of nodes in that root’s tree.

Algorithm:

1) r₁ = find(a), r₂ = find(b)

2) if r₁ = r₂: already same set

3) attach smaller to larger:

• •if size[r₁] < size[r₂]: swap
• •parent[r₂] = r₁
• •size[r₁] += size[r₂]

Why it helps: each time a node’s tree is attached under another, the size of the resulting tree at least doubles. A node can only be “moved upward” O(log n) times.

Union by rank

Store rank[root], which approximates tree height.

Algorithm:

1) r₁ = find(a), r₂ = find(b)

2) if r₁ = r₂: return

3) compare ranks:

• •if rank[r₁] < rank[r₂]: swap
• •parent[r₂] = r₁
• •if rank[r₁] = rank[r₂]: rank[r₁] += 1

Why rank works: ranks only increase when two equal-rank trees are merged, which is rare per node, and creates a provable bound when combined with path compression.

Rank vs size: which should you use?

Both are excellent. Rank is slightly more common in textbooks; size can be easier to reason about and gives you set sizes for free.

Either one + path compression ⇒ near-constant amortized time.

The famous time bound (what it really means)

With both heuristics:

• •Total time for m operations on n elements is O(m α(n)).

This is an amortized statement:

• •Some single operations might still take longer (especially early on).
• •Averaged across the whole sequence, operations are extremely fast.

“Near-constant” is not marketing—it's math

α(n) grows so slowly that it’s ≤ 4 for values of n far beyond what you can store in memory.

That’s why Union-Find is one of the few structures where theoretical and practical performance line up remarkably well.

A careful invariant to keep

Union must connect roots to roots.

That means union(a,b) should do:

• •r₁ = find(a)
• •r₂ = find(b)
• •parent[r₂] = r₁ (or vice versa)

If you accidentally do parent[a] = b without finding roots, you can break the forest structure and even create cycles, making find incorrect or non-terminating.

The pattern: dynamic connectivity under unions

Union-Find shines when:

• •Connections are only added (monotonic growth).
• •You need to query whether two elements are connected.

It does not directly support efficiently removing connections (dynamic connectivity with deletions is harder).

Kruskal’s algorithm (Minimum Spanning Tree)

In Kruskal’s algorithm, you sort edges by weight and add them if they don’t create a cycle.

The cycle check is exactly:

• •edge (u,v) is safe iff find(u) ≠ find(v)
• •then union(u,v)

So DSU provides cycle detection quickly, making Kruskal efficient.

Cycle detection in an undirected graph

As you scan edges:

• •If find(u) = find(v), then u and v are already connected ⇒ adding (u,v) creates a cycle.
• •Otherwise union(u,v).

This is a lightweight way to detect cycles without full DFS each time.

Connected components as they evolve

Suppose you’re building components from interactions:

• •Each interaction merges components.
• •You can ask at any time whether two nodes are in the same component.

With union by size, you can also answer:

• •“How big is the component containing x?”
• •root = find(x)
• •size[root]

Percolation / grid connectivity

In an N×N grid, you may open cells and union adjacent open cells.

Queries like “is there a path from top to bottom?” become connectivity checks between virtual nodes representing borders.

DSU and equivalence relations

Union-Find is a practical way to maintain an equivalence relation ~ over elements:

• •Reflexive: x ~ x (same root)
• •Symmetric: x ~ y ⇒ y ~ x
• •Transitive: x ~ y and y ~ z ⇒ x ~ z

Union operations add equivalences; find queries membership in equivalence classes.

How it connects to what you already know

You already know:

• •Trees: DSU stores a forest of rooted trees.
• •Amortized analysis: DSU’s speed guarantee is amortized; single operations can vary, but the sequence is fast.

Think of DSU as a case study where an extremely simple structure (parent pointers) becomes powerful when paired with the right heuristics.

Implementation checklist (practical)

When writing DSU in code:

• •Initialize: parent[x] = x for all x.
• •Choose one heuristic: rank or size.
• •Always call find() inside union().
• •Use path compression in find().

The resulting code is short, reliable, and performance-friendly.

A note on vectors and math notation

Union-Find is less about vector math (no v or ‖v‖ needed here), and more about combinatorial structure. Still, it’s grounded in precise invariants and amortized bounds, which is why it belongs in a core data structures track.