Union-Find (Disjoint Set)

Disjoint sets as a forest

Union-find maintains a partition of 0..n-1 into disjoint sets, stored as a forest: every element points at a parent, and each set’s root (a node that is its own parent) is the set’s representative. Two elements are in the same set exactly when Find walks them to the same root.

graph TD
R1["2 (root)"] --> A["0"]
R1 --> B["1"]
R2["5 (root)"] --> C["3"]
R2 --> D["4"]

The two trees above are two sets: {0,1,2} with representative 2, and {3,4,5} with representative 5. Connected(0,1) is true; Connected(0,3) is false.

Find, Union, and the two optimizations

A naive forest can grow into a tall chain, making Find O(n). Two cheap tricks fix that:

• Path compression — when Find walks to the root, re-point every node on the path straight at the root. The tree flattens, so later queries are fast.
• Union by rank — when merging, hang the shorter tree under the taller (track an approximate height, the “rank”). This keeps trees shallow.

Together they make m operations cost O(m·α(n)), where α is the inverse Ackermann function — at most 4 for any realistic n, so each op is effectively constant:

package main

import "fmt"

// DSU is a disjoint-set (union-find) over 0..n-1.
type DSU struct {
parent []int
rank   []int
count  int // number of disjoint sets
}

func NewDSU(n int) *DSU {
d := &DSU{parent: make([]int, n), rank: make([]int, n), count: n}
for i := range d.parent {
	d.parent[i] = i // each element starts in its own set
}
return d
}

// Find returns x's representative, compressing the path on the way up.
func (d *DSU) Find(x int) int {
for d.parent[x] != x {
	d.parent[x] = d.parent[d.parent[x]] // path compression (halving)
	x = d.parent[x]
}
return x
}

// Union merges the sets of a and b; returns false if already joined.
func (d *DSU) Union(a, b int) bool {
ra, rb := d.Find(a), d.Find(b)
if ra == rb {
	return false // already in the same set
}
// union by rank: attach the shorter tree under the taller
if d.rank[ra] < d.rank[rb] {
	ra, rb = rb, ra
}
d.parent[rb] = ra
if d.rank[ra] == d.rank[rb] {
	d.rank[ra]++
}
d.count--
return true
}

func (d *DSU) Connected(a, b int) bool { return d.Find(a) == d.Find(b) }

func main() {
d := NewDSU(6)
d.Union(0, 1)
d.Union(1, 2)
d.Union(3, 4)

fmt.Println("0~2 connected:", d.Connected(0, 2)) // true
fmt.Println("0~3 connected:", d.Connected(0, 3)) // false
fmt.Println("disjoint sets:", d.count)           // 3: {0,1,2} {3,4} {5}

d.Union(2, 4) // merge the two big groups
fmt.Println("0~3 now:", d.Connected(0, 3), " sets:", d.count) // true, 2
}

What it’s for

Union-find is the right tool whenever you incrementally connect things and ask whether two are joined:

• Connected components — union every edge, then the number of distinct roots is the component count.
• Cycle detection in an undirected graph — process edges; if an edge’s two endpoints already share a root, adding it would close a cycle.
• Kruskal’s minimum spanning tree — sort edges by weight and add each one only if it joins two different sets (union returns true), skipping any that would form a cycle.
• Dynamic connectivity — “are these two nodes connected right now?” as edges arrive over time, which a one-shot BFS/DFS can’t answer cheaply.

graph LR
E["edges arrive"] --> U{"Union(u,v)
returns false?"}
U -->|"already same set"| C["edge forms a cycle"]
U -->|"merged"| K["keep edge (e.g. Kruskal MST)"]

Reference

See also

• graphs — BFS/DFS connectivity and the MST/cycle problems union-find accelerates.
• hash tables — map arbitrary keys to dense 0..n-1 indices for the DSU arrays.
• Big-O — where the α(n) amortized bound sits.
• greedy — Kruskal’s MST is a greedy algorithm built on union-find.

Next: divide and conquer on sorted data — binary search.

Related topics