Disjoint Set Union — Concept¶
Party-তে friend circles মিশে যাচ্ছে: groups কেবল একসাথে বড় হয়, আর সবার একটাই প্রশ্ন — "আমরা কি এখনো একই circle-এ?"
Real-life analogy: party-র friend circles¶
Party শুরু হয় সবাই একা দাঁড়িয়ে — প্রত্যেকে নিজের নিজের circle। তারপর পরিচয়পর্ব শুরু হয়:
- Alice-এর সাথে Bob-এর দেখা → তাদের circle দুটো মিশে এক হয়ে যায়।
- Carol-এর সাথে Dave-এর দেখা → আরেকটা merged circle।
- Bob-এর সাথে Carol-এর দেখা → এখন চারজনই এক circle, কারণ Bob-এর circle-এর সাথে Carol-এর circle merge করা মানে দুই circle-এর সবাইকে টেনে আনা।
দুটো জিনিস এটাকে নিখুঁত DSU model বানায়:
- Circles শুধু merge-ই হয়, কখনো split না। কেউ কারো সাথে un-meet করে না। এই merge-only দুনিয়াতেই DSU বাস করে।
- প্রতিটা circle-এর একজন spokesperson আছে। দুজন মানুষ একই circle-এ কিনা check করতে তুমি সবাইকে interview করো না — প্রত্যেককে শুধু জিজ্ঞেস করো "তোমার circle-এর spokesperson কে?" Same spokesperson → same circle। Spokesperson-কেই DSU বলে representative।
প্রতিটা DSU operation আসলে party-র দুটো move-এর একটা: আমার spokesperson খোঁজো (find) আর এক spokesperson-কে আরেকজনের অধীনে এনে দুটো circle merge করো (union)।
Memory picture: এক array-র ভেতরে একটা forest¶
DSU প্রতিটা group-কে রাখে "কে কাকে point করে"-র একটা tree হিসেবে, আর সব tree মিলে — পুরো forest টা — থাকে একটামাত্র parent array-তে। parent[x] হলো x যাকে point করে; যে node নিজেকেই point করে, সে একটা root — তার tree-র representative।
শুরু: 6 জন মানুষ (0–5), সবাই একা। ছয়টা ছোট্ট এক-node tree:
parent: index 0 1 2 3 4 5
value [0, 1, 2, 3, 4, 5] <- everyone points at themselves
forest: (0) (1) (2) (3) (4) (5) six roots, six groups
union(0, 1) আর union(2, 3)-এর পরে (এক root ঝোলে অন্যটার নিচে):
union(1, 3)-এর পরে — খেয়াল করো, আমরা 1 আর 3-কে সরাসরি জুড়ি না। আমরা তাদের roots খুঁজি (0 আর 2) আর root-কে root-এর সাথে জুড়ি:
এখন find(3) হাঁটে 3 → 2 → 0 আর উত্তর দেয় 0। find(1) হাঁটে 1 → 0 আর উত্তর দেয় 0। Same representative → same group, আর আমরা node 4 বা 5-কে ছুঁইওনি। BFS/DFS-এর সাথে তুলনা করো, যারা আনন্দে পুরো graph চষে বেড়াত।
Array-টাই IS the structure। কোনো node object নেই, কোনো adjacency list নেই — element প্রতি স্রেফ একটা integer।
Core invariants¶
- Root rule:
parent[r] == rঠিক roots-দের জন্যই; প্রতিটা group-এর ঠিক একটাই root — তার representative। - Membership rule:
find(x) == find(y)iff x আর y একই group-এ। (সরাসরিparent[x] == parent[y]compare করাই হলো classic bug — tree flat না হলে parents কিন্তু representatives না।) - Component count rule: group-এর সংখ্যা = root-এর সংখ্যা, আর প্রতিটা successful union (দুটো আলাদা root) সেটা ঠিক 1 করে কমায়।
- Merge-only rule: unions কখনো split করে না।
ununionবলে কিছু নেই (reverse-time processing হলো standard workaround — নিচের patterns দেখো)।
দুটো optimization (magic-টা এখানেই থাকে)¶
Naive DSU একটা লম্বা chain-এ পরিণত হতে পারে — তখন find-এর খরচ O(n)। দুটো সস্তা trick সেটা ঠেকায়, আর দুটো মিলে DSU-কে computer science-এর দ্রুততম structures-এর একটা বানিয়ে দেয়।
Optimization 1: path compression (find-এর ভেতরে)¶
Root-এর দিকে উঠতে উঠতে, পথে পড়া প্রতিটা node-কে সরাসরি root-এ re-point করো। যে হাঁটাটা এইমাত্র দিলে, সেটা আর কখনো দিতে হবে না।
Tree-টা ব্যবহারের মধ্য দিয়েই নিজেকে flatten করে — যেমন পায়ে-হাঁটা পথ একসময় পাকা রাস্তা হয়ে যায়। Frame-by-frame version visual-explanation.md-এ।
Optimization 2: union by size (union-এর ভেতরে)¶
দুটো root merge করার সময়, ছোট tree-টাকে বড়টার নিচে ঝোলাও। ছোট tree-র nodes root থেকে এক step দূরে সরে; বড় tree-র nodes নড়েই না। কোনো node-এর distance-to-root কেবল তখনই বাড়তে পারে যখন তার tree মেশে অন্তত সমান বড় কোনো tree-তে — তাই depth বাড়ার প্রতিবার তার tree অন্তত দ্বিগুণ হয়, যা ঘটতে পারে বড়জোর log2(n) বার। Trees অগভীর থাকে।
(সহোদর variant "union by rank" size-এর বদলে আনুমানিক একটা height track করে; দুটোই কাজ করে। Size বেশি বন্ধুত্বপূর্ণ, কারণ size number গুলো নিজেরাই কাজে লাগে — "আমার island কত বড়?")
ঠিক কত fast? Inverse Ackermann note¶
দুটো optimization সহ, n elements-এ m operations-এর খরচ O(m · α(n)), যেখানে α হলো inverse Ackermann function। Friendly version: α(n) হলো বাস্তবে তোমার দেখা সবচেয়ে ধীরে-বাড়া function — observable universe-এর atom সংখ্যার চেয়ে ছোট প্রতিটা n-এর জন্য α(n) ≤ 4। তাই প্রতিটা operation-কে constant time ধরো; interview-তে বলো "amortized near-constant, inverse Ackermann" আর এগিয়ে যাও। কেউ তোমাকে এটা prove করতে বলবে না (proof-টা সত্যিই কঠিন); symbol-টার মানে জানাই expected level।
কখন DSU ব্যবহার করবে — আর কখন না¶
DSU ব্যবহার করো যখন:
- তোমার শুধু "same group?" আর "merge groups" লাগবে — paths না, distances না।
- Edges/connections সময়ের সাথে আসে আর queries তাদের মাঝে মাঝে ঢোকে (dynamic connectivity)।
- Undirected edges-এর জন্য একটা cycle guard দরকার (Kruskal's MST, redundant-edge problems)।
- Shared attribute দিয়ে records group করছ (email দিয়ে accounts, color region দিয়ে pixels)।
DSU ব্যবহার করো না যখন:
- Nodes-দের মধ্যকার আসল path বা distance দরকার — DSU ওসব সব ভুলে যায়; BFS/DFS/Dijkstra ব্যবহার করো (
../09-graphs/)। - Edges directed — DSU-র connectivity স্বভাবগতভাবেই symmetric।
- Connections remove করতে হবে — DSU split করতে পারে না (যদি না সময় উল্টো করে process করতে পারো)।
- Graph fixed আর একবারই traverse করছ — plain DFS components সমান fast আর তর্কসাপেক্ষে simpler।
Complexity table¶
| Operation | Naive (no tricks) | Path compression + union by size |
|---|---|---|
find(x) |
O(n) worst case (chain) | O(α(n)) amortized ≈ O(1) |
union(x, y) |
O(n) worst case | O(α(n)) amortized ≈ O(1) |
connected(x, y) |
O(n) | O(α(n)) amortized ≈ O(1) |
| Space | O(n) | O(n) — parent + size arrays |
| m operations total | O(m·n) | O(m · α(n)) ≈ O(m) |
Traversal দিয়ে q-টা connectivity query-র উত্তরের সাথে তুলনা করো: O(q · (V + E)) versus DSU-র O((q + E) · α(V))। দশ লাখ query, দশ লাখ-edge graph-এ — পার্থক্যটা মিনিট আর millisecond-এর।
ছোট ছোট snippets, dry run সহ¶
1. পুরো structure-টা বারো লাইনে¶
parent = list(range(6)) # [0,1,2,3,4,5] — everyone their own root
size = [1] * 6
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path halving: skip a generation
x = parent[x]
return x
def union(x, y):
rx, ry = find(x), find(y)
if rx == ry:
return False # already together — no merge
if size[rx] < size[ry]:
rx, ry = ry, rx # rx is now the bigger root
parent[ry] = rx # smaller hangs under bigger
size[rx] += size[ry]
return True
Dry run: union(0,1) → roots 0,1 আলাদা, sizes tie, parent[1]=0, size[0]=2, returns True। union(1,0) → দুটোই find করে 0-তে, returns False। ওই True/False return-টা সোনার খনি: সে বলে "এই edge-টা সত্যিই নতুন কিছু connect করল।"
2. Edges stream হতে হতে components গোনা¶
components = 6
for u, v in [(0,1), (2,3), (1,3), (4,5)]:
if union(u, v):
components -= 1
print(components) # 2 -> groups {0,1,2,3} and {4,5}
Dry run: শুরু 6-এ। Edge (0,1) merge করে → 5। Edge (2,3) merge করে → 4। Edge (1,3) জোড়া দুটোকে merge করে → 3। Edge (4,5) merge করে → 2। প্রতিটা successful union ঠিক একটা group সরায় — invariant-টা তোমার হয়ে অঙ্ক করে দিচ্ছে।
3. এক comparison-এ cycle detection¶
edges = [(0,1), (1,2), (2,0)] # a triangle
for u, v in edges:
if not union(u, v): # u and v ALREADY connected...
print("cycle closed by", (u, v)) # ...so this edge closes a loop
কাজ করে কেন: একটা undirected cycle-এর দরকার দুটো already-connected node-এর মধ্যে একটা edge। union-এর False return করাই ঠিক সেই detection — কোনো DFS coloring লাগে না। এটাই Redundant Connection-এর পুরো solution।
DSU pattern catalog¶
DSU-র moving parts কম, তাই এর patterns আসলে এই নিয়ে: কী union করছ আর সাথে কোন extra data চড়ছে।
Pattern A — Dynamic connectivity¶
Trigger words: "after each connection", "process queries online", "are X and Y connected now"। Idea: edges আসতে আসতে DSU maintain করো; connected প্রতিটা query-র উত্তর দেয় O(α)-তে। Thinking tweak: traversal প্রতি query-তে দুনিয়াটা নতুন করে compute করে; DSU queries-এর মাঝে দুনিয়াটা মনে রাখে। Problems: Find if Path Exists in Graph, Number of Islands II।
Pattern B — Undirected graph-এ cycle detection¶
Trigger words: "redundant edge", "edge that can be removed", "is this a valid tree"। Idea: edges-গুলোকে union-এ খাওয়াও; প্রথম False-ই cycle-closer। Valid tree = ঠিক n−1 edges আর শূন্য False। Inherits from: ../09-graphs/concept.md-এর "tree + one extra edge = one cycle" fact। Problems: Redundant Connection, Graph Valid Tree।
Pattern C — Kruskal's MST connection¶
Trigger words: "minimum cost to connect everything", "cheapest network"। Idea: edges-কে weight ascending-এ sort করো; যে edge-এর union সফল, সেটা নাও; cycle-closers skip করো। DSU হলো সেই O(α) cycle guard, যেটা Kruskal-এর greedy loop-কে fast করে। Thinking tweak: greedy ঠিক করে order (cheap আগে — ../08-heap-priority-queue/patterns.md-এর heap+greedy combo-গুলোর মতো); DSU উত্তর দেয় "এই edge-টা কি নষ্ট হবে?" একই sort-then-union কঙ্কাল threshold problems-ও solve করে, যেমন Swim in Rising Water: height order-এ cells union করো যতক্ষণ না start আর goal connect হয়।
Pattern D — Records grouping আর merging¶
Trigger words: "merge accounts", "group items sharing any attribute", "equivalence classes"। Idea: nodes-দের graph-ঘেঁষা হতেই হবে না — কোনো key (একটা email, একটা row, একটা constraint a==b) share করা যেকোনো দুটো record union করো, তারপর records-কে find দিয়ে bucket করো। Thinking tweak: DSU আসলে একটা equivalence-relation engine — reflexive, symmetric, আর transitive যা কিছু ("email share করে, transitively") — তা-ই DSU-আকৃতির। Inherits from: ../05-hashing/-এর hash-map bucketing। Problems: Accounts Merge, Satisfiability of Equality Equations, Smallest String With Swaps।
Pattern E — Reverse-time tricks (সামনের এক ঝলক)¶
DSU delete করতে পারে না — কিন্তু সব deletion আগে থেকে জানা থাকলে (offline), সময়টা উল্টো করে process করো: final state থেকে শুরু করো আর প্রতিটা deletion-কে একটা addition বানিয়ে দাও। "Walls being removed" উল্টোদিকে হয়ে যায় "walls being added"। Trick-টা তুলে রাখো; competitive programming জুড়ে এটা বারবার ফিরে আসে।
পরের ধাপের সাথে bridge¶
visual-explanation.mdunions আর path compression frame by frame animate করে।implementation.pyবারো লাইনটাকে cycle-detection আর component demos সহ একটা tested class-এ package করে।- Proofs আর extensions সহ reference treatment: cp-algorithms DSU।