Union–Find in one picture

Imagine a bunch of islands (disconnected groups).

• Union = build a bridge between two islands (now they’re one bigger island).
• Find = ask, “Which island is this person on?” If two people have the same island leader, they’re connected.

Under the hood, Union–Find keeps little trees of members with a “representative” at the top. With tricks like path compression and union by rank/size, lookups are basically instant.

Where you’ll use it (especially in interviews)

If the problem smells like connectivity or merging groups, think Union–Find:

• Connected components: “How many groups are there?”
• Cycle detection (undirected graphs): “Does adding this edge create a loop?”
• Grid/maze problems: “Do start and finish end up connected?”
• Network questions: “When does the whole network become connected?”
• Kruskal’s MST: Sorting edges + Union–Find = chef’s kiss.

Quick mental checklist

• Are we merging things over time? → Union
• Are we asking “same group?” a lot? → Find
• Do we care about speed with tons of merges/lookups? → Use DSU with path compression + union by size

Ready to wire up those islands? Let’s make Union–Find do the heavy lifting.