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

> **এখান থেকে শুরু করুন:** [সহজ ব্যাখ্যা, শেখার ক্রম ও বাস্তব ব্যবহার](learning-guide.md) → [প্রশ্ন, official link ও স্থানীয় সমাধান](problems/README.md)। [উৎসের তালিকা](source-map.md)-এ reference পাবেন।

> একটামাত্র ছোট্ট 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/](../09-graphs/README.md)), প্রতিটা 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/](../02-arrays-and-strings/README.md)) — পুরো structure-টাই একটা array।
- Tree-র vocabulary: parent, root ([../07-trees/](../07-trees/README.md))।
- Basic graph ideas: nodes, edges, connected components ([../09-graphs/concept.md](../09-graphs/concept.md))।

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

- DFS দিয়ে connected components ([../09-graphs/dfs.md](../09-graphs/dfs.md)) — DSU একই প্রশ্নের উত্তর দেয় অন্যভাবে; দুটোর তুলনা করাই দুটোই বোঝার দ্রুততম পথ।
- এই fact: V nodes-এর একটা tree-তে ঠিক V − 1-টা edge থাকে, আর যেকোনো extra edge যোগ করলে ঠিক একটা cycle তৈরি হয়।
- Dynamic arrays-এর "amortized" cost ([../02-arrays-and-strings/](../02-arrays-and-strings/README.md)) — 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 ছাড়া · [ব্যাখ্যা](problems/001-find-if-path-exists-dsu.md) | [LeetCode 1971](https://leetcode.com/problems/find-if-path-exists-in-graph/) | Dynamic connectivity |
| Number of Provinces — friend cluster গোনো · [ব্যাখ্যা](problems/002-number-of-provinces-dsu.md) | [LeetCode 547](https://leetcode.com/problems/number-of-provinces/) | Component counting |
| Building Roads — সব শহর connect করতে minimum রাস্তা · [ব্যাখ্যা](problems/003-building-roads-dsu.md) | [CSES — Building Roads](https://cses.fi/problemset/task/1666) | Component counting (answer = components − 1) |

### Medium

| Problem | Source | Pattern |
| --- | --- | --- |
| Redundant Connection — যে edge টা cycle বন্ধ করে সেটা খোঁজো · [ব্যাখ্যা](problems/005-redundant-connection.md) | [LeetCode 684](https://leetcode.com/problems/redundant-connection/) | Cycle detection |
| Number of Operations to Make Network Connected — spare cables নতুন করে লাগাও · [ব্যাখ্যা](problems/006-make-network-connected.md) | [LeetCode 1319](https://leetcode.com/problems/number-of-operations-to-make-network-connected/) | Components + spare-edge counting |
| Accounts Merge — যেকোনো email share করা accounts merge করো · [ব্যাখ্যা](problems/009-accounts-merge.md) | [LeetCode 721](https://leetcode.com/problems/accounts-merge/) | Grouping / merging records |
| Most Stones Removed with Same Row or Column — row/column ধরে stones union করো · [ব্যাখ্যা](problems/011-most-stones-removed.md) | [LeetCode 947](https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/) | Creative union keys |
| Satisfiability of Equality Equations — a==b আর a!=b constraints process করো · [ব্যাখ্যা](problems/007-equality-equations.md) | [LeetCode 990](https://leetcode.com/problems/satisfiability-of-equality-equations/) | Union equals, then check not-equals |
| Smallest String With Swaps — index group-এর ভেতরে যত খুশি swap · [ব্যাখ্যা](problems/008-smallest-string-with-swaps.md) | [LeetCode 1202](https://leetcode.com/problems/smallest-string-with-swaps/) | Group then sort inside groups |
| Number of Islands — land region গোনো (DFS classic-এর DSU variant) · [ব্যাখ্যা](problems/010-number-of-islands-dsu.md) | [LeetCode 200](https://leetcode.com/problems/number-of-islands/) | Component counting on a grid |
| Graph Valid Tree — ঠিক একটা component, শূন্য cycle · [ব্যাখ্যা](problems/004-graph-valid-tree.md) | [LeetCode 261](https://leetcode.com/problems/graph-valid-tree/) | Cycle detection + component count |

### Hard

| Problem | Source | Pattern |
| --- | --- | --- |
| Swim in Rising Water — সবচেয়ে আগে কখন grid পার হওয়া যায় · [ব্যাখ্যা](problems/015-swim-in-rising-water-dsu.md) | [LeetCode 778](https://leetcode.com/problems/swim-in-rising-water/) | Sort cells by height, union until connected (Kruskal flavor) |
| Making A Large Island — পানি থেকে ডাঙায় best একটা flip · [ব্যাখ্যা](problems/014-making-a-large-island.md) | [LeetCode 827](https://leetcode.com/problems/making-a-large-island/) | Component sizes + neighbor merging |
| Number of Islands II — islands আসে এক cell করে · [ব্যাখ্যা](problems/013-number-of-islands-ii.md) | [LeetCode 305](https://leetcode.com/problems/number-of-islands-ii/) | Dynamic connectivity (DSU's home turf) |
| Road Construction — প্রতিটা নতুন রাস্তার পরে components আর largest size · [ব্যাখ্যা](problems/017-road-construction.md) | [CSES 1676 · Road Construction](https://cses.fi/problemset/task/1676) | Dynamic connectivity + size tracking |
| Redundant Connection II — directed, আরও প্যাঁচালো ভাইটা · [ব্যাখ্যা](problems/016-redundant-connection-ii.md) | [LeetCode 685](https://leetcode.com/problems/redundant-connection-ii/) | 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](https://visualgo.net/en)-র Union-Find module; reference write-up [cp-algorithms DSU](https://cp-algorithms.com/data_structures/disjoint_set_union.html)-এ।

## 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](https://codeforces.com/problemset/)-এ আর [CSES Problem Set](https://cses.fi/problemset/)-এ।
- 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](https://cp-algorithms.com/data_structures/disjoint_set_union.html) আর [USACO Guide](https://usaco.guide/)।

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

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

## Source map

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