# DSU: নতুন সংযোগ এলে দলগুলো মিলিয়ে রাখা

[অধ্যায়ের সূচি](README.md) · [অনুশীলন ও সমাধান](problems/README.md) · [মূল ধারণা](concept.md)

দুটি শহর একই সড়ক-নেটওয়ার্কে আছে কি না জানতে সব রাস্তা আবার ঘুরতে হবে কেন? নতুন রাস্তা যোগ হলে দুই শহরের **দল** মিলিয়ে রাখা যায়। DSU এই দলগুলোর membership সংরক্ষণ করে। এটি মূল graph-এর route সংরক্ষণ করে না।

## শেখার ক্রম

1. [Find, union ও representative](concept.md) পড়ুন। Representative একটি label; সর্বনিম্ন node হওয়া বাধ্যতামূলক নয়।
2. [Parent array ও forest পাশাপাশি](visual-explanation.md) দেখুন। Forest-এর link মূল রাস্তার edge নয়।
3. [Union-by-size এবং path halving-এর code](implementation.py) চালান।
4. [Practice tracker](problems/README.md) থেকে reachability → components → cycle → grouping নিন।

## একটি প্রোগ্রাম: নতুন রাস্তার পরে network report

শহর A, B, C, D। প্রতিটি নতুন রাস্তার পরে জানতে হবে কতটি আলাদা দল আছে এবং সবচেয়ে বড় দলে কত শহর।

| যোগ হওয়া রাস্তা | দলগুলো | দল-সংখ্যা | সবচেয়ে বড় দল |
| --- | --- | --- | --- |
| শুরু | {A}, {B}, {C}, {D} | 4 | 1 |
| A–B | {A,B}, {C}, {D} | 3 | 2 |
| C–D | {A,B}, {C,D} | 2 | 2 |
| B–C | {A,B,C,D} | 1 | 4 |
| A–D | {A,B,C,D} | 1 | 4 |

শেষ রাস্তার দুই endpoint আগেই একই দলে। তাই `union(A,D)` false ফেরত দেয়; component count কমবে না। Undirected graph-এ এই অতিরিক্ত edge একটি cycle তৈরি করে।

```mermaid
flowchart BT
  B["B"] --> A["A: root, size 4"]
  C["C"] --> A
  D["D"] --> C
```

এই ছবিতে arrow `node → parent`। `find(D)` পথে D → C → A যায়। Full path compression করলে D সরাসরি A-কে point করবে; membership একই থাকবে। **শুধু root-এর size নির্ভরযোগ্য**: পুরোনো root C-এর size field রেখে দেওয়া হলেও সেটিকে নতুন component-এর size ভাবা যাবে না।

```mermaid
flowchart BT
  B["B"] --> A["A: root, size 4"]
  C["C"] --> A
  D["D"] --> A
```

## কোথায় ব্যবহার করবেন

| প্রোগ্রাম | Element কী | কখন union | পরে কী পাবেন |
| --- | --- | --- | --- |
| Account merge | Email বা account ID | একই email শেয়ার করলে | একই ব্যক্তির candidate records-এর দল |
| Network dashboard | Computer ID | নতুন cable যোগ হলে | Connected group ও group size |
| Image region grouping | সক্রিয় pixel | পাশের সক্রিয় pixel পেলে | Connected region |
| Kruskal MST | Vertex | সস্তা edge ভিন্ন দল জুড়লে | Cycle ছাড়া নির্বাচিত edge |

Account name এক হওয়া মাত্র union করা যাবে না; problem যে shared identifier-কে প্রমাণ হিসেবে দিচ্ছে সেটি ব্যবহার করতে হবে।

## সীমাবদ্ধতা বুঝলে ভুল tool বাছবেন না

| দরকার | DSU উপযুক্ত? | বিকল্প/কারণ |
| --- | --- | --- |
| কেবল নতুন edge যোগ, অনেক connectivity query | হ্যাঁ | Union-by-size + compression-এ amortized `O(α(n))` |
| দুই node-এর আসল route | না | BFS/DFS-এর parent রাখুন |
| Shortest distance | না | Weight অনুযায়ী BFS/Dijkstra |
| অনলাইনে edge মুছে দল আলাদা করা | সাধারণ DSU পারে না | বিশেষ offline/rollback পদ্ধতি লাগে |
| Directed graph-এর reachability | সাধারণ DSU যথেষ্ট নয় | Direction হারিয়ে যায় |

[Road Construction-এর স্থানীয় নোট](problems/017-road-construction.md) এবং [CSES 1676-এর মূল প্রশ্ন](https://cses.fi/problemset/task/1676) এই report-এর সরাসরি অনুশীলন।