Union-Find

One-liner: keep track of which items belong to the same group, merge two groups in almost constant time, and ask "are these two together?" without walking the whole graph.

The analogy

Picture a party where people keep discovering they are friends. You do not want a list of every friendship. You only want a group leader for each circle of friends. To ask "are Ana and Bo in the same circle?", you find each one's leader and compare. When two circles meet, one leader simply starts reporting to the other. That is Union-Find: a leader per group, and merging is one reassignment.

Recognition signals

Reach for Union-Find when you see:

1. Items that get connected over time, such as edges added one by one, or pairs of "same group" facts.
2. Questions about connectivity: how many groups, are these two connected, or which edge first creates a loop.
3. You do not need the path between two nodes. You only need to know whether they are connected.
4. A graph search would be repeated many times as new connections arrive.

Step-by-step walkthrough

Five nodes 0..4 and edges [0,1], [1,2], [3,4]:

1. Start with five groups. Each node is its own leader.
2. Union 0 and 1: they become one group. Four groups.
3. Union 1 and 2: 1 is already with 0, so 2 joins them. Three groups.
4. Union 3 and 4: two groups left, {0,1,2} and {3,4}.
5. If [0,2] arrived next, Find(0) and Find(2) give the same leader. Union returns false: this edge would close a cycle.

Code template

A parent slice plus two operations. The comments mark the four ideas that make it fast.

// UF tracks which items belong to the same group. Find answers "which group?", Union merges two groups.
type UF struct {
	parent []int
	size   []int
	groups int
}

func NewUF(n int) *UF {
	u := &UF{parent: make([]int, n), size: make([]int, n), groups: n}
	for i := range u.parent {
		u.parent[i] = i // 1. everyone starts as their own group's root
		u.size[i] = 1
	}
	return u
}

// Find returns the root of x's group, flattening the path as it goes.
func (u *UF) Find(x int) int {
	for u.parent[x] != x {
		u.parent[x] = u.parent[u.parent[x]] // 2. path compression: point at the grandparent
		x = u.parent[x]
	}
	return x
}

// Union merges the groups of a and b. It reports false if they were already together.
func (u *UF) Union(a, b int) bool {
	ra, rb := u.Find(a), u.Find(b)
	if ra == rb {
		return false // 3. already connected: this edge would close a cycle
	}
	if u.size[ra] < u.size[rb] {
		ra, rb = rb, ra
	}
	u.parent[rb] = ra // 4. attach the smaller tree under the larger
	u.size[ra] += u.size[rb]
	u.groups--
	return true
}

Why each part exists:

The real solutions

Number of connected components — start with n groups and subtract one for every successful union:

// CountComponents: number of connected components in an undirected graph of n nodes.
func CountComponents(n int, edges [][]int) int {
	u := NewUF(n)
	for _, e := range edges {
		u.Union(e[0], e[1])
	}
	return u.groups
}

Redundant connection — the first edge whose two ends are already connected is the one that closes the loop:

// FindRedundantConnection: the edge that closes a cycle in a graph that was a tree plus one extra edge.
// The input has n nodes and n edges, so nodes 1..n fit in n+1 slots. If both ends are already connected, this edge makes the cycle.
func FindRedundantConnection(edges [][]int) []int {
	u := NewUF(len(edges) + 1) // nodes are labelled 1..n
	for _, e := range edges {
		if !u.Union(e[0], e[1]) {
			return e
		}
	}
	return nil
}

Number of provinces — the same idea over an adjacency matrix:

// FindCircleNum: number of friend groups in an adjacency matrix.
func FindCircleNum(connected [][]int) int {
	n := len(connected)
	u := NewUF(n)
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			if connected[i][j] == 1 {
				u.Union(i, j)
			}
		}
	}
	return u.groups
}

Valid tree — a tree has exactly n - 1 edges and no cycle:

// ValidTree: n nodes form a tree if there are exactly n-1 edges and no edge closes a cycle.
func ValidTree(n int, edges [][]int) bool {
	if len(edges) != n-1 {
		return false
	}
	u := NewUF(n)
	for _, e := range edges {
		if !u.Union(e[0], e[1]) {
			return false
		}
	}
	return true
}

For graph searches that need paths, distances or an ordering, see Graphs.

Complexity

α is the inverse Ackermann function. It is below 5 for any input that fits in memory, so treat each operation as constant.

Common mistakes

Practice ladder

Ordered Easy → Hard. For each, decide: do connections arrive over time, and do I need the path or only the yes/no?

1. 1.
   Find if Path Exists in Graph

   Only a yes/no connectivity question.
   Easy
2. 2.
   Number of Provinces
   Medium
3. 3.
   Number of Connected Components in an Undirected Graph
   Medium
4. 4.
   Graph Valid Tree

   How many edges does a tree on n nodes have?
   Medium
5. 5.
   Redundant Connection

   Which edge joins two items already together?
   Medium
6. 6.
   Accounts Merge

   Treat each shared email as a connection.
   Medium
7. 7.
   Number of Islands II

   Land is added over time.
   Hard

Which pattern? Drills

Unlabeled problems — pick the pattern, then read why.