# Disjoint Set Union — Concept

[অধ্যায়ের সূচি](README.md) · [সহজ ব্যাখ্যা ও বাস্তব ব্যবহার](learning-guide.md) · [অনুশীলন ও সমাধান](problems/README.md)

> 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 বানায়:

1. **Circles শুধু merge-ই হয়, কখনো split না।** কেউ কারো সাথে un-meet করে না। এই merge-only দুনিয়াতেই DSU বাস করে।
2. **প্রতিটা 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:

```text
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 ঝোলে অন্যটার নিচে):

```text
parent: [0, 0, 2, 2, 4, 5]

forest:    0       2       (4)   (5)
           |       |
           1       3
```

`union(1, 3)`-এর পরে — খেয়াল করো, আমরা 1 আর 3-কে সরাসরি জুড়ি না। আমরা তাদের **roots** খুঁজি (0 আর 2) আর root-কে root-এর সাথে জুড়ি:

```text
parent: [0, 0, 0, 2, 4, 5]

forest:      0         (4)   (5)
            / \
           1   2
               |
               3
```

এখন `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 করো**। যে হাঁটাটা এইমাত্র দিলে, সেটা আর কখনো দিতে হবে না।

```text
before find(4):   0            after find(4):        0
                  |                                / | \
                  1                               1  2  4
                  |                                  |
                  2                              (3 untouched —
                  |                               it was not on the path)
                  4
```

Tree-টা ব্যবহারের মধ্য দিয়েই নিজেকে flatten করে — যেমন পায়ে-হাঁটা পথ একসময় পাকা রাস্তা হয়ে যায়। Frame-by-frame version [visual-explanation.md](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/](../09-graphs/README.md))।
- 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-টা বারো লাইনে

```python
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 গোনা

```python
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

```python
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](https://leetcode.com/problems/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](https://leetcode.com/problems/find-if-path-exists-in-graph/), [Number of Islands II](https://leetcode.com/problems/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](../09-graphs/concept.md)-এর "tree + one extra edge = one cycle" fact। **Problems:** [Redundant Connection](https://leetcode.com/problems/redundant-connection/), [Graph Valid Tree](https://leetcode.com/problems/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](../08-heap-priority-queue/patterns.md)-এর heap+greedy combo-গুলোর মতো); DSU উত্তর দেয় "এই edge-টা কি নষ্ট হবে?" একই sort-then-union কঙ্কাল threshold problems-ও solve করে, যেমন [Swim in Rising Water](https://leetcode.com/problems/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/](../05-hashing/README.md)-এর hash-map bucketing। **Problems:** [Accounts Merge](https://leetcode.com/problems/accounts-merge/), [Satisfiability of Equality Equations](https://leetcode.com/problems/satisfiability-of-equality-equations/), [Smallest String With Swaps](https://leetcode.com/problems/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.md](visual-explanation.md) unions আর path compression frame by frame animate করে।
- [implementation.py](implementation.py) বারো লাইনটাকে cycle-detection আর component demos সহ একটা tested class-এ package করে।
- Proofs আর extensions সহ reference treatment: [cp-algorithms DSU](https://cp-algorithms.com/data_structures/disjoint_set_union.html)।