Intuition The big pictureImagine groups of friends. Each group has one leader (the representative root ). To check if two people are in the same group, you find each person's leader and compare. To merge two groups, you point one leader at the other. The whole trick of DSU is to make "find your leader" almost instant — by flattening the chains (path compression) and never making the tree taller than necessary (union by rank). Together they push the cost per operation down to α(n) , the inverse Ackermann function, which is ≤ 4 for any input you will ever see.
Definition Disjoint Set Union (DSU / Union-Find)A data structure that maintains a collection of disjoint sets (no element in two sets) and supports:
find(x) → return the representative (root) of x's set.union(x, y) → merge the sets containing x and y.same(x, y) → find(x) == find(y).
Each set is stored as a rooted tree ; the root is the representative. We store one array parent[] where parent[root] == root.
Definition α(n) — inverse AckermannThe Ackermann function A ( m , n ) A(m,n) A ( m , n ) α ( n ) \alpha(n) α ( n ) slowly : α ( n ) ≤ 4 \alpha(n) \le 4 α ( n ) ≤ 4 n ≤ 2 2 2 2 16 n \le 2^{2^{2^{2^{16}}}} n ≤ 2 2 2 2 16
Intuition The naive failureWithout optimization, union just hangs one root under another arbitrarily. Adversarial unions can build a linked list of height n n n find walks O ( n ) O(n) O ( n ) O ( n ) O(n) O ( n )
Two independent fixes:
Union by rank controls the building : always hang the shorter tree under the taller one, so height grows slowly.Path compression fixes things while reading : after a find, point every node visited directly at the root, so future finds are fast.
find
Goal: climb to the root, then flatten.
def find (x): while parent[x] != x: # not yet root parent[x] = parent[parent[x]] # path halving x = parent[x] return x Why this step? parent[x] != x is exactly the test "am I a root?" (root points to itself). The line parent[x] = parent[parent[x]] makes x skip its parent and point to its grandparent — path halving , which compresses without recursion.
Full path compression (recursive) flattens completely :
def find (x): if parent[x] != x: parent[x] = find(parent[x]) # set parent directly to root return parent[x] Why this step? The recursion returns the root; we assign every node on the path to point straight at it, so the next find is O ( 1 ) O(1) O ( 1 )
rank[x] is an upper bound on the height of the tree rooted at x. It starts at 0. We only ever compare ranks; we never need true heights.
union
def union (x, y): rx, ry = find(x), find(y) if rx == ry: return # already same set if rank[rx] < rank[ry]: rx, ry = ry, rx # ensure rx is the taller/equal root parent[ry] = rx # hang smaller under larger if rank[rx] == rank[ry]: rank[rx] += 1 # tie → height grows by 1 Why this step? Hanging the shorter tree under the taller one means the combined height = max of the two heights — it does not increase. Only when ranks are equal can the height grow, and then by just 1.
Intuition Why the two together give α(n)Union by rank guarantees rank ≤ log n \le \log n ≤ log n re-flattening the tree, so the rank becomes a loose over-estimate of the real height. A careful amortized analysis (Tarjan) over a sequence of m m m O ( m α ( n ) ) O(m\,\alpha(n)) O ( m α ( n )) α(n) amortized per operation . We don't reproduce the full potential-function proof here, but the takeaway is: practically constant time.
Worked example Unions on {0..5}Start: parent=[0,1,2,3,4,5], rank=[0,0,0,0,0,0].
union(0,1): roots 0,1, equal rank → parent[1]=0, rank[0]=1. Why? equal rank tie raises height.union(2,3): parent[3]=2, rank[2]=1.union(0,2): rank[0]rank[2] 1 → parent[2]=0, rank[0]=2. Why? tie again, root 0's rank bumps to 2.union(4,5): parent[5]=4, rank[4]=1.union(0,4): rank[0]=2 > rank[4]=1 → hang 4 under 0, parent[4]=0, no rank change . Why? unequal ranks → height already covered, no bump.
Now find(5): path 5→4→0; compression sets parent[5]=0. Why? future find(5) is one hop.
size and union by rank are different algorithms with different complexity."
Why it feels right: they track different quantities (node count vs height bound).
Fix: Both give the same O ( α ( n ) ) O(\alpha(n)) O ( α ( n )) size (hang smaller-count tree under bigger-count) is often easier and equally good. Use either consistently.
Common mistake "I can updaterank after path compression to keep it accurate."
Why it feels right: compression shrinks height, so rank looks stale.
Fix: Don't. rank is only an upper bound used to decide merges; keeping it stale is correct and is exactly what the analysis assumes. Recomputing height is expensive and unnecessary.
Common mistake "Forgettingif rx == ry: return causes only minor inefficiency."
Why it feels right: merging a set with itself seems harmless.
Fix: Without it you may do parent[ry]=rx when ry==rx, or wrongly bump rank — corrupting the structure. Always early-return on equal roots.
find is while parent[x]!=x: x=parent[x] — that's enough."
Why it feels right: it does return the root correctly.
Fix: It works but is slow (no compression). You lose the α(n) guarantee. Add the compression line.
Recall Feynman: explain to a 12-year-oldEvery kid belongs to a team, and each team has one captain. To find your captain you ask "who's your boss?" and keep going up until someone says "I'm the boss" — that's the captain. Trick 1 (path compression): on the way up, everyone you pass writes down the captain's name directly, so next time they answer instantly. Trick 2 (union by rank): when two teams merge, the smaller team's captain salutes the bigger team's captain, so chains never get long. Do both and asking "who's your captain?" is basically free — like, never more than 4 questions even for billions of kids.
"COMPRESS the path, RANK the merge."
Find → C ompress (flatten as you read).Union → small R anks bow to big ranks (tie ⇒ +1).
What does parent[x] == x signify in DSU? x is the root / representative of its set.
What is path compression? During find, repoint visited nodes directly (or via grandparent) toward the root so future finds are faster.
What is union by rank? Hang the tree with smaller rank under the one with larger rank; on a tie, attach either way and increment the winner's rank.
Why is rank only an upper bound, not true height? Path compression flattens trees, so real height ≤ stored rank; we never update rank afterward.
Minimum number of nodes in a tree of rank r? 2 r 2^r 2 r (proved by induction: a rank rises only when two equal-rank roots merge).
Max rank / height with union by rank alone? ≤ log 2 n \le \log_2 n ≤ log 2 n , since a rank-r tree has
≥ 2 r \ge 2^r ≥ 2 r nodes.
Amortized time per op with both optimizations? O ( α ( n ) ) O(\alpha(n)) O ( α ( n )) , inverse Ackermann ≤ 4 in practice.
Why early-return when find(x) == find(y) in union? They're already in the same set; merging would corrupt parent pointers / rank.
Is union by size equivalent to union by rank? Yes, both give
O ( α ( n ) ) O(\alpha(n)) O ( α ( n )) with path compression; size hangs fewer-node tree under larger.
What does α(n) ≤ 4 mean practically? For any realistic n, each operation costs effectively constant time.
Kruskal's Minimum Spanning Tree — uses DSU to detect cycles when adding edges.Connected Components — DSU answers "same component?" online.Trees and Forests — each set is a rooted tree; the collection is a forest.Amortized Analysis — α(n) bound comes from a potential-function argument.Ackermann Function — its inverse defines the complexity.Graph Cycle Detection — union creating same-root ⇒ cycle in undirected graph.
hangs shorter under taller in
Intuition Hinglish mein samjhoDSU yaani Union-Find ka kaam simple hai: tumhare paas kuch groups hain, aur har group ka ek captain (root) hota hai. find(x) poochta hai "tumhara captain kaun hai?" aur union(x,y) do groups ko jodta hai. Pure structure ko ek parent[] array se store karte hain, jahan root apne aap ko hi point karta hai (parent[root]==root).
Bina optimization ke yeh ek lambi chain ban sakti hai — phir har find mein O ( n ) O(n) O ( n ) union by rank : jab do trees merge karo, toh chhoti (kam height wali) tree ko badi tree ke neeche lagao. Isse height kabhi badhti nahi, sirf tie hone par 1 badhti hai. Isse proof nikalta hai ki rank r r r 2 r 2^r 2 r ≤ log 2 n \le \log_2 n ≤ log 2 n
Doosra trick path compression : jab find chalao, toh raste mein jitne nodes aaye sabko seedha root pe point kara do. Agli baar wahi find ek hi hop mein ho jayega. Dono tricks saath lagao toh per-operation cost gir kar α(n) (inverse Ackermann) ho jaati hai — jo practically 4 se kabhi zyada nahi hoti, yaani basically constant time.
Yeh matter isliye karta hai kyunki DSU Kruskal MST , connected components , aur cycle detection jaise problems ka backbone hai. Interview aur competitive programming mein yeh ek must-know hai. Yaad rakhne ka mantra: "Find pe compress karo, Union mein rank dekho."
