Module 09 · DSA · Four patterns the ladders lean on

Who is in my group? (union-find)

Before you start. Graphs (BFS, DFS, Dijkstra, topological sort) gave you dots and the lines between them, and the question “can I get from here to there?” Clinic #26: Redundant Connection used a small tool to find the one cable that closes a loop: every dot keeps a pointer to another dot, and following pointers upward ends at a dot that points at itself. That clinic built the tool and used it. This lesson is about the tool itself: why it is nearly free, and when to pick it over a plain walk through the graph.

Lesson 68 of 74 in DSA

The rest of this lesson is part of a plan.

A plan opens every lesson, board, video, lab and paper on chalk. Yearly is $39/year, or $19.50 for your first year with LAUNCH50, ends 1 Nov, 18:30 UTC.

See plans Already a member? Sign in

Or start free: a free account opens lessons 2 and 3 of every track.

In this lesson

1964: a compiler has to work out who shares a box
The disjoint set: groups that never overlap and only ever merge
find: follow pointers to the root
union: glue two groups by pointing one root at the other
The slow day: a chain a million items long
Path compression: tidy the chain on the way up
Union by rank: hang the small group under the big one
How fast, with both habits together
The bare structure: parent list, find, union
Path compression: watching a chain flatten
The whole class: union by size, groups counted, cycle as False
The measurement: parent hops on a chain of 1,000,000
Union-find against a plain walk: when each wins

Terms it explains: disjoint set, root, find, union, union-find, path compression, union by rank, inverse Ackermann function.

Review DSA

Connects to

The running total (prefix sums and difference arrays)The stack that stays sorted (monotonic stack and deque)

Index

Open everything on chalk.

Who is in my group? (union-find)

In this lesson