Go Guide

Trees & graphs · Lesson 33 of 62 · about 40 min

Union-Find

Track which items belong to the same group as connections arrive, in nearly constant time, and build minimum spanning trees with it.

Visualgo: Union-Find ↗
On this page · 10 sections
  1. 01Two operations
  2. 02How it works
  3. 03Two optimizations make it nearly O(1)
  4. 04Kruskal's minimum spanning tree
  5. 05The full program
  6. 06Complexity
  7. 07Recognizing the pattern
  8. 08Summary
  9. 09Check your understanding
  10. 10Practice in Go

Two operations#

OperationMeaning
Find(x)return the representative (root) of x's group
Union(a, b)merge the groups of a and b; return false if they were already together

Storage is just a slice: parent[x] is x's parent, and a root is its own parent. Initially every item is alone: parent[i] = i.

How it works#

Five items, then Union(0,1), Union(2,3), Union(1,3):

stepparent slicegroups
start[0 1 2 3 4]
Union(0,1)[0 0 2 3 4]
Union(2,3)[0 0 2 2 4]
Union(1,3): Find(1)=0, Find(3)=2, attach 2 under 0[0 0 0 2 4]

Now Find(3) walks 3 → 2 → 0: root 0. Find(4) is 4. Different roots: different groups.

Run the trace

The simplest possible Union-Find, with no optimizations yet, printing the parent slice after each step:

uf_trace.go
Go
package main
 
import "fmt"
 
func main() {
	parent := []int{0, 1, 2, 3, 4}
	find := func(x int) int {
		path := []int{x}
		for parent[x] != x {
			x = parent[x]
			path = append(path, x)
		}
		fmt.Printf("  find walks %v\n", path)
		return x
	}
	union := func(a, b int) {
		ra, rb := find(a), find(b)
		if ra == rb {
			fmt.Printf("union(%d,%d): already together\n", a, b)
			return
		}
		parent[rb] = ra
		fmt.Printf("union(%d,%d): attach root %d under root %d -> %v\n", a, b, rb, ra, parent)
	}
	union(0, 1)
	union(2, 3)
	union(1, 3)
	union(0, 3)
	fmt.Println("same group 3 and 0?", find(3) == find(0))
	fmt.Println("same group 3 and 4?", find(3) == find(4))
}
Output
  find walks [0]
  find walks [1]
union(0,1): attach root 1 under root 0 -> [0 0 2 3 4]
  find walks [2]
  find walks [3]
union(2,3): attach root 3 under root 2 -> [0 0 2 2 4]
  find walks [1 0]
  find walks [3 2]
union(1,3): attach root 2 under root 0 -> [0 0 0 2 4]
  find walks [0]
  find walks [3 2 0]
union(0,3): already together
  find walks [3 2 0]
  find walks [0]
same group 3 and 0? true
  find walks [3 2 0]
  find walks [4]
same group 3 and 4? false

Step through it

Two optimizations make it nearly O(1)#

Union by size: attach the root of the smaller tree under the root of the larger one. A node only gets deeper when its tree merges into one at least as big, so depth stays at most log n.

Path compression: while walking up in Find, point nodes closer to the root. The version below uses path halving: each node on the path is pointed at its grandparent. Later finds on those nodes are much shorter.

With both, a sequence of m operations costs O(m · α(n)), where α is the inverse Ackermann function, at most 4 for any input that fits in the universe. Treat it as constant.

See the difference

Unite 1,000 items in a chain, always attaching the bigger group under the newcomer (the worst choice), and measure the longest path a Find must walk. Then do the same with union by size and path halving:

uf_depth.go
Go
package main
 
import "fmt"
 
type Naive struct{ parent []int }
 
func (d *Naive) Find(x int) int {
	for d.parent[x] != x {
		x = d.parent[x]
	}
	return x
}
 
type DSU struct{ parent, size []int }
 
