# DSU — group জোড়া দেওয়া ও পথ ছোট করা

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

DSU-তে `parent[x]` বলে x থেকে root খুঁজতে পরের কোন node-এ যাব। Root নিজেকেই parent বলে। **Union দুই root-কে জোড়ে; find root খুঁজে এবং চলার পথ ছোট করতে পারে।**

## Union — ছয়টি group থেকে একটি

শুরুতে 0–5 প্রত্যেকেই আলাদা root। ছোট group-কে বড়টির নিচে রাখব। Size সমান হলে এই উদাহরণে প্রথম argument-এর root জিতবে। বাক্সের index হলো element; ভেতরের value হলো তার parent।

```dsa
kind: array
title: প্রতিটি union-এর পরে সম্পূর্ণ parent array
steps:
  - label: শুরু — 6টি group
    values: [0, 1, 2, 3, 4, 5]
    note: প্রত্যেকে নিজেই root; প্রতিটি group-এর size 1।
  - label: union(0, 1) — 5টি group
    values: [0, 0, 2, 3, 4, 5]
    active: [1]
    note: Size সমান। parent[1] = 0; root 0-এর size এখন 2।
  - label: union(2, 3) — 4টি group
    values: [0, 0, 2, 2, 4, 5]
    active: [3]
    note: parent[3] = 2; root 2-এর size এখন 2।
  - label: union(1, 3) — 3টি group
    values: [0, 0, 0, 2, 4, 5]
    active: [2]
    note: Roots 0 ও 2। দুই group-এর size 2; parent[2] = 0, size[0] = 4।
  - label: union(4, 5) — 2টি group
    values: [0, 0, 0, 2, 4, 4]
    active: [5]
    note: parent[5] = 4; root 4-এর size এখন 2।
  - label: union(5, 0) — 1টি group
    values: [0, 0, 0, 2, 0, 4]
    active: [4]
    note: Roots 4 ও 0। Size 2 < 4, তাই parent[4] = 0; size[0] = 6।
```

`union(1,3)`-তে সরাসরি 1-এর সঙ্গে 3 জোড়া হয় না। আগে `find(1)` পথে `1 → 0`, আর `find(3)` পথে `3 → 2` যায়। তারপর **root 2-এর parent** বদলায়। তার নিচে থাকা 3 নিজে না সরেও একই group-এর অংশ হয়ে যায়।

শেষ forest নিচে। Arrow **child থেকে parent**-এর দিকে; root-এর self-loop আঁকা হয়নি।

```mermaid
flowchart BT
  n1((1)) --> n0["0 · root · size 6"]
  n2((2)) --> n0
  n4((4)) --> n0
  n3((3)) --> n2
  n5((5)) --> n4
```

| Union-এর পরে | সম্পূর্ণ size array | অর্থপূর্ণ root size |
| --- | --- | --- |
| শুরু | `[1,1,1,1,1,1]` | সবাই 1 |
| `(0,1)` | `[2,1,1,1,1,1]` | 0-এর size 2 |
| `(2,3)` | `[2,1,2,1,1,1]` | 0 ও 2-এর size 2 |
| `(1,3)` | `[4,1,2,1,1,1]` | 0-এর size 4 |
| `(4,5)` | `[4,1,2,1,2,1]` | 0-এর size 4, 4-এর size 2 |
| `(5,0)` | `[6,1,2,1,2,1]` | শুধু 0-এর size 6 |

Non-root-এর পুরোনো size মুছে দেওয়া হয়নি; সিদ্ধান্ত নিতে **শুধু root-এর size** ব্যবহার করি। ছোট group বড়টির নিচে গেলে ছোট group-এর node-গুলোর depth এক বাড়ে। কোনো node-এর depth বাড়ার জন্য তার group-এর size অন্তত দ্বিগুণ হয়; তাই compression ছাড়াও height `O(log n)` থাকে।

## Full path compression — একই root, ছোট পথ

বোঝানোর জন্য এবার আলাদা একটি দীর্ঘ chain নিই: `parent = [0,0,1,2,3]`। এটি আগের union-by-size ধাপগুলোর ফল নয়। `find(4)` প্রথমে `4 → 3 → 2 → 1 → 0` যায়—চারটি edge। Full compression সেই পথের node-গুলোকে সরাসরি 0-এর সঙ্গে জুড়ে দেয়।

```mermaid
flowchart BT
  subgraph before["আগে: find(4)-এ 4টি edge"]
    b4((4)) --> b3((3)) --> b2((2)) --> b1((1)) --> b0["0 · root"]
  end
  subgraph after["পরে: find(4)-এ 1টি edge"]
    a1((1)) --> a0["0 · root"]
    a2((2)) --> a0
    a3((3)) --> a0
    a4((4)) --> a0
  end
```

```dsa
kind: array
title: Full compression-এর আগে ও পরে
steps:
  - label: আগে
    values: [0, 0, 1, 2, 3]
    note: Root-এ পৌঁছাতে 4 থেকে চারটি parent pointer অনুসরণ করতে হয়।
  - label: find(4)-এর পরে
    values: [0, 0, 0, 0, 0]
    active: [2, 3, 4]
    note: 2, 3 ও 4-এর parent বদলেছে। 1 আগেই root-কে point করছিল।
```

Compression **শুধু যে পথে যায় সেই path** বদলায়। উদাহরণ: `[0,0,0,1,3]` থেকে `find(4)` পথ `4 → 3 → 1 → 0` ছোট করে; node 2-তে যায় না। ফল `[0,0,0,0,0]` পুরো flat দেখালেও 2 আগে থেকেই root-এ ছিল। অন্য শাখা থাকলে সেটি নিজে থেকে flat হতো না।

## Implementation-এ path halving

[implementation.py](implementation.py)-র iterative `find` full compression-এর বদলে **path halving** করে: বর্তমান node-কে তার grandparent-এর সঙ্গে জোড়ে, তারপর সেই grandparent-এ যায়।

```python
while parent[x] != x:
    parent[x] = parent[parent[x]]
    x = parent[x]
```

দুই পদ্ধতির ফল এক pass-এ একরকম নাও হয়। একই chain-এ `find(4)` দিয়ে পার্থক্য দেখো:

| পদ্ধতি | `parent` শুরু | একটি `find(4)` শেষে | 4 থেকে root-এর পথ |
| --- | --- | --- | --- |
| Full compression | `[0,0,1,2,3]` | `[0,0,0,0,0]` | `4 → 0` |
| Path halving | `[0,0,1,2,3]` | `[0,0,0,2,2]` | `4 → 2 → 0` |

Halving-এ প্রথমে `parent[4]=2`, এরপর `parent[2]=0` হয়। পরের find পথ আরও ছোট করতে পারে। Union-by-size-এর সঙ্গে দুই পদ্ধতিরই amortized সময় `O(α(n))`, যা ব্যবহারিক input-এ খুব ছোট।

## Find ও union একসঙ্গে — `union(3,5)`

শুরু `parent = [0,0,0,2,4,4]`। Groups `{0,1,2,3}` ও `{4,5}`। এবার path halving ব্যবহার করি।

| ধাপ | কাজ | ফল |
| --- | --- | --- |
| 1 | `find(3)` পথে `3 → 2 → 0` | `parent[3]=0`; root 0 |
| 2 | `find(5)` পথে `5 → 4` | root 4; parent বদলায় না |
| 3 | Size 4 ও 2 তুলনা | ছোট root 4-কে 0-এর নিচে রাখি |
| 4 | Group count কমাই | 2 থেকে 1 |

```mermaid
flowchart BT
  n1((1)) --> n0["0 · root · size 6"]
  n2((2)) --> n0
  n3((3)) --> n0
  n4((4)) --> n0
  n5((5)) --> n4
```

শেষ parent array `[0,0,0,0,0,4]`। 5 এখনো 4-কে point করে—এটি ভুল নয়। Union-এর পরে পুরো tree আবার flatten করার দরকার নেই; পরের `find(5)` তার পথ ছোট করবে।

## নিজে চেষ্টা করো

1. ছয়টি singleton থেকে `union(2,4)`, `union(0,2)`, `union(3,5)`, `union(4,5)` করো। প্রতিবার parent array লেখো। শেষে 2টি group থাকবে।
2. Chain `0 ← 1 ← 2 ← 3`-এ full compression সহ `find(3)` করে আগে-পরে array লেখো।
3. প্রথম অনুশীলনের final state-এ কোন union নতুন group জোড়া দিতে পারবে না? Root দিয়ে ব্যাখ্যা করো।
4. `parent = [1,2,2,2,3]`-এ path halving সহ `find(0)` করলে কোন cell বদলায়?

চলমান উদাহরণ: [VisuAlgo Union-Find](https://visualgo.net/en/ufds)। আরও পড়া: [cp-algorithms DSU](https://cp-algorithms.com/data_structures/disjoint_set_union.html)।