3.5.15
Socho friends ke groups hain. Har group ka ek leader hota hai (wo representative root hai). Do logon ko check karna ho ki woh ek hi group mein hain, toh dono ka leader dhundho aur compare karo. Do groups merge karne hon, toh ek leader ko doosre ki taraf point kar do. DSU ki poori trick yahi hai ki "apna leader dhundho" ko almost instant banao — chains ko flatten karke (path compression) aur tree ko kabhi zaroorat se zyada lamba nahi banne dena (union by rank). Dono milke har operation ki cost ko α(n) tak le jaate hain, jo inverse Ackermann function hai, aur jo bhi input tum dekhoge usme ≤ 4 rehta hai.
Definition Disjoint Set Union (DSU / Union-Find)Ek data structure jo disjoint sets ka collection maintain karta hai (koi bhi element do sets mein nahi) aur in operations ko support karta hai:
find(x) → x ke set ka representative (root) return karo.union(x, y) → x aur y wale sets ko merge karo.same(x, y) → find(x) == find(y).
Har set ek rooted tree ki tarah store hota hai; root hi representative hota hai. Hum ek array parent[] store karte hain jahan parent[root] == root.
Definition α(n) — inverse AckermannAckermann function A ( m , n ) α ( n ) dheere badhta hai: α ( n ) ≤ 4 n ≤ 2 2 2 2 16
Intuition Naive approach ka failureOptimization ke bina, union ek root ko doosre ke neeche arbitrarily lata deta hai. Adversarial unions ek linked list bana sakte hain jiska height n find O ( n ) O ( n )
Do alag-alag fixes hain:
Union by rank banane ko control karta hai: hamesha chota tree bade ke neeche lagao, taaki height dheere badhey.Path compression cheezein padhte waqt theek karta hai: find ke baad, visit kiye gaye har node ko seedha root ki taraf point kar do, taaki future finds fast hon.
find banana
Goal: root tak chadhna, phir flatten karna.
def find (x): while parent[x] != x: # not yet root parent[x] = parent[parent[x]] # path halving x = parent[x] return x Yeh step kyun? parent[x] != x exactly yeh test hai ki "kya main root hoon?" (root apni taraf khud point karta hai). Line parent[x] = parent[parent[x]] x ko apna parent skip karke grandparent ki taraf point kara deti hai — path halving , jo bina recursion ke compress karta hai.
Full path compression (recursive) completely flatten karta hai:
def find (x): if parent[x] != x: parent[x] = find(parent[x]) # set parent directly to root return parent[x] Yeh step kyun? Recursion root return karta hai; hum path ke har node ko seedha uski taraf assign kar dete hain, toh unka agla find O ( 1 )
rank[x] x se rooted tree ki height ka ek upper bound hai. Yeh 0 se shuru hota hai. Hum sirf ranks compare karte hain; asli heights ki zaroorat nahi.
union banana
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 Yeh step kyun? Chote tree ko bade ke neeche lagate hain toh combined height = dono ki maximum height hoti hai — yeh badhti nahi . Height tab hi badh sakti hai jab ranks equal hon, aur tab bhi sirf 1 se.
Intuition Dono milke α(n) kyun dete hainUnion by rank guarantee karta hai rank ≤ log n re-flatten karta rehta hai tree ko, toh rank real height ka ek loose over-estimate ban jaata hai. Ek careful amortized analysis (Tarjan) m O ( m α ( n )) α(n) amortized per operation . Hum yahan poora potential-function proof nahi karte, lekin takeaway hai: practically constant time.
Worked example {0..5} par UnionsShuru: 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. Kyun? equal rank tie height badhata hai.union(2,3): parent[3]=2, rank[2]=1.union(0,2): rank[0]rank[2] 1 → parent[2]=0, rank[0]=2. Kyun? phir tie, root 0 ka rank 2 ho gaya.union(4,5): parent[5]=4, rank[4]=1.union(0,4): rank[0]=2 > rank[4]=1 → 4 ko 0 ke neeche lago, parent[4]=0, koi rank change nahi . Kyun? unequal ranks → height already covered hai, koi bump nahi.
Ab find(5): path 5→4→0; compression parent[5]=0 set kar deta hai. Kyun? aage find(5) ek hi hop mein hoga.
size aur union by rank alag algorithms hain alag complexity ke saath."
Kyun sahi lagta hai: dono alag quantities track karte hain (node count vs height bound).
Fix: Dono path compression ke saath same O ( α ( n )) size (chote-count tree ko bade-count ke neeche) often aasaan hai aur utna hi accha. Koi bhi ek consistently use karo.
rank ko path compression ke baad update kar sakta hoon taaki accurate rahe."
Kyun sahi lagta hai: compression height ghata deta hai, toh rank purana lagta hai.
Fix: Mat karo. rank sirf ek upper bound hai jo merge decisions ke liye use hota hai; isko stale rehne dena sahi hai aur analysis exactly yahi assume karti hai. Height recompute karna expensive aur unnecessary hai.
if rx == ry: return bhoolna sirf thodi si inefficiency karta hai."
Kyun sahi lagta hai: kisi set ko khud se merge karna harmless lagta hai.
Fix: Iske bina tum parent[ry]=rx tab kar sakte ho jab ry==rx ho, ya galat rank bump kar sakte ho — structure corrupt ho jaata hai. Hamesha equal roots par early-return karo.
find hai while parent[x]!=x: x=parent[x] — yahi kaafi hai."
Kyun sahi lagta hai: yeh root sahi return karta hai.
Fix: Kaam karta hai lekin slow hai (koi compression nahi). Tum α(n) guarantee kho dete ho. Compression line add karo.
Recall Feynman: 12-saal ke bachche ko samjhaoHar bachcha ek team ka hissa hai, aur har team ka ek captain hota hai. Apna captain dhundhne ke liye tum poochho "tera boss kaun hai?" aur tab tak upar jaate raho jab tak koi nahi bole "main boss hoon" — wahi captain hai. Trick 1 (path compression): upar jaate waqt, jitne log milte hain woh seedha captain ka naam likh lete hain, toh agli baar instantly jawaab dete hain. Trick 2 (union by rank): jab do teams merge hon, choti team ka captain badi team ke captain ko salute karta hai, toh chains kabhi lambi nahi hoti. Dono karo aur "tera captain kaun hai?" practically free ho jaata hai — matlab, billions of kids ke liye bhi kabhi 4 se zyada sawaal nahi.
"COMPRESS the path, RANK the merge."
Find → C ompress (padhte waqt flatten karo).Union → chote R anks bade ranks ke aage jhukein (tie ⇒ +1).
DSU mein parent[x] == x ka kya matlab hai? x apne set ka root / representative hai.
Path compression kya hai? find ke dauran, visited nodes ko seedha (ya grandparent ke zariye) root ki taraf repoint karo taaki future finds fast hon.
Union by rank kya hai? Chote rank wale tree ko bade rank wale ke neeche lagao; tie pe kisi bhi taraf attach karo aur winner ka rank increment karo.
Rank sirf upper bound kyun hai, true height nahi? Path compression trees ko flatten karta hai, toh real height ≤ stored rank hoti hai; hum rank baad mein update nahi karte.
Rank r wale tree mein minimum kitne nodes hote hain? 2 r
Sirf union by rank se max rank / height kitna hoga? ≤ log 2 n ≥ 2 r
Dono optimizations ke saath amortized time per op? O ( α ( n ))
Union mein find(x) == find(y) hone par early-return kyun karte hain? Woh already ek hi set mein hain; merge karna parent pointers / rank corrupt kar dega.
Union by size aur union by rank equivalent hain? Haan, dono path compression ke saath O ( α ( n ))
Practically α(n) ≤ 4 ka matlab kya hai? Kisi bhi realistic n ke liye, har operation effectively constant time leta hai.
Kruskal's Minimum Spanning Tree — edges add karte waqt cycles detect karne ke liye DSU use karta hai.Connected Components — DSU online "same component?" answer karta hai.Trees and Forests — har set ek rooted tree hai; collection ek forest hai.Amortized Analysis — α(n) bound ek potential-function argument se aata hai.Ackermann Function — uska inverse complexity define karta hai.Graph Cycle Detection — union mein same root banna ⇒ undirected graph mein cycle.
hangs shorter under taller in