func (d *DSU) Find(x int) int {
	for d.parent[x] != x {
		d.parent[x] = d.parent[d.parent[x]] // path halving
		x = d.parent[x]
	}
	return x
}
 
func (d *DSU) Union(a, b int) {
	ra, rb := d.Find(a), d.Find(b)
	if ra == rb {
		return
	}
	if d.size[ra] < d.size[rb] {
		ra, rb = rb, ra
	}
	d.parent[rb] = ra // smaller tree under larger
	d.size[ra] += d.size[rb]
}
 
func depth(parent []int, x int) int {
	steps := 0
	for parent[x] != x {
		x = parent[x]
		steps++
	}
	return steps
}
 
func maxDepth(parent []int) int {
	best := 0
	for x := range parent {
		best = max(best, depth(parent, x))
	}
	return best
}
 
func main() {
	const n = 1000
	naive := &Naive{make([]int, n)}
	dsu := &DSU{make([]int, n), make([]int, n)}
	for i := range n {
		naive.parent[i], dsu.parent[i], dsu.size[i] = i, i, 1
	}
	for i := 1; i < n; i++ {
		naive.parent[naive.Find(0)] = i // old root goes under the newcomer
		dsu.Union(i, 0)
	}
	fmt.Println("naive deepest find:", maxDepth(naive.parent), "steps")
	fmt.Println("DSU deepest find:  ", maxDepth(dsu.parent), "steps")
}
Output
naive deepest find: 999 steps
DSU deepest find:   1 steps

Kruskal's minimum spanning tree#

A spanning tree connects all n nodes using n-1 edges; the minimum one has the smallest total weight (cheapest way to cable buildings, connect cities). Kruskal's algorithm:

  1. Sort all edges by weight.
  2. For each edge, if its endpoints are in different groups, take it and union them. Otherwise skip it (it would make a cycle).
  3. Stop after n-1 edges.

Run the trace

The edges from the full program below, sorted by weight. Each line says whether Kruskal keeps the edge or skips it:

kruskal_trace.go
Go
package main
 
import (
	"cmp"
	"fmt"
	"slices"
)
 
type Edge struct{ U, V, W int }
 
func main() {
	n := 5
	edges := []Edge{{0, 1, 4}, {0, 2, 1}, {1, 2, 2}, {1, 3, 5}, {2, 3, 8}, {3, 4, 3}}
	slices.SortFunc(edges, func(a, b Edge) int { return cmp.Compare(a.W, b.W) })
 
	parent := []int{0, 1, 2, 3, 4}
	var find func(int) int
	find = func(x int) int {
		if parent[x] != x {
			parent[x] = find(parent[x])
		}
		return parent[x]
	}
 
	total, taken := 0, 0
	for _, e := range edges {
		ru, rv := find(e.U), find(e.V)
		if ru == rv {
			fmt.Printf("edge %d-%d (w %d): skip, would make a cycle\n", e.U, e.V, e.W)
			continue
		}
		parent[ru] = rv
		total += e.W
		taken++
		fmt.Printf("edge %d-%d (w %d): take, total %d\n", e.U, e.V, e.W, total)
		if taken == n-1 {
			fmt.Println("n-1 edges taken: done")
			break
		}
	}
}
Output
edge 0-2 (w 1): take, total 1
edge 1-2 (w 2): take, total 3
edge 3-4 (w 3): take, total 6
edge 0-1 (w 4): skip, would make a cycle
edge 1-3 (w 5): take, total 11
n-1 edges taken: done

Step through it

The full program#

dsu.go
Go
package main
 
import (
	"cmp"
	"fmt"
	"slices"
)
 
type DSU struct {
	parent, size []int
	Groups       int
}
 
func NewDSU(n int) *DSU {
	d := &DSU{parent: make([]int, n), size: make([]int, n), Groups: n}
	for i := range n {
		d.parent[i], d.size[i] = i, 1
	}
	return d
}
 
func (d *DSU) Find(x int) int {
	for d.parent[x] != x {
		d.parent[x] = d.parent[d.parent[x]] // path halving
		x = d.parent[x]
	}
	return x
}
 
func (d *DSU) Union(a, b int) bool {
	ra, rb := d.Find(a), d.Find(b)
	if ra == rb {
		return false
	}
	if d.size[ra] < d.size[rb] {
		ra, rb = rb, ra
	}
	d.parent[rb] = ra // smaller tree under larger
	d.size[ra] += d.size[rb]
	d.Groups--
	return true
}
 
func redundantConnection(edges [][2]int, n int) [2]int {
	d := NewDSU(n)
	for _, e := range edges {
		if !d.Union(e[0], e[1]) {
			return e
		}
	}
	return [2]int{-1, -1}
}
 
type wEdge struct{ u, v, w int }
 
func kruskal(n int, edges []wEdge) (int, []wEdge) {
	slices.SortFunc(edges, func(a, b wEdge) int { return cmp.Compare(a.w, b.w) })
	d := NewDSU(n)
	total := 0
	var used []wEdge
	for _, e := range edges {
		if d.Union(e.u, e.v) {
			total += e.w
			used = append(used, e)
			if len(used) == n-1 {
				break
			}
		}
	}
	return total, used
}
 
func main() {
	d := NewDSU(5)
	d.Union(0, 1)
	d.Union(2, 3)
	d.Union(1, 3)
	fmt.Println(d.Find(3) == d.Find(0), d.Find(4) == d.Find(0), "groups:", d.Groups)
	fmt.Println("already joined:", !d.Union(0, 2))
 
	fmt.Println(redundantConnection([][2]int{{0, 1}, {1, 2}, {2, 3}, {1, 3}, {3, 4}}, 5))
 
	edges := []wEdge{{0, 1, 4}, {0, 2, 1}, {1, 2, 2}, {1, 3, 5}, {2, 3, 8}, {3, 4, 3}}
	total, used := kruskal(5, edges)
	fmt.Println("MST cost:", total, used)
}
Output
true false groups: 2
already joined: true
[1 3]
MST cost: 11 [{0 2 1} {1 2 2} {3 4 3} {1 3 5}]

Trace Kruskal: sorted weights 1, 2, 3, 4, 5, 8. Take 0–2 (1), 1–2 (2), 3–4 (3); skip 0–1 (4) because 0 and 1 are already connected through 2; take 1–3 (5). Four edges for five nodes: done, total 11.

Complexity#

OperationTime
Find, Union (with both optimizations)nearly O(1) amortized
counting components over m edgesO(m)
KruskalO(m log m), dominated by sorting

Recognizing the pattern#

  • Connections arrive over time and you ask "connected?" or "how many groups?".
  • "Find the edge that creates a cycle" in an undirected graph.
  • Grouping by equivalence (same account, same equation variable, similar strings).
  • Minimum spanning tree.

If the graph is fixed and you only need components once, a DFS works too. Union-Find shines when edges keep arriving.

Summary#

  • Union-Find keeps groups as trees; Find returns the root, Union links roots.
  • Union by size plus path compression make both operations effectively constant time.
  • A failed Union means the two were already connected: a cycle in an undirected graph.
  • Kruskal's MST: sort edges, keep those that join different groups.

Check your understanding

Answer before scrolling back up. If you miss one, reread the matching section, then try again.

  1. Q1.Union(a, b) returns false. What do you learn?

  2. Q2.What does path compression do?

  3. Q3.Why attach the smaller tree under the larger one (union by size)?

  4. Q4.Kruskal's algorithm builds a minimum spanning tree by:

Practice in Go

Write a table test first, then the solution. On LeetCode, choose Go as the language. Open a hint only after 15 minutes stuck.

Finished this lesson?

Mark it done to track your progress. It is saved in this browser only.