Keep track of which items belong to the same group, and merge groups quickly.
The idea (friend groups)
Imagine a party where people slowly become friends. You want to answer “are Ana and Raj in the same friend group?” and to merge two groups when their members meet. Union-find does both in almost constant time.
Every group is a tree, and the person at the top is the group’s root (its leader). The array parent[i] says who each person points to; a leader points to themselves.
Find(x): follow parents upward until you reach a root. Two people are in the same group if their roots are the same.
Union(a, b): find both roots; if they differ, hang the smaller tree under the bigger tree’s root (union by size), so trees stay short.
Path compression: while walking up in Find, re-point everyone you passed straight at the root. The next Find is almost instant.
Watch it work
Allowed: union A B and find A (items are numbered from 0). At most 15 operations.
Try it
Run the default operations and watch find 3: node 3 jumps straight to the root. That is path compression.
Do union 0 1, union 1 2, union 2 3, union 3 4. Does the tree become a long chain? Why not?
Call union 0 1 twice. What does the second call say?
Merge everything into one group, then find any item.
Common mistakes
Comparing parents instead of roots.parent[a] == parent[b] is wrong unless both are roots. Always compare Find(a) == Find(b).
Forgetting to initialize. Every item must start as its own parent: parent[i] = i, size[i] = 1.
Merging without checking the roots. Linking two items in the same group can create a cycle.
Updating size of the wrong root. Add to the size of the root that stays on top.
Complexity, in plain English: with union by size and path compression each operation is almost constant time (O(α(n)), where α grows so slowly it is below 5 for any input you will ever see). Memory is two small arrays.