Problem link ও উৎস
- **Original source:** CSES Problem Set — Building Roads
- **Platform:** CSES —
- **Topic:** disjoint set union
- **Difficulty:** Easy
- **Pattern:** components − 1 (connect all components)
- **Basic idea inherited from:** [../../09-graphs/](../../09-graphs/README.md)-এর connected-components; এখানে component গুনে তাদের জোড়ার রাস্তা ছাপাই
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
`n` টা city আর `m` টা existing road দেওয়া। তোমাকে বলতে হবে — সব city-কে একসাথে যুক্ত করতে **সবচেয়ে কম কয়টা নতুন road** লাগবে, আর কোন কোন জোড়া city-র মধ্যে সেগুলো বানাতে হবে। (CSES-এ city 1..n; আমরা ভেতরে 0-indexed ধরব।)
```text
n = 4, roads = (1-2) (3-4) [0-indexed: (0-1) (2-3)]
দুটো আলাদা দল: {1,2} আর {3,4}
এক রাস্তা যোগ করলেই সব যুক্ত -> উত্তর: 1 রাস্তা, যেমন (2-4)
```
### Input ও output {#8-example-input-and-output}
```text
Input : n=4, roads=[(0,1),(2,3)]
Output: 1, [(0,2)]
Input : n=5, roads=[]
Output: 4, [(0,1),(1,2),(2,3),(3,4)] (সবাই একা -> শেকল)
Input : n=3, roads=[(0,1),(1,2)]
Output: 0, [] (আগেই যুক্ত)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো কয়েকটা আলাদা দ্বীপপুঞ্জ, প্রতিটায় ভেতরে সেতু আছে কিন্তু একে অপরের সাথে নেই। সব দ্বীপপুঞ্জকে এক করতে তুমি একটার সাথে আরেকটাকে সেতুতে বাঁধো — `c` টা দ্বীপপুঞ্জ হলে `c − 1` সেতুই যথেষ্ট, একটা লম্বা শেকলের মতো।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
মূল ভিত হলো **connected components বের করা** — [../../09-graphs/](../../09-graphs/README.md)-এর সেই কাজ। যখন তুমি জানো কয়টা আলাদা দল আছে, তখন তাদের একটা শেকলে গাঁথতে লাগে ঠিক **(দল − 1)** টা রাস্তা। DSU দল গোনে আর প্রতি দলের একজন প্রতিনিধি দেয়।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: `c` টা আলাদা component-কে একটা connected graph বানাতে ন্যূনতম **c − 1** edge লাগে — ঠিক যেমন `c` টা গাছকে একটা বনে নয়, একটা শেকলে বাঁধতে c−1 দড়ি লাগে। বেশি দিলে cycle তৈরি হয় (অপচয়); কম দিলে কেউ বিচ্ছিন্ন থেকে যায়। তাই minimum = c − 1, আর প্রতিটা নতুন road দুটো ভিন্ন component জোড়ে।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **DSU** (`parent` + `size`)। প্রথমে existing road union করি; তারপর প্রতিটা component থেকে একজন প্রতিনিধি তুলে তাদের পরপর জুড়ে নতুন road-এর তালিকা বানাই।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
এটা বিশুদ্ধ component প্রশ্ন — "কয়টা দল আর কাকে কার সাথে জুড়ব?" DSU merge-only দুনিয়ায় road union করে দল গড়ে, আর `find` দিয়ে প্রতি node-এর প্রতিনিধি দেয়। প্রতিনিধি দেখে আমরা প্রতি দল থেকে একটা করে node বেছে শেকল বানাতে পারি — পথ/দূরত্ব ছাড়াই।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সরল চিন্তা: adjacency list বানাও, DFS/BFS দিয়ে component বের করো, প্রতিটা component-এর একটা node তালিকায় রাখো, তারপর পরপর জুড়ে দাও।
```text
1) DFS দিয়ে প্রতিটা component label করো
2) প্রতি component থেকে একটা প্রতিনিধি নাও
3) প্রতিনিধিদের পরপর জুড়ে c−1 টা road ছাপাও
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
DFS version ঠিকঠাক — O(n + m)। কিন্তু CSES-এর scale-এ (n, m ১০ লাখ পর্যন্ত) recursive DFS-এ stack overflow-এর ভয়, আর adjacency list গড়ার overhead। DSU iterative, array-ভিত্তিক, recursion-হীন — বড় input-এ নিরাপদ ও পরিষ্কার, একই O(n + m)।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **উত্তরের সংখ্যাটা শুধু component-সংখ্যার উপর নির্ভর — c − 1।** কোন road কোথায় বানাবে তার অসংখ্য valid উত্তর; সবচেয়ে সহজ হলো প্রতি component-এর এক প্রতিনিধিকে একটা শেকলে গাঁথা।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
সব existing road `union` করো। তারপর `find(i)` দিয়ে প্রতিটা distinct root-এর প্রথম node সংগ্রহ করো — এরা প্রতিনিধি। প্রতিনিধি `k` টা হলে তাদের পরপর জুড়ে `k − 1` road বানাও। পুরোটা amortized প্রায় O(n + m)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "প্রতিটা জোড়া city-র জন্য কি আলাদা ভাবতে হবে?" — না। প্রশ্নটাকে নামিয়ে আনো "কয়টা দল আছে?"-এ। দল `c` হলে উত্তর সবসময় `c − 1`; বাকিটা শুধু প্রতিনিধি বেছে শেকল গাঁথা।
### ছবিতে বোঝা {#7-visual-explanation}
existing road union করো, তারপর প্রতি component-এর এক প্রতিনিধি নিয়ে পরপর জোড়ো।
```text
n=5, existing roads: (0-1) (2-3)
শুরু: *0 *1 *2 *3 *4 parent: [0,1,2,3,4] components = 5
union(0,1): *0 *2 *3 *4 parent: [0,0,2,3,4] components = 4
|
1
union(2,3): *0 *2 *4 parent: [0,0,2,2,4] components = 3
| |
1 3
প্রতিনিধি: find(0)=0, find(2)=2, find(4)=4 -> reps = [0, 2, 4]
শেকল: (0-2) (2-4) -> নতুন road = 2 (= components − 1)
*0----নতুন----*2----নতুন----*4
| |
1 3 এখন সব এক component
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `n=5, roads=[(0,1),(2,3)]`:
1. `union(0,1)` → {0,1}; `union(2,3)` → {2,3}; node 4 একা
2. প্রতিনিধি খোঁজা: find(0)=0 (নতুন), find(1)=0 (পুরোনো), find(2)=2 (নতুন), find(3)=2 (পুরোনো), find(4)=4 (নতুন)
3. reps = [0, 2, 4]
4. শেকল: (0,2), (2,4) → নতুন road = 2
5. return `2, [(0,2),(2,4)]`
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
class DSU:
def __init__(self, n):
self.parent = list(range(n)) # প্রথমে সবাই নিজের নিজের root
self.size = [1] * n
def find(self, x): # representative + path compression
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # path halving
x = self.parent[x]
return x
def union(self, x, y): # union by size; merge হলে True
rx, ry = self.find(x), self.find(y)
if rx == ry:
return False
if self.size[rx] < self.size[ry]:
rx, ry = ry, rx
self.parent[ry] = rx
self.size[rx] += self.size[ry]
return True
def building_roads(n, roads):
dsu = DSU(n)
for u, v in roads:
dsu.union(u, v) # existing road দিয়ে দল গড়ো
reps = []
seen = set()
for city in range(n): # প্রতি component-এর প্রথম node
r = dsu.find(city)
if r not in seen:
seen.add(r)
reps.append(city)
new_roads = [(reps[i], reps[i + 1]) for i in range(len(reps) - 1)]
return len(new_roads), new_roads
# ---- tests ----
assert building_roads(4, [(0, 1), (2, 3)]) == (1, [(0, 2)])
assert building_roads(5, []) == (4, [(0, 1), (1, 2), (2, 3), (3, 4)])
assert building_roads(3, [(0, 1), (1, 2)]) == (0, []) # আগেই যুক্ত
assert building_roads(1, []) == (0, []) # একটাই city
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `for u, v in roads: dsu.union(u, v)` — সব existing road দিয়ে component গড়ো।
- `seen` set + `reps` list — প্রতিটা distinct root-এর জন্য একবার করে একটা প্রতিনিধি city তুলে রাখি।
- `if r not in seen` — একই root আগে দেখা থাকলে আবার নেব না; তাই reps-এ প্রতি component থেকে ঠিক একজন।
- `new_roads = [(reps[i], reps[i+1]) ...]` — প্রতিনিধিদের পরপর জুড়ে শেকল; `k` প্রতিনিধি → `k − 1` road।
- `return len(new_roads), new_roads` — সংখ্যা আর তালিকা দুটোই।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
প্রথম test-এ দুই component {0,1},{2,3}; reps=[0,2]; এক road (0,2)। দ্বিতীয়টায় ৫ জন একা; reps=[0,1,2,3,4]; চার road শেকলে। তৃতীয়টায় সব যুক্ত; reps=[0]; কোনো road নয়। single-city-ও 0। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O((n + m) · α(n))** ≈ **O(n + m)** — m টা union, n টা find প্রতিনিধি খুঁজতে; প্রতিটা amortized near-constant।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** — `parent` + `size` + `seen` + `reps`, সবই O(n)।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- উত্তর `c` বলা, `c − 1` নয় — একটা শেকল গাঁথতে দল-সংখ্যার চেয়ে একটা কম দড়ি লাগে।
- প্রতিনিধি বাছার সময় `find` না করে কাঁচা `parent[city]` দেখা — flat না হলে ভুল প্রতিনিধি।
- CSES-এর 1-indexed city ভুলে 0-indexed ছাপানো (input/output-এ ±1 মেলানো জরুরি)।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: [../../09-graphs/](../../09-graphs/README.md)-এর connected components। DFS-এ তুমি component label করতে; এখানে DSU দিয়ে union করে প্রতিনিধি তুলছ। উত্তরের অঙ্ক (c−1) একই থাকে। বড় CP-scale input-এ DSU-র iterative রূপ recursive DFS-এর চেয়ে নিরাপদ।
### পরের অনুশীলন {#22-similar-harder-problems}
- Number of Operations to Make Network Connected (c−1, তবে spare edge গুনে) —