LESSON 22 · PATTERN GUIDE

Union Find / DSU

Track disjoint connected groups with near-constant amortized merge and find operations.

FIRST, LEARN THE PATTERNFind identifies a set representative; union merges two sets. Path compression and union by size keep trees shallow.

The task repeatedly joins components, detects redundant connections, or asks whether two nodes are connected.

How to approach it

Initialize every item as its own parent, find roots with compression, and attach the smaller tree under the larger one.

Watch out for

DSU supports connectivity merges but not arbitrary edge removals or path distances.

A CLOSER EXPLANATION

DSU represents each connected component as a parent-pointer tree. Path compression flattens the route during find, while union by size attaches the smaller tree below the larger. Together they make many connectivity operations almost constant time in practice.

NOW YOU TRY

Practice question

Starting with 5 separate components, merge (0,1), (1,2), and (3,4). How many components remain?

EXAMPLEn = 5; unions = [(0,1), (1,2), (3,4)]Give your answer before revealing the explanation.

Show a hint

Each successful merge reduces the component count by one.

Show an answer

2 components.

CONNECT IT TO REAL LIFE

Union Find / DSU at work

Initially six towns are disconnected. New roads connect A–B, B–C, D–E, and E–F. How many separate road-connected groups remain?

Show one possible approach

Two groups: {A,B,C} and {D,E,F}. Each union joins two previously separate components and reduces the component count by one.

Practice next

Use these problem IDs to find additional practice for this pattern:

547684131915799901202