Problem link ও উৎস
- **Original source:** Classic capstone interview problem (cycle detection / topological sort)
- **Platform:** LeetCode —
- **Topic:** graphs + hashing (adjacency)
- **Difficulty:** Medium
- **Pattern:** Cycle detection via topological sort (Kahn's BFS on indegree)
- **Basic idea inherited from:** এটা একটা cross-topic capstone — এখানে মেশে **09 graphs** (prerequisite-গুলোকে একটা directed graph ধরে, cycle আছে কি না / topological order সম্ভব কি না দেখা) আর **05 hashing** (adjacency list-টা একটা dictionary/`defaultdict` দিয়ে O(1)-এ গড়া ও পড়া)। দুই tool জোড়া লাগলেই এই problem।
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে `numCourses`টা কোর্স (`0` থেকে `numCourses-1`) আর কিছু prerequisite জোড়া দেওয়া। প্রতিটা জোড়া `[a, b]`-র মানে: কোর্স `a` করার **আগে** কোর্স `b` করতেই হবে। প্রশ্ন: এমন কোনো ক্রম আছে কি, যাতে সব কোর্স শেষ করা যায়? (মানে কোনো চক্রাকার নির্ভরতা — "A-র আগে B, B-র আগে A" — নেই তো?) সম্ভব হলে `True`, নাহলে `False`।
```text
numCourses = 2, prerequisites = [[1, 0]]
মানে: 1-এর আগে 0 -> 0 তারপর 1 -> সম্ভব -> True
numCourses = 2, prerequisites = [[1, 0], [0, 1]]
মানে: 1-এর আগে 0, আবার 0-এর আগে 1 -> চক্র! -> False
```
### Input ও output {#8-example-input-and-output}
```text
Input : numCourses=2, prerequisites=[[1,0]] -> Output: True
Input : numCourses=2, prerequisites=[[1,0],[0,1]] -> Output: False (চক্র)
Edge case 1 (কোনো prereq নেই): numCourses=3, [] -> Output: True
Edge case 2 (একটা কোর্স): numCourses=1, [] -> Output: True
Edge case 3 (নিজের উপর নির্ভর): numCourses=1, [[0,0]] -> Output: False
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তুমি জামাকাপড় পরছ — মোজার আগে জুতো পরা যায় না, শার্টের আগে কোট না। তুমি প্রথমে সেই জিনিসগুলো পরো যেগুলোর কোনো "আগে-শর্ত" নেই (অন্তর্বাস, মোজা)। একটা পরে ফেললে যেসব জিনিসের শর্ত পূরণ হলো (এবার জুতো পরা যায়), সেগুলো "তৈরি" তালিকায় ঢোকে। সব পরা শেষ হলে ভালো; কিন্তু যদি "A-র আগে B, B-র আগে A" এমন গিঁট থাকে, তুমি কখনোই শুরু করতে পারবে না — সেটাই cycle।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এই problem দুটো আগের chapter-এর tool জোড়া দেয়:
- **09 graphs** থেকে: prerequisite-গুলোকে একটা **directed graph** ধরা (edge `b -> a` মানে "b শেষ হলে তবে a-র দিকে যাওয়া যায়")। তখন "সব কোর্স করা সম্ভব?" = "graph-এ cycle নেই তো?" = "একটা topological order বের করা যায় কি?"
- **05 hashing** থেকে: graph-টা একটা **adjacency list** (`defaultdict(list)`) দিয়ে রাখা — কোন node থেকে কোথায় edge যায়, তা O(1)-এ পড়া।
একা graph-চিন্তা দেয় cycle/topo framing; একা hashing দেয় adjacency-র দ্রুত গঠন। দুটো মিললে O(V+E)।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: **সব কোর্স করা সম্ভব ঠিক তখনই যখন directed graph-টা acyclic (DAG)।** একটা DAG-এ সবসময় অন্তত একটা node থাকে যার কোনো অসম্পূর্ণ prerequisite নেই (indegree 0); সেটা শেষ করে সরিয়ে দিলে আবার নতুন indegree-0 node বেরোয়। সব node এভাবে সরাতে পারলে cycle নেই; কোনো এক পর্যায়ে আর indegree-0 না পেলে বাকিগুলো একটা cycle-এ আটকা — অসম্ভব।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
- একটা **adjacency list** (`defaultdict(list)`, 05 hashing) — graph-এর edge রাখতে।
- একটা **indegree array** — প্রতিটা node-এর কতগুলো অসম্পূর্ণ prerequisite।
- একটা **queue** (`deque`) — Kahn's BFS-এ indegree-0 node ধরে রাখতে।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Topological sort-এ বারবার দুটো কাজ লাগে: (1) "এই node থেকে কোথায় কোথায় edge যায়" দ্রুত জানা, (2) "এই মুহূর্তে কোন কোন node-এর indegree 0" ধরে রাখা। adjacency list (hashmap) প্রথমটা O(1)-এ দেয়; indegree array + queue দ্বিতীয়টা সহজ করে। এই combination-ই Kahn-এর algorithm-কে O(V+E)-এ চালায়। তাই graph (09) + hashing (05) এখানে নিখুঁত।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা কোর্স থেকে DFS করে দেখি কোনো পথ ঘুরে নিজের কাছে ফিরে আসে কি না (cycle খোঁজা)। প্রতিটা DFS-এ বর্তমান পথের node গুলো একটা "recursion stack"-এ রেখে, আবার সেই node-এ পৌঁছালে cycle।
```text
for প্রতিটা course c:
if dfs(c) cycle পায়:
return False
return True
# dfs: c-কে "চলমান পথে" চিহ্নিত করো, প্রতিবেশীতে যাও;
# চলমান node আবার পেলে cycle; শেষ হলে চিহ্ন তুলে নাও
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
সাবধানে visited/finished চিহ্ন না রাখলে একই subtree বারবার ঘুরে DFS **O(V·(V+E))** বা আরও খারাপ হয়ে যায়। ঠিকভাবে memo করলে DFS-ও O(V+E)-এ নামে — কিন্তু তিন রঙের state (unvisited / in-progress / done) সামলানো bug-প্রবণ। Kahn's BFS (indegree) একই O(V+E) আরও সরল ও কম-ভুলের পথে দেয়, আর বাড়তি হিসেবে একটা valid order-ও দেয়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **প্রশ্নটা আসলে "graph-এ cycle আছে কি?" — আর একটা DAG-এ সবসময় indegree-0 node দিয়ে শুরু করে সব node সরানো যায়।** যদি সব node সরাতে পারি (processed == numCourses), cycle নেই। কোনো পর্যায়ে আর indegree-0 না পেলে, বাকিগুলো cycle-এ আটকা। এই এক চিন্তাই সমাধান।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
Adjacency list (`b -> a`) আর indegree array বানাও। indegree-0 সব node queue-তে দাও (এদের আগে কোনো শর্ত নেই)। queue থেকে এক এক node নাও, "processed" গুনো, আর তার প্রতিবেশীদের indegree কমাও; কারো indegree 0 হলে queue-তে দাও। শেষে যদি processed == numCourses, তাহলে সব করা সম্ভব (`True`), নাহলে cycle (`False`)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "কোন ক্রমে কোর্স করব খুঁজব" ভাবার বদলে ভাবো "শুধু জিজ্ঞেস করি — সব node কি indegree-0 দিয়ে এক এক করে সরানো যায়?" topological-feasibility একটা সহজ indegree-counting-এ গলে যায়; পুরো order বের করারও দরকার নেই, শুধু গুনলেই হয়।
### ছবিতে বোঝা {#7-visual-explanation}
`numCourses=4`, prereqs `[[1,0],[2,0],[3,1],[3,2]]` — Kahn's BFS:
```text
edge (b->a): 0->1, 0->2, 1->3, 2->3
indegree: [0, 1, 1, 2] # node 0-এর কোনো শর্ত নেই
queue=[0] নাও 0; processed=1; 1,2-র indegree-- -> [0,0,0,2]; queue=[1,2]
queue=[1,2] নাও 1; processed=2; 3-র indegree-- -> [_,_,0,1]; queue=[2]
queue=[2] নাও 2; processed=3; 3-র indegree-- -> [_,_,_,0]; queue=[3]
queue=[3] নাও 3; processed=4; queue খালি
processed (4) == numCourses (4) -> cycle নেই -> True
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `numCourses=3`, prereqs `[[1,0],[2,1]]` (edge `0->1`, `1->2`):
1. adjacency: `{0:[1], 1:[2]}`; indegree `[0, 1, 1]`; queue `[0]`; processed 0
2. নাও `0`: processed 1; `1`-র indegree → 0; queue `[1]`
3. নাও `1`: processed 2; `2`-র indegree → 0; queue `[2]`
4. নাও `2`: processed 3; queue খালি
5. processed (3) == numCourses (3) → return `True`
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
from collections import deque, defaultdict
def can_finish(num_courses, prerequisites):
adj = defaultdict(list) # b -> [a, ...]: b শেষ হলে a-রা এক ধাপ এগোয়
indegree = [0] * num_courses
for a, b in prerequisites: # a-র আগে b
adj[b].append(a)
indegree[a] += 1
queue = deque(c for c in range(num_courses) if indegree[c] == 0)
processed = 0
while queue:
node = queue.popleft()
processed += 1 # এই কোর্স "করা গেল"
for nxt in adj[node]:
indegree[nxt] -= 1 # একটা শর্ত পূরণ হলো
if indegree[nxt] == 0:
queue.append(nxt)
return processed == num_courses # সব করা গেলে cycle নেই
# ---- tests ----
assert can_finish(2, [[1, 0]]) is True
assert can_finish(2, [[1, 0], [0, 1]]) is False # সরাসরি চক্র
assert can_finish(3, []) is True # কোনো শর্ত নেই
assert can_finish(1, []) is True # একটা কোর্স
assert can_finish(1, [[0, 0]]) is False # নিজের উপর নির্ভর = চক্র
assert can_finish(4, [[1,0],[2,0],[3,1],[3,2]]) is True
assert can_finish(3, [[0,1],[1,2],[2,0]]) is False # ত্রিভুজ চক্র
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `adj = defaultdict(list)` — adjacency list, নতুন key আপনাআপনি খোলে (05 hashing)।
- `for a, b in prerequisites` — `a`-র আগে `b`, তাই edge `b -> a` যোগ করি আর `a`-র indegree বাড়াই।
- `queue = deque(... indegree[c] == 0)` — যেসব কোর্সের কোনো শর্ত নেই, তারা প্রথমে তৈরি।
- `processed += 1` — queue থেকে নেওয়া মানে এই কোর্স সফলভাবে করা গেল, গুনে রাখি।
- `for nxt in adj[node]` — যাদের এই node শর্ত ছিল, তাদের indegree কমাও।
- `if indegree[nxt] == 0: queue.append(nxt)` — সব শর্ত পূরণ হলে সেই কোর্স এবার তৈরি।
- `return processed == num_courses` — সব কোর্স process হলে DAG (সম্ভব); কম হলে কিছু cycle-এ আটকা (অসম্ভব)।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`numCourses=2, [[1,0]]`-এ indegree `[0,1]`, queue `[0]`; `0` নিয়ে processed 1, `1`-র indegree 0 হয়ে queue-তে; `1` নিয়ে processed 2; 2 == 2 → `True` — assert pass। `[[1,0],[0,1]]`-এ দুটো node-ই indegree 1, queue শুরুতেই খালি, processed 0 ≠ 2 → `False`। ত্রিভুজ চক্র, self-loop, খালি-prereq case-ও সঠিক। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(V + E)** — প্রতিটা node একবার queue-তে ঢোকে-বেরোয় (V), প্রতিটা edge একবার relax হয় (E)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(V + E)** — adjacency list সব edge রাখে (E), indegree array আর queue O(V)।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- edge-এর দিক উল্টে দেওয়া (`a -> b` বনাম `b -> a`) — `[a,b]` মানে "a-র আগে b", তাই edge `b -> a`; উল্টালে cycle-যুক্তি ভেঙে যায়।
- শেষে `processed == num_courses` চেক না করে শুধু queue খালি কি না দেখা — cycle-এ আটকা node গুলো কখনো queue-তে ঢোকেই না, তাই গোনাটাই আসল test।
- self-loop (`[0,0]`) ভুলে যাওয়া — এটা একটা cycle, `False` হওয়া উচিত; indegree-পদ্ধতি এটা আপনাআপনি ধরে।
- disconnected node (কোনো prereq নেই) ভুলে যাওয়া — এদের indegree 0, শুরুতেই queue-তে দিতে হয়।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: directed graph-এ cycle detection / topological sort (09 graphs, [../../09-graphs/topological-sort.md](../../09-graphs/topological-sort.md)) + adjacency list-এর জন্য hashmap (05 hashing, [../../05-hashing/](../../05-hashing/README.md))। সাধারণ graph traversal-ই এখানে indegree-গণনার মোড়কে।
### পরের অনুশীলন {#22-similar-harder-problems}
- Course Schedule II (শুধু সম্ভব কি না না, আসল order ফেরত দাও) —