Problem link ও উৎস
- **Original source:** "অদ্ভুত statement-কে graph-এ model করা"-র classic প্রয়োগ
- **Platform:** LeetCode —
- **Topic:** graphs
- **Difficulty:** Hard
- **Pattern:** BFS on transformed graph (node = route, edge = shared stop)
- **Basic idea inherited from:** modeling habit (এই repo-র "nodes কী, edges কী" অভ্যাস)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে কতগুলো bus route দেওয়া আছে; `routes[i]` মানে i-নম্বর bus পরপর ওই stop-গুলোতে থামে (আর route-টা চক্রাকারে চলতে থাকে)। তুমি `source` stop-এ দাঁড়িয়ে আছ আর `target` stop-এ যেতে চাও। তুমি যেকোনো bus-এ চড়তে আর নামতে পারো। সবচেয়ে কম **কয়টা bus** নিলে target-এ পৌঁছানো যায়, সেটা বের করো; না পারলে -1। (একই stop হলে 0।)
```text
routes = [[1, 2, 7], [3, 6, 7]]
source = 1, target = 6
bus 0 (stop 1,2,7)-এ চড়ে stop 7-এ নামি, সেখানে bus 1 (3,6,7) ধরি, stop 6-এ নামি।
2 টা bus -> উত্তর: 2
```
### Input ও output {#8-example-input-and-output}
```text
Input : routes = [[1,2,7],[3,6,7]], source=1, target=6
Output: 2
Input : routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source=15, target=12
Output: -1
Edge case (source == target): routes=[[1,2,7],[3,6,7]], source=1, target=1 -> 0
Edge case (এক bus-ই যথেষ্ট): routes=[[1,7]], source=1, target=7 -> 1
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো শহরের bus-map। তুমি stop-গুলো নিয়ে মাথা ঘামাচ্ছ না; তোমার আসল প্রশ্ন — "কয়টা bus বদলাতে হবে।" তাই তুমি প্রতিটা bus line-কে একটা বিন্দু ভাবো, আর দুটো line-এর মধ্যে যোগ আছে যদি তাদের কোনো common stop থাকে (যেখানে তুমি transfer করতে পারো)। source stop থেকে যত line ধরা যায় সব ধরো (layer 1), তাদের transfer-stop থেকে যত নতুন line ধরা যায় (layer 2) — যে layer-এ target-ছোঁয়া line পাবে, সেটাই কম bus-সংখ্যা।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা দাঁড়িয়ে এই repo-র সবচেয়ে কেন্দ্রীয় অভ্যাসের উপর: **"আমার node কী, edge কী"** (README-র modeling বাক্য)। ভুল modeling করলে problem-টা জট পাকিয়ে যায়; সঠিক modeling করলে সেটা সাধারণ BFS-এ মিলিয়ে যায়। এখানে চালাকি — node হিসেবে stop নয়, **route** নাও। একই stop share করা দুটো route-এর মধ্যে edge, আর "কয়টা bus" = এই route-graph-এ BFS-এর layer-সংখ্যা। unweighted, তাই [../shortest-path.md](../shortest-path.md)-এর প্রথম row: plain BFS, deque।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic হলো graph-এর সঠিক রূপান্তর। যদি stop-কে node ধরো, তবে একই route-এর সব stop পরস্পরের সাথে যুক্ত — তাতে edge-সংখ্যা বিস্ফোরিত হয় (একটা route-এ m stop হলে `m^2` edge)। কিন্তু "কয়টা bus" আসলে route-পরিবর্তনের সংখ্যা। তাই node = route ধরলে, একটা bus নেওয়া = একটা route-node visit করা, আর BFS-এর layer ঠিক bus-সংখ্যা গোনে। মূল গণিত: একই stop দুটো route-কে এক ধাপে যুক্ত করে (এক bus থেকে আরেক bus-এ transfer)।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
তিনটা: (১) একটা **dict (defaultdict)** — `stop -> কোন কোন route সেই stop ছোঁয়`, এটাই route-graph-এর adjacency-র ভিত্তি; (২) একটা **deque** — BFS-এর FIFO queue; (৩) দুটো **set** — visited routes আর visited stops, যাতে কিছু দুবার process না হয়।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
`stop -> routes` dict fit করে কারণ "এই stop-এ দাঁড়িয়ে কোন কোন bus ধরা যায়" প্রশ্নটা বারবার লাগে, আর dict সেটা O(1)-তে দেয়। Deque fit করে কারণ unweighted graph-এ সবচেয়ে কম bus = BFS, আর BFS-এর প্রাণ FIFO queue। visited set দুটো fit করে কারণ একই route দুবার চড়লে layer বাড়ে শুধু, লাভ নেই; আর একই stop দুবার ঘাঁটলে অপ্রয়োজনীয় কাজ — set দিয়ে দুটোই থামাই।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: stop-কে node ধরে graph বানাও — একই route-এর প্রতি জোড়া stop-এর মধ্যে edge। তারপর সেই stop-graph-এ BFS, কিন্তু "কয়টা bus" গুনতে গেলে কোন edge কোন route-এর সেটাও track করতে হবে, যা জটিল আর ভারী।
```text
1) প্রতিটা route-এর সব stop জোড়ায় জোড়ায় edge যোগ করো
2) source stop থেকে BFS
3) bus-পরিবর্তন গুনতে route বদলের হিসাব রাখো (ঝামেলার)
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
stop-কে node ধরলে একটা m-stop route `m^2` edge তৈরি করে; বড় route থাকলে edge-সংখ্যা ভয়ংকর বেড়ে যায়, memory আর সময় দুটোই ফুলে ওঠে। তার উপর "কয়টা bus" গোনা stop-graph-এ অস্বাভাবিক — কারণ একই route-এর ভেতর হাঁটা কোনো bus-পরিবর্তন নয়, কিন্তু stop-edge সেটা আলাদা করে না। মূল অপচয়: ভুল জিনিসকে (stop) node বানানো, যেখানে আসল প্রশ্ন route-পরিবর্তন নিয়ে।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: গোনার একক bus, তাই node হওয়া উচিত route — stop নয়। দুটো route এক ধাপে পৌঁছানো যায় যদি তাদের একটা common stop থাকে। তখন BFS-এর layer-সংখ্যা সরাসরি bus-সংখ্যা গোনে, আর "একই route-এ হাঁটা ফ্রি" ব্যাপারটা আপনাআপনি সামলে যায় (পুরো route এক node)।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
আগে `stop -> routes` map বানাও। BFS শুরু করো source stop-এ ধরা যায় এমন সব route দিয়ে (buses=1)। queue থেকে route বের করো, তার প্রতিটা stop দেখো; কোনো stop target হলে এই buses-ই উত্তর; নাহলে সেই stop থেকে ধরা যায় এমন unvisited route গুলো queue-তে দাও (buses+1)। route আর stop দুটোই visited mark করো, যাতে চক্র না হয়। BFS layer-by-layer ছড়ায়, তাই প্রথম যে layer-এ target মেলে সেটাই সবচেয়ে কম bus।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "stop = node" — এই স্বাভাবিক ধারণাটা ছেড়ে দাও; প্রশ্ন যেহেতু "কয়টা bus", তাই "route = node, common stop = edge" ভাবো। যা গোনা হচ্ছে, সেটাই হওয়া উচিত graph-এর layer — এই এক বদল Hard problem-টাকে সাধারণ BFS বানিয়ে দেয়।
### ছবিতে বোঝা {#7-visual-explanation}
`routes = [[1,2,7],[3,6,7]]`, source 1, target 6। প্রথমে `stop->routes`:
```text
stop_to_routes: 1->[0] 2->[0] 7->[0,1] 3->[1] 6->[1]
BFS (node = route):
source 1 থেকে ধরা যায় route 0 -> queue: (route0, buses=1)
pop route0 (buses=1): stops 1,2,7
stop 7 -> route 1 নতুন -> push (route1, buses=2)
pop route1 (buses=2): stops 3,6,7
stop 6 == target -> return 2
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`routes=[[1,7]], source=1, target=7` (উত্তর 1):
1. `stop_to_routes`: `1->[0]`, `7->[0]`।
2. `source != target`। source 1-এ ধরা যায় route 0 → queue `[(0, 1)]`, `visited_routes={0}`, `visited_stops={1}`।
3. pop `(0, 1)`। route 0-এর stops `[1, 7]`: stop 1 target নয় (আর visited); stop 7 == target → return `1`।
আরেকটা: `source=1, target=6, routes=[[1,2,7],[3,6,7]]`:
1. queue `[(0,1)]`। pop route0 (buses 1): stop 7 → route1 push `(1,2)`। pop route1 (buses 2): stop 6 == target → return `2`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
from collections import defaultdict, deque
def num_buses_to_destination(routes, source, target):
# graph-এর node bus নয়, ROUTE; দুটো route share করলে stop-এ edge
if source == target:
return 0
# stop -> কোন কোন route সেই stop ছোঁয়
stop_to_routes = defaultdict(list)
for i, route in enumerate(routes):
for stop in route:
stop_to_routes[stop].append(i)
# BFS: state = একটা route (পুরো route এক ধাপে চড়া যায়)
queue = deque()
visited_routes = set()
visited_stops = {source}
for r in stop_to_routes[source]: # source থেকে যত route ধরা যায়
queue.append((r, 1)) # (route, এ পর্যন্ত নেওয়া bus সংখ্যা)
visited_routes.add(r)
while queue:
route, buses = queue.popleft()
for stop in routes[route]:
if stop == target:
return buses
if stop not in visited_stops:
visited_stops.add(stop)
for nxt in stop_to_routes[stop]:
if nxt not in visited_routes:
visited_routes.add(nxt)
queue.append((nxt, buses + 1))
return -1
# ---- tests ----
assert num_buses_to_destination([[1, 2, 7], [3, 6, 7]], 1, 6) == 2
assert num_buses_to_destination([[7, 12], [4, 5, 15], [6], [15, 19], [9, 12, 13]], 15, 12) == -1
assert num_buses_to_destination([[1, 2, 7], [3, 6, 7]], 1, 1) == 0
assert num_buses_to_destination([[1, 7]], 1, 7) == 1
assert num_buses_to_destination([[2], [2, 8]], 8, 2) == 1
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `if source == target: return 0` — একই জায়গায় থাকলে কোনো bus লাগে না।
- `stop_to_routes[stop].append(i)` — প্রতিটা stop কোন কোন route ছোঁয়, এই map-ই transfer-graph-এর ভিত্তি।
- `for r in stop_to_routes[source]` — BFS-এর শুরু: source-এ দাঁড়িয়ে যত bus ধরা যায়, সব layer-1।
- `queue.append((r, 1))` — (route, এ পর্যন্ত নেওয়া bus); source-এর route গুলো 1 bus।
- `for stop in routes[route]` — current bus-এর সব stop ঘোরো (পুরো route এক ধাপে যাওয়া যায়)।
- `if stop == target: return buses` — কোনো stop target হলেই এই bus-সংখ্যা সবচেয়ে কম (BFS গ্যারান্টি)।
- `if stop not in visited_stops` ও ভেতরের loop — নতুন stop থেকে যত unvisited route ধরা যায়, সব queue-তে `buses+1` সহ।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`num_buses_to_destination([[1,2,7],[3,6,7]], 1, 6)`: source ≠ target। `stop_to_routes` দেয় `7->[0,1]` ইত্যাদি। source 1-এ route 0 ধরা যায় → queue `[(0,1)]`। route 0 process: stop 7 হয়ে route 1 push `(1,2)`। route 1 process: stop 6 == target → return 2। দ্বিতীয় test-এ source 15 আর target 12-এর route গুলো কোনো common stop দিয়ে যুক্ত হয় না (BFS শেষ হয়) → return -1। বাকি assert pass, শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(সব route-এর মোট stop-সংখ্যা + transfer)** — `stop_to_routes` বানাতে সব stop একবার; BFS-এ প্রতিটা route একবার process আর তার stop গুলো একবার দেখা হয়। প্রতিটা stop থেকে route-list একবারই খোলা হয় (stop visited হয়ে যায়), তাই কাজ মোট stop-সংখ্যার সমানুপাতিক।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(সব route-এর মোট stop-সংখ্যা)** — `stop_to_routes` map-এ প্রতিটা (route, stop) জোড়ার entry; সাথে visited দুটো set আর queue, যা route/stop-সংখ্যায় সীমিত।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- stop-কে node ধরা — `m^2` edge-এ memory/সময় বিস্ফোরণ; route-কে node ধরো।
- `source == target` early check বাদ দেওয়া — তখন 0-এর জায়গায় ভুলভাবে 1 আসে।
- visited *routes* track না করে শুধু visited stops রাখা (বা উল্টো) — একটাই যথেষ্ট নয়; route আবার চড়া আর stop আবার ঘাঁটা — দুটোই থামাতে হয়।
- BFS-এর বদলে DFS — কম-bus-সংখ্যার গ্যারান্টি নষ্ট।
- route push-এর সময় visited mark না করে pop-এর সময় করা — একই route বহুবার queue-তে ঢুকে কাজ ফুলে ওঠে।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: এই repo-র **modeling habit** ("node কী, edge কী") আর তার উপর সাধারণ **BFS** ([../shortest-path.md](../shortest-path.md)-এর unweighted row)। আটকে গেলে আগে নিজেকে জিজ্ঞেস করো "যা গুনছি (bus) সেটা কি graph-এর layer হচ্ছে?" — উত্তর না হলে node-এর সংজ্ঞা বদলাও। তারপর বাকিটা চেনা grid-BFS-এর মতোই।
### পরের অনুশীলন {#22-similar-harder-problems}
- Word Ladder (implicit graph BFS, transform করে node বানানো) —