Friend Circles: Everyone Points to a Representative
Imagine 6 people, each starting in their own friend circle. Every person keeps a single pointer: "who do I consider my group's representative?" At first, everyone points to themselves — 6 separate circles.
When two people become friends, we don't merge their whole circles by hand — we just make one representative point to the other. Two people are in the same circle exactly when following their pointers, one hop at a time, leads to the same person at the end of the chain.
This is stored as one flat array, parent[], where parent[i] is the person i currently points to. For 6 people [0,1,2,3,4,5], the starting array is parent = [0,1,2,3,4,5] — everyone points to themselves, so everyone is their own root. After union(0,1), parent becomes [0,0,2,3,4,5] — person 1 now points to person 0, so find(1) walks 1 → 0 and stops (0 points to itself). After union(2,3) and then union(0,2), parent becomes [0,0,0,2,4,5] — now find(3) walks 3 → 2 → 0, so 0, 1, 2, and 3 are all one circle, while 4 and 5 remain alone.
Forest Merge: Union + Path Compression
8 elements, unioned by size. Watch node colors merge as sets combine, and watch step 7 flatten a path when find() is called.
8 elements, each its own set: parent[i] = i for every i.
Path Compression + Union by Size
🚀 Path Compression
During find(), point every node visited on the way to the root directly at the root. This is exactly what happens at step 7 above — find(7) flattens 7's chain from "7 → 6 → 4" down to "7 → 4" so the next lookup is one hop shorter.
⚖️ Union by Size (or Rank)
Always attach the smaller tree under the larger tree's root, never the reverse. Without this, unlucky union order can build a long chain, making find() degrade toward O(N).
The Union-Find Class
How it Works
find(x)walks to the root, compressing the path on the way back up.union(a, b)attaches the smaller tree under the larger one.counttracks the number of distinct sets — decrement it on every successful union.connected(a, b)is justfind(a) === find(b)— the whole point of the structure.
How to Spot This Pattern
🔎 "Are X and Y connected / in the same group?"
🔎 "Number of provinces / circles / islands" after a list of connections.
🔎 "Redundant connection" — find the edge that creates a cycle.
🔎 "Accounts merge" — group records that share any attribute.
🔎 Edges/connections arrive one at a time, and you need to answer queries in between.
Named problems: Number of Provinces · Redundant Connection · Accounts Merge · Most Stones Removed with Same Row or Column · Number of Islands II
Union-Find vs DFS/BFS Connectivity
A single DFS/BFS traversal can answer "what's connected to what" just fine on a fixed, static graph. Union-Find earns its keep the moment the graph changes over time or you need many connectivity queries.
| Situation | Best Tool | Why |
|---|---|---|
| Static graph, one query | DFS / BFS | One O(V+E) traversal answers everything you need; no extra structure to maintain. |
| Dynamic edges / many queries | Union-Find | Each union/find is ~O(1) amortized — re-running DFS after every new edge would be far too slow. |
Common Mistakes
Forgetting Path Compression
Without it, an unlucky union order can build a long chain, and find() degrades toward O(N) per call instead of near O(1).
Comparing Roots After the Union
Writing union(a, b); find(a) === find(b) to "check if a union happened" is always true — of course they match, you just unioned them. Capture whether the union actually merged two different roots (most implementations return that as a boolean).
Rank vs Size, and Indexing
Don't mix "union by rank" (tree height) with "union by size" (node count) in the same implementation — pick one. And watch for 1-indexed problem inputs against a 0-indexed parent array; an off-by-one here silently corrupts every union.
Ready to Practice?
"Flatten the path, balance by size, and unite the disjoint into one."