10 — Disjoint Set Union (DSU / Union-Find)¶

একটামাত্র ছোট্ট array, দুটো ছোট্ট function, near-constant time — আর "এই দুজন কি একই group-এ?" এর উত্তর দেয় যেকোনো traversal-এর চেয়ে দ্রুত।

এই data structure টা কী¶

Disjoint Set Union (যাকে Union-Find-ও বলে) একগুচ্ছ non-overlapping group maintain করে। এটা ঠিক দুটো operation support করে:

find(x) — x কোন group-এ আছে? (Group-টার representative return করে।)
union(x, y) — x আর y-র group দুটো এক করে দাও।

ব্যস, এটাই পুরো interface। ভেতরে, প্রতিটা group হলো "কে কাকে point করে"-র একটা ছোট tree, যা একটামাত্র parent array-তে রাখা। দুটো বিখ্যাত optimization সহ — path compression আর union by size/rank — দুটো operation-ই কার্যত constant time-এ চলে।

DSU edges, paths, বা neighbors store করে না। সে একটাই প্রশ্নের উত্তর দেয় — "same group or not?" — আর সেটা দেয় অবিশ্বাস্য দ্রুত।

এটা কেন আছে (কোন pain solve করে)¶

ধরো connections একটা একটা করে আসছে — বন্ধুত্ব তৈরি হচ্ছে, network cable লাগানো হচ্ছে — আর প্রতিটার পরে তোমাকে উত্তর দিতে হবে "A আর B কি এখন connected?"

Graph traversal দিয়ে (../09-graphs/), প্রতিটা query মানে একটা নতুন BFS/DFS: প্রশ্ন প্রতি O(V + E)। হাজার query মানে graph-টা হাজারবার নতুন করে হাঁটা।
Connections শুধু groups merge-ই করে, কখনো split করে না। Traversal অপচয় করে এটা ভুলে যায়; যা আগেই জানা ছিল তা শুরু থেকে আবার recompute করে।

DSU এই merge-only স্বভাবটাকেই কাজে লাগায়: সে group structure-টাকে incrementally up to date রাখে, তাই প্রতিটা find আর union-এর খরচ amortized near-O(1)। দশ লাখ operation শেষ হয় মোটামুটি দশ লাখ step-এ — মোট, প্রত্যেকটায় না।

Real software-এ কোথায় ব্যবহার হয়¶

Kruskal's minimum spanning tree — কোনো edge cycle তৈরি করবে কিনা, DSU O(α)-তে ঠিক করে দেয়।
Network connectivity monitoring — "এই দুটো machine কি একই segment-এ?"
Image processing — connected-component labeling পাশাপাশি একই-রঙা pixels merge করে।
Account/entity deduplication — একই email বা phone number share করা user accounts merge করা।
Compilers আর type checkers — type inference-এর unification আসলে অন্তরে union-find।
Physics আর games — percolation simulation, ধাক্কা-খাওয়া object-দের cluster merge করা।
Maze generation — শুধু তখনই দেয়াল ভাঙো যখন সেটা দুটো আলাদা region জোড়ে (Kruskal-style mazes)।

Prerequisites¶

Solid Python: lists, dicts, functions, classes।
Arrays আর indices (../02-arrays-and-strings/) — পুরো structure-টাই একটা array।
Tree-র vocabulary: parent, root (../07-trees/)।
Basic graph ideas: nodes, edges, connected components (../09-graphs/concept.md)।

শেখার আগে কী revise করবে¶

DFS দিয়ে connected components (../09-graphs/dfs.md) — DSU একই প্রশ্নের উত্তর দেয় অন্যভাবে; দুটোর তুলনা করাই দুটোই বোঝার দ্রুততম পথ।
এই fact: V nodes-এর একটা tree-তে ঠিক V − 1-টা edge থাকে, আর যেকোনো extra edge যোগ করলে ঠিক একটা cycle তৈরি হয়।
Dynamic arrays-এর "amortized" cost (../02-arrays-and-strings/) — DSU-র near-O(1)-ও একই ঘরানার একটা amortized দাবি।

Learning goals (checklist)¶

[ ] Parent-array forest ছবিটা explain করতে পারা: প্রতিটা group একটা tree, প্রতিটা tree-র root হলো representative।
[ ] Path compression সহ find implement করা আর compression tree-কে কী করে — explain করতে পারা।
[ ] Size দিয়ে union implement করা আর ছোট tree কেন বড়টার নিচে ঝোলে — explain করতে পারা।
[ ] Invariant টা বলতে পারা: find(x) == find(y) iff x আর y একই group-এ।
[ ] Edges stream হতে হতে DSU দিয়ে connected components গুনতে পারা।
[ ] একটা find comparison দিয়েই undirected graph-এ cycle-তৈরি-করা edge টা detect করতে পারা।
[ ] Kruskal's MST কীভাবে DSU-কে তার cycle guard হিসেবে ব্যবহার করে — sketch করতে পারা।
[ ] Inverse Ackermann function α(n)-এর মানে এক friendly বাক্যে বলতে পারা।
[ ] কোনো connectivity problem-এ DSU vs BFS/DFS বাছাই করা আর সিদ্ধান্তটা defend করতে পারা।
[ ] "accounts merge"-ধাঁচের একটা grouping problem শুরু থেকে শেষ পর্যন্ত solve করতে পারা।

Problem categories¶

Category	Typical question shape
Dynamic connectivity	"After each new edge, are A and B connected? How many groups remain?"
Cycle detection (undirected)	"Find the edge that closes a cycle / can be removed"
Component counting	"How many islands / provinces / networks?"
Grouping / merging records	"Merge accounts sharing an email", "group similar items"
Kruskal's MST	"Cheapest set of edges connecting everything"
Offline / reverse-time tricks	"Process removals as reversed additions"

Practice list¶

নিচের সব problem আমাদের নিজেদের ভাষায় বর্ণনা করা; official statement-এর জন্য link follow করো। Difficulty label গুলো আনুমানিক।

Easy¶

Problem	Source	Pattern
Find if Path Exists in Graph — reachability, এবার traversal ছাড়া	LeetCode 1971	Dynamic connectivity
Number of Provinces — friend cluster গোনো	LeetCode 547	Component counting
Building Roads — সব শহর connect করতে minimum রাস্তা	CSES — Building Roads	Component counting (answer = components − 1)

Medium¶

Problem	Source	Pattern
Redundant Connection — যে edge টা cycle বন্ধ করে সেটা খোঁজো	LeetCode 684	Cycle detection
Number of Operations to Make Network Connected — spare cables নতুন করে লাগাও	LeetCode 1319	Components + spare-edge counting
Accounts Merge — যেকোনো email share করা accounts merge করো	LeetCode 721	Grouping / merging records
Most Stones Removed with Same Row or Column — row/column ধরে stones union করো	LeetCode 947	Creative union keys
Satisfiability of Equality Equations — a==b আর a!=b constraints process করো	LeetCode 990	Union equals, then check not-equals
Smallest String With Swaps — index group-এর ভেতরে যত খুশি swap	LeetCode 1202	Group then sort inside groups
Number of Islands — land region গোনো (DFS classic-এর DSU variant)	LeetCode 200	Component counting on a grid
Graph Valid Tree — ঠিক একটা component, শূন্য cycle	LeetCode 261	Cycle detection + component count

Hard¶

Problem	Source	Pattern
Swim in Rising Water — সবচেয়ে আগে কখন grid পার হওয়া যায়	LeetCode 778	Sort cells by height, union until connected (Kruskal flavor)
Making A Large Island — পানি থেকে ডাঙায় best একটা flip	LeetCode 827	Component sizes + neighbor merging
Number of Islands II — islands আসে এক cell করে	LeetCode 305	Dynamic connectivity (DSU's home turf)
Road Construction — প্রতিটা নতুন রাস্তার পরে components আর largest size	CSES Problem Set — "Road Construction"	Dynamic connectivity + size tracking
Redundant Connection II — directed, আরও প্যাঁচালো ভাইটা	LeetCode 685	Cycle + double-parent case analysis

Visualization ideas¶

Parent array-টা আঁকো এক সারি বাক্স হিসেবে, আর তার উপরে forest-টা trees হিসেবে; প্রতিটা operation-এর পরে দুটোই আবার আঁকো আর মিলিয়ে দেখো।
union-কে animate করো এমনভাবে: একটা tree-কে তুলে অন্য tree-র root-এর নিচে ঝুলিয়ে দেওয়া হচ্ছে।
Path compression-কে animate করো একটা "flattening" হিসেবে: একটা find-এর পরেই, হাঁটা path-এর প্রতিটা node সরাসরি root-এর নিচে চলে আসে।
Component count-কে track করো এমন এক counter হিসেবে যা প্রতিটা successful union-এ ঠিক 1 করে কমে।
Interactive: VisuAlgo-র Union-Find module; reference write-up cp-algorithms DSU-এ।

Common mistakes (সাধারণ ভুল)¶

find(x) == find(y)-র বদলে parent[x] == parent[y] compare করা — tree পুরো flat না হলে parents কিন্তু representatives না।
union(x, y)-কে parent[x] = y হিসেবে লেখা — সেটা nodes জোড়ে, x-এর পুরোনো subtree-কে এতিম করে দিতে পারে। সবসময় root to root link করো।
Path compression বা union by size ভুলে যাওয়া: প্রত্যেকে এককভাবেই জিনিসটা fast রাখে; কোনোটাই না থাকলে worst-case O(n) chain হতে পারে।
বিশাল input-এ Python-এর recursion limit না বাড়িয়ে find-এ recursion ব্যবহার করা — iterative two-pass version-টা ঝামেলাই এড়িয়ে যায়।
ভুলে যাওয়া যে DSU শুধু undirected connectivity handle করে — directed reachability-র জন্য অন্য tool লাগে।
DSU-র কাছে group splitting আশা করা — un-union বলে কিছু নেই (reverse-time processing হলো workaround)।
Label-এর type গুলিয়ে ফেলা: nodes string হলে আগে তাদের integer-এ map করো (বা dict-based parent ব্যবহার করো)।

Interview problem-এর সাথে connection¶

Big-tech interview preparation-এ DSU একটা প্রিয় "elegant tool": Redundant Connection, Accounts Merge, Number of Provinces-এর মতো problem-এর traversal solution আছে, কিন্তু DSU solution-টা ছোট, দ্রুত, আর শক্তিশালী data-structure fluency-র signal দেয়। Classic interview মুহূর্তটা: খেয়াল করা যে problem-টার শুধু "same group?" লাগবে — paths না — আর জোরে বলা "this is union-find"। Streaming variant-গুলোর (Number of Islands II) কোনো clean traversal solution-ই নেই; DSU-ই intended path।

Competitive programming-এর সাথে connection¶

DSU competitive programming-এর top-tier workhorse: code করতে ছোট, TLE করানো প্রায় অসম্ভব।
Kruskal's MST (DSU-র সবচেয়ে বিখ্যাত client) প্রতিনিয়ত আসে Codeforces-এ আর CSES Problem Set-এ।
Offline tricks — queries sort করা, deletions উল্টো করে additions হিসেবে process করা — এর reach বহুগুণ বাড়িয়ে দেয়।
পরে যেসব extension-এর সাথে দেখা হবে: DSU with rollback, weighted/parity DSU ("merging-এর মধ্যে bipartite checks"), small-to-large merging। সামনের পথের জন্য দেখো cp-algorithms DSU আর USACO Guide।

Recommended learning order (পরামর্শমতো শেখার ক্রম)¶

concept.md — friend-circles analogy, parent-array forest, দুটো optimization, patterns।
visual-explanation.md — unions-এ trees-এর merge আর compression-এ তাদের flatten হওয়া, frame by frame।
implementation.py — পড়ো, চালাও, ভাঙো, ঠিক করো।
problems/README.md — tracker শুরু করো আর grind করো, easy থেকে hard।
তারপর ফিরে যাও ../09-graphs/problems/-এ আর Number of Provinces ও Swim in Rising Water আবার solve করো DSU দিয়ে — দুটো solution-এর তুলনা দুটো tool-কেই পাকা করে।

Source map¶

এই folder-এর প্রতিটা idea আর link কোথা থেকে এসেছে আর প্রত্যেকটার copying status কী — দেখো source-map.md-এ।