Problem link ও উৎস
- **Original source:** Classic reachability exercise
- **Platform:** LeetCode —
- **Topic:** graphs
- **Difficulty:** Easy
- **Pattern:** reachability (BFS / DFS traversal)
- **Basic idea inherited from:** queue দিয়ে BFS ([../../04-stack-and-queue/](../../04-stack-and-queue/README.md)); first-arrival traversal
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
`n` টা node (`0` থেকে `n-1` পর্যন্ত নম্বর দেওয়া) আর কিছু undirected `edges` দেওয়া আছে। তোমাকে দুটো node দেওয়া হবে — `source` আর `destination`। বলো: edge ধরে হেঁটে কি `source` থেকে `destination`-এ আদৌ পৌঁছানো যায়? শুধু হ্যাঁ/না — পথের দৈর্ঘ্য বা পথটা কী, কিছুই লাগবে না।
```text
0 -- 1 -- 2 source = 0, destination = 2 -> True (0->1->2)
0 -- 1 3 -- 4 source = 0, destination = 4 -> False (আলাদা দ্বীপ)
```
### Input ও output {#8-example-input-and-output}
```text
Input : n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
Output: True
Input : n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
Output: False
Edge case (একটাই node): n = 1, edges = [], source = 0, destination = 0 -> True
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা শহরের road map ভাবো ([../concept.md](../concept.md)-এর সেই map)। মোড়গুলো node, রাস্তাগুলো edge। তুমি বাসা (`source`) থেকে stadium (`destination`)-এ যেতে পারবে কিনা জানতে চাও। তুমি বাসা থেকে বেরিয়ে এক এক করে পৌঁছানো-যায় এমন প্রতিটা মোড়ে যাও, দেখা মোড় গুলো মনে রাখো (যাতে ঘুরে না আসো)। stadium-এ যদি পৌঁছাও — হ্যাঁ; পুরো এলাকা ঘুরেও না পেলে — না।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
মূল ভিত হলো **queue দিয়ে BFS** ([../../04-stack-and-queue/](../../04-stack-and-queue/README.md))। একটা queue জিনিসগুলো arrival order-এ process করে; BFS সেই queue-তে start node ঢুকিয়ে দিয়ে বারবার front pop করে আর তার unseen neighbors enqueue করে। "পৌঁছানো যায় কি" প্রশ্নটা মানেই — start থেকে traversal চালিয়ে দেখো destination কখনো queue-তে আসে কিনা।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: **reachability হলো connectivity।** `source` থেকে `destination`-এ পথ আছে তখনই, যখন তারা একই connected component-এ থাকে। BFS (বা DFS) start node থেকে যা যা ছোঁয়া সম্ভব সব ছুঁয়ে ফেলে — পুরো component-টা। তাই destination যদি সেই ছোঁয়া-set-এ আসে, পথ আছে; না এলে নেই। `visited` set নিশ্চিত করে প্রতিটা node বড়জোর একবার process হয়, cycle থাকলেও loop হয় না।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
- **Adjacency list** (`dict` of lists) — edge list থেকে বানানো; undirected বলে প্রতিটা edge দুই দিকেই যোগ হয়।
- **Queue** (`collections.deque`) — BFS frontier ধরে রাখে; arrival order বজায় রাখে।
- **Visited set** — কোন node ইতিমধ্যে claim হয়েছে, যাতে cycle-এ আটকে না যাই।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Adjacency list fit করে কারণ real graph sparse — প্রতিটা node হাতে গোনা কয়েকটাকে ছোঁয়, আর neighbor list করতে লাগে শুধু O(deg)। Queue fit করে কারণ BFS-এর গোটা চরিত্রই first-in-first-out: যা আগে discover হয়, আগে explore হয়। Visited set fit করে কারণ graph পেছনে loop করতে পারে — set ছাড়া BFS চিরকাল ঘুরতে থাকত।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সরল চিন্তা: source থেকে সব সম্ভাব্য পথ চেষ্টা করে দেখি destination-এ পৌঁছায় কিনা — প্রতিটা branch-এ recurse করে, সব সম্ভাবনা ঘুরে।
```text
পথ খোঁজো 0 থেকে:
0 -> 1 -> 2 ? পৌঁছে গেছে!
অন্য candidate: 0 -> 2, এটিও goal-এ পৌঁছায়। visited ছাড়া cycle-এ ফিরে যাওয়ার ঝুঁকি থাকে।
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
`visited` ছাড়া সব পথ আলাদা করে ঘোরা **exponential** হয়ে যেতে পারে — একই node বারবার ভিন্ন পথে ছোঁয়া হয়, আর cycle থাকলে চিরকাল ঘোরে। আসল কথা: কোন *পথে* পৌঁছালাম তা পাত্তা দিই না, শুধু পৌঁছানো-যায় কিনা চাই। তাই প্রতিটা node একবার ছুঁলেই যথেষ্ট — visited set দিয়ে O(V + E)-তে নামা যায়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **প্রতিটা node বড়জোর একবার visit করলেই reachability পুরো বোঝা হয়ে যায়।** একবার কোনো node "ছোঁয়া" হয়ে গেলে তার থেকে যা যা পৌঁছানো যায়, সেগুলো একবারই explore করলে চলে — আবার এলে নতুন কিছু পাওয়ার নেই।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
Edge list থেকে adjacency list বানাও। source-কে queue আর visited-এ রাখো। তারপর: front pop করো, প্রতিটা unseen neighbor-কে mark করে enqueue করো; কোনো neighbor destination হলেই `True`। Queue খালি হয়ে গেলে আর কিছু পৌঁছানোর নেই — `False`। একই কাজ DFS দিয়েও হয় (queue-র জায়গায় stack); reachability-তে দুটোই সমান।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "সব পথ খুঁজব" না ভেবে ভাবো "source-এর component-টা পুরো ছুঁয়ে ফেলব আর দেখব destination সেই component-এ পড়ল কিনা।" path enumeration থেকে নেমে এসো একবারের traversal-এ।
### ছবিতে বোঝা {#7-visual-explanation}
`n = 3`, `edges = [[0,1],[1,2],[2,0]]`, `source = 0`, `destination = 2`:
```text
adjacency list:
0 -> [1, 2]
1 -> [0, 2]
2 -> [1, 0]
BFS (queue front .. back):
start: seen = {0} queue = [0]
pop 0 -> neighbor 1 (নতুন, enqueue), 2 == destination! -> True
0
/ \
1---2 <- 2 destination, 0 থেকে সরাসরি পৌঁছানো যায়
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`n = 6`, `edges = [[0,1],[0,2],[3,5],[5,4],[4,3]]`, `source = 0`, `destination = 5`:
1. adjacency: `0:[1,2]`, `1:[0]`, `2:[0]`, `3:[5,4]`, `5:[3,4]`, `4:[5,3]`
2. `seen = {0}`, `queue = [0]`
3. pop `0` → neighbor `1` (নতুন, enqueue), `2` (নতুন, enqueue)। কেউ destination 5 না।
4. pop `1` → neighbor `0` (seen)। নতুন কিছু না।
5. pop `2` → neighbor `0` (seen)। নতুন কিছু না।
6. queue খালি। `5` কখনো ছোঁয়া হয়নি → return `False`। (5 অন্য component-এ।)
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
from collections import deque, defaultdict
def valid_path(n, edges, source, destination):
if source == destination: # নিজের কাছে নিজে — সবসময় পৌঁছানো যায়
return True
adj = defaultdict(list)
for u, v in edges:
adj[u].append(v)
adj[v].append(u) # undirected: দুই দিকেই register করো
seen = {source}
q = deque([source]) # queue: ../../04-stack-and-queue/ থেকে
while q:
node = q.popleft() # front pop (FIFO)
for nxt in adj[node]:
if nxt == destination:
return True
if nxt not in seen:
seen.add(nxt) # push করার সময় mark করো (pop-এ নয়)
q.append(nxt)
return False
# ---- tests ----
assert valid_path(3, [[0, 1], [1, 2], [2, 0]], 0, 2) is True
assert valid_path(6, [[0, 1], [0, 2], [3, 5], [5, 4], [4, 3]], 0, 5) is False
assert valid_path(1, [], 0, 0) is True # একটাই node
assert valid_path(2, [[0, 1]], 0, 1) is True
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `if source == destination: return True` — শুরু আর শেষ এক হলে পথ আছেই (length-0 path)।
- `adj[u].append(v)` / `adj[v].append(u)` — undirected, তাই edge দুই দিকেই বসাও; এই দ্বিগুণ লাইন ভুললে অর্ধেক graph হারিয়ে যায়।
- `seen = {source}` / `q = deque([source])` — start node একসাথে visited আর queue-তে।
- `q.popleft()` — `deque`-এর O(1) front pop; `list.pop(0)` ব্যবহার করলে BFS চুপিচুপি quadratic হয়ে যায়।
- `if nxt == destination: return True` — destination ছোঁয়ামাত্র থামো।
- `seen.add(nxt)` ঠিক `q.append(nxt)`-এর পাশে — push করার সময় mark, যাতে একই node queue-তে বারবার না ঢোকে।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`valid_path(3, [[0,1],[1,2],[2,0]], 0, 2)`: adjacency `0:[1,2]`। pop 0 → neighbor 1 enqueue, তারপর 2 == destination → `True`। দ্বিতীয় test-এ 0 আর 5 আলাদা component, queue খালি হয়ে `False`। বাকি দুটোও মেলে। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(V + E)** — adjacency list বানাতে O(V + E), আর BFS-এ প্রতিটা node একবার pop হয়, প্রতিটা edge constant সংখ্যকবার দেখা হয়।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(V + E)** — adjacency list O(V + E), আর queue ও visited set মিলে O(V)।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- undirected graph-এ edge শুধু এক দিকে যোগ করা (`adj[u].append(v)` করে `adj[v].append(u)` ভুলে যাওয়া) — অর্ধেক পথ গায়েব।
- `seen.add` কে pop-এর সময় করা — তখন একই node queue-তে বহুবার ঢুকে BFS ফুলে যায়।
- `deque`-এর বদলে `list` দিয়ে `pop(0)` — প্রতি pop O(n), পুরো BFS quadratic।
- `source == destination` edge case না ভাবা (যদিও এখানে আগেই ধরা হয়েছে)।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: queue-র FIFO আচরণ ([../../04-stack-and-queue/](../../04-stack-and-queue/README.md)) আর graph traversal ([../bfs.md](../bfs.md))। এটা সেই six-line BFS reachability — [../concept.md](../concept.md)-এর "stadium-এ পৌঁছাতে পারব?" snippet-এরই problem রূপ। এখান থেকেই components, shortest path, multi-source — সব BFS-পরিবার শুরু।
### পরের অনুশীলন {#22-similar-harder-problems}
- Number of Provinces (পুরো graph-এ কয়টা component) —