Problem link ও উৎস
- **Original source:** Classic directed-cycle-detection / prerequisite-feasibility exercise
- **Platform:** LeetCode —
- **Topic:** graphs
- **Difficulty:** Medium
- **Pattern:** cycle detection (directed graph)
- **Basic idea inherited from:** recursion & backtracking ([../../06-recursion-and-backtracking/](../../06-recursion-and-backtracking/README.md)); DFS coloring ([../dfs.md](../dfs.md)); topological sort intro ([../topological-sort.md](../topological-sort.md))
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
`numCourses` টা কোর্স আছে (`0` থেকে `numCourses - 1`)। `prerequisites`-এ জোড়া `[a, b]` মানে "কোর্স `a` করার আগে কোর্স `b` করতেই হবে"। বলো: সব কোর্স কি শেষ করা **সম্ভব**? সম্ভব হলে `True`, নাহলে `False`। আসলে প্রশ্নটা হলো — এই dependency-গুলোর মধ্যে কোনো **চক্র (cycle)** আছে কিনা; চক্র থাকলে কোনোটাই শুরু করা যায় না, তাই অসম্ভব।
```text
0 <- 1 মানে: 1-এর আগে 0 (edge 0 -> 1? না; prereq [1,0]=1 চাই 0)
চক্র থাকলে (A চাই B, B চাই A) -> কোনোটাই করা যায় না -> False
চক্র না থাকলে (DAG) -> একটা valid order আছে -> True
```
### Input ও output {#8-example-input-and-output}
```text
Input : numCourses=2, prerequisites=[[1,0]]
Output: True (1-এর আগে 0; কোনো চক্র নেই)
Input : numCourses=2, prerequisites=[[1,0],[0,1]]
Output: False (0 চাই 1, 1 চাই 0 -> চক্র -> অসম্ভব)
Edge case (কোনো prerequisite নেই): numCourses=3, prerequisites=[] -> True
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তুমি একগুচ্ছ কাজের তালিকা সাজাচ্ছ যেখানে কিছু কাজ অন্য কাজের উপর নির্ভর করে। তুমি একটা কাজ ধরে তার নির্ভরতাগুলো খুঁজতে নামো, সেগুলোর নির্ভরতা, এভাবে গভীরে। যেসব কাজ এখন তোমার "হাতে-নেওয়া, কিন্তু শেষ হয়নি" — সেগুলো GRAY। যদি গভীরে নামতে নামতে এমন কাজে পৌঁছাও যেটা এখনই তোমার হাতে-নেওয়া (GRAY) — তুমি বৃত্তাকার নির্ভরতায় আটকেছ: "এটা শেষ করতে হলে এটাই আগে শেষ লাগে।" তখন তালিকা কখনো সম্পূর্ণ হবে না।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
মূল ভিত হলো **recursion** ([../../06-recursion-and-backtracking/](../../06-recursion-and-backtracking/README.md)) আর **DFS coloring** ([../dfs.md](../dfs.md))। prerequisites একটা directed graph বানায় (edge `a -> b` মানে "a-এর আগে b")। directed graph-এ চক্র খোঁজার আদর্শ উপায় হলো DFS-এর তিন-রঙ (WHITE/GRAY/BLACK) কৌশল — `dfs.md`-এ যেটা পড়েছ। তাই এটা চেনা DFS, কিন্তু একটা node "এখন recursion stack-এ আছে কিনা" track করে।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: **সব কোর্স শেষ করা সম্ভব iff prerequisite graph-এ কোনো directed cycle নেই** (মানে graph একটা DAG)। যদি `A চাই B`, `B চাই C`, `C চাই A` — তিনজনের কেউই কখনো শুরু করতে পারে না, deadlock। directed graph-এ "আগে visit করেছি" দিয়ে চক্র ধরা যায় না (পুরোনো, শেষ-হওয়া অংশে আবার পৌঁছাতে পারো)। তাই তিন state দরকার: GRAY = এখন current path/recursion stack-এ; **একটা GRAY node-এ আবার পৌঁছানো = চক্র** (নিজের অসমাপ্ত পথে ধাক্কা)। BLACK = পুরো explore শেষ, নিরীহ।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
- **adjacency list** — prerequisites থেকে `adj[a] = [b, ...]` (a-এর আগে যেসব লাগে)।
- **color array** — প্রতিটা node-এর state: `WHITE=0`, `GRAY=1`, `BLACK=2`।
- **DFS recursion** — তিন-রঙ চক্র-detection-এর জন্য।
- (বিকল্প) **indegree + `collections.deque`** — Kahn দিয়েও চক্র ধরা যায় (#16-এর মূল কৌশল)।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
তিন-রঙ color array fit করে কারণ directed cycle-detection-এ "এই node কি **এখন** আমার চলমান পথে?" — এই প্রশ্নের উত্তর GRAY/BLACK পার্থক্যই দেয়; শুধু visited (দুই-state) হলে পুরোনো region আর current path গুলিয়ে ভুল cycle ধরা পড়ত। adjacency list fit করে কারণ আমরা প্রতিটা node-এর dependents একবার করে ঘুরি — O(V + E)। DFS fit করে কারণ "current path-এ ফিরে এলাম কিনা" recursion stack-এর স্বাভাবিক ব্যাপার, GRAY ঠিক সেই stack-কেই চিহ্নিত করে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল (ভুল) চিন্তা: directed graph-এ শুধু "visited" set দিয়ে DFS করে চক্র ধরার চেষ্টা — কোনো visited node-এ আবার পৌঁছালেই চক্র ঘোষণা।
```text
1) adjacency list বানাও
2) প্রতিটা node থেকে DFS, একটা visited set রাখো
3) ইতিমধ্যে visited কোনো node-এ পৌঁছালে "চক্র" বলো
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
এটা ধীর নয়, বরং **ভুল**: directed graph-এ একটা already-visited node মানেই চক্র নয় — হতে পারে তুমি শুধু আগে-শেষ-হওয়া কোনো অংশে দুটো ভিন্ন path দিয়ে পৌঁছেছ (যেমন diamond `a->b, a->c, b->d, c->d`; `d`-তে দুবার পৌঁছাই, কিন্তু চক্র নেই)। তাই দুই-state visited false positive দেয়। সমাধান বাড়তি খরচ নয়, বরং সঠিক state সংখ্যা: তিন রঙ। GRAY (current path) আর BLACK (শেষ) আলাদা করলে তবেই সত্যিকারের back-edge ধরা পড়ে। খরচ সেই O(V + E)-ই, শুধু logic সঠিক হয়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **directed graph-এ চক্র = DFS করতে করতে একটা GRAY (এখনো recursion stack-এ থাকা) node-এ ফিরে আসা।** "visited" যথেষ্ট নয়; "এই মুহূর্তে আমার চলমান পথে আছে কিনা" — সেটাই চক্রের আসল সংকেত। GRAY থেকে BLACK-এ যাওয়ার মুহূর্তটাই বলে "এই node ও তার নিচের সব নিরাপদ"।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
`color` সব WHITE-এ শুরু। প্রতিটা node থেকে (এখনো WHITE হলে) DFS: ঢোকার সময় GRAY করো; প্রতিটা প্রতিবেশীর জন্য — GRAY হলে চক্র (return চক্র-পাওয়া-গেছে); WHITE হলে recurse, চক্র পেলে উপরে propagate; শেষে node-কে BLACK করো। কোনো DFS-এ চক্র পেলে `False`; সব শেষ হলে `True`। O(V + E)। (বিকল্প: Kahn-এ indegree 0 ছাড়াতে ছাড়াতে যদি সব node বের না হয়, চক্র আছে — #16-এ বিস্তারিত।)
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "সব কোর্স শেষ করা যায় কিনা?" — এই scheduling প্রশ্নটাকে অনুবাদ করো "prerequisite graph-এ directed চক্র আছে কিনা?"-তে। আর চক্র খুঁজতে "visited" নয়, "এখন recursion stack-এ আছে কিনা" (GRAY) দেখো। বাস্তব প্রশ্ন → graph property → সঠিক DFS state — এই তিন ধাপের অনুবাদই এখানে আসল দক্ষতা।
### ছবিতে বোঝা {#7-visual-explanation}
`numCourses=4`, prerequisites `[[1,0],[2,1],[3,2],[1,3]]` দিয়ে (edge a->b মানে a চাই b):
```text
edges: 1->0, 2->1, 3->2, 1->3
0 <- 1 <- 2
^ |
| v
+--- 3 (1->3, 3->2, 2->1 একটা চক্র!)
DFS from 1: 1 GRAY -> 0 (BLACK, leaf) -> ফিরে -> 3 GRAY -> 2 GRAY
-> 2 চাই 1, কিন্তু 1 এখনো GRAY (recursion stack-এ) -> CYCLE -> False
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`numCourses=2`, prerequisites `[[1,0],[0,1]]` (0 চাই 1, 1 চাই 0):
1. `adj`: edge `1->0` (prereq [1,0]) আর `0->1` (prereq [0,1])। `color = [WHITE, WHITE]`।
2. node 0 WHITE → `dfs(0)`: `color[0]=GRAY`। 0-এর প্রতিবেশী `1` WHITE → `dfs(1)`: `color[1]=GRAY`।
3. 1-এর প্রতিবেশী `0` — `color[0]==GRAY`! → চক্র পাওয়া গেল, `dfs(1)` returns "cycle"।
4. উপরে propagate → `dfs(0)` "cycle" → মূল ফল `False`। (0 ও 1 পরস্পরের prerequisite, deadlock।)
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
from collections import deque
def can_finish_dfs(num_courses, prerequisites):
adj = [[] for _ in range(num_courses)]
for a, b in prerequisites: # a করার আগে b -> edge a -> b
adj[a].append(b)
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * num_courses
def has_cycle(u):
color[u] = GRAY # ঢুকছি: এখন recursion stack-এ
for v in adj[u]:
if color[v] == GRAY: # নিজের চলমান পথে ফিরে এলাম -> চক্র
return True
if color[v] == WHITE and has_cycle(v):
return True
color[u] = BLACK # বেরোচ্ছি: পুরো explore শেষ, নিরাপদ
return False
for node in range(num_courses):
if color[node] == WHITE and has_cycle(node):
return False # চক্র মানেই অসম্ভব
return True
def can_finish_kahn(num_courses, prerequisites):
# বিকল্প: indegree 0 ছাড়াতে ছাড়াতে সব বের হলে চক্র নেই (#16-এর কৌশল)
adj = [[] for _ in range(num_courses)]
indeg = [0] * num_courses
for a, b in prerequisites:
adj[b].append(a) # b শেষ হলে a unlock
indeg[a] += 1
q = deque(c for c in range(num_courses) if indeg[c] == 0)
done = 0
while q:
c = q.popleft()
done += 1
for nxt in adj[c]:
indeg[nxt] -= 1
if indeg[nxt] == 0:
q.append(nxt)
return done == num_courses # সব বের হলে DAG, নাহলে চক্র
# ---- tests ----
for can_finish in (can_finish_dfs, can_finish_kahn):
assert can_finish(2, [[1, 0]]) is True
assert can_finish(2, [[1, 0], [0, 1]]) is False
assert can_finish(3, []) is True # prereq নেই
assert can_finish(4, [[1, 0], [2, 1], [3, 2]]) is True # সরল chain (DAG)
assert can_finish(3, [[0, 1], [1, 2], [2, 0]]) is False # ত্রিভুজ চক্র
assert can_finish(4, [[1, 0], [2, 0], [3, 1], [3, 2]]) is True # diamond, চক্র নেই
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `adj[a].append(b)` — prereq `[a, b]` মানে edge `a -> b` ("a-এর আগে b")।
- `color = [WHITE] * num_courses` — প্রতিটা node শুরুতে অস্পর্শিত।
- `color[u] = GRAY` — node-এ ঢুকছি, এখন recursion stack-এ; এটাই current-path marker।
- `if color[v] == GRAY: return True` — GRAY প্রতিবেশী = back-edge = চক্র।
- `color[u] = BLACK` — সব dependent শেষ, node চিরতরে নিরাপদ।
- Kahn version-এ `adj[b].append(a)` + `indeg[a] += 1` — edge দিক উল্টো (b unlock করে a), আর `done == num_courses` দিয়ে চক্র-চেক।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
দুই approach-এই: `[[1,0]]` সরল prereq, চক্র নেই → `True`। `[[1,0],[0,1]]` পরস্পর-নির্ভর → DFS-এ GRAY node-এ ফিরে আসে / Kahn-এ কেউ indegree 0-তে পৌঁছায় না → `False`। খালি prereq → `True`। chain (DAG) → `True`। ত্রিভুজ `0->1->2->0` → চক্র → `False`। diamond-এ `3`-তে দুই path-এ পৌঁছালেও চক্র নেই (দুই-state visited হলে এখানেই ভুল হতো) → `True`। সব assert pass, শেষে print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
দুই approach JS-এ: তিন-রঙ DFS (WHITE/GRAY/BLACK) আর Kahn (indegree); দুটোই directed চক্র ধরে।
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// edges: prereq [a,b] মানে "a-এর আগে b" -> edge a -> b
function canFinishDFS(numCourses, prerequisites) {
// adjacency list: প্রতিটা node-এর জন্য আলাদা array (shared-ref bug এড়িয়ে)
const adj = Array.from({ length: numCourses }, () => []);
for (const [a, b] of prerequisites) adj[a].push(b);
const WHITE = 0, GRAY = 1, BLACK = 2;
const color = new Array(numCourses).fill(WHITE);
const hasCycle = (u) => {
color[u] = GRAY; // এখন recursion stack-এ
for (const v of adj[u]) {
if (color[v] === GRAY) return true; // current path-এ ফিরলাম -> চক্র
if (color[v] === WHITE && hasCycle(v)) return true;
}
color[u] = BLACK; // explore শেষ, নিরাপদ
return false;
};
for (let i = 0; i < numCourses; i++) {
if (color[i] === WHITE && hasCycle(i)) return false;
}
return true;
}
function canFinishKahn(numCourses, prerequisites) {
const adj = Array.from({ length: numCourses }, () => []);
const indeg = new Array(numCourses).fill(0);
for (const [a, b] of prerequisites) { adj[b].push(a); indeg[a]++; } // b unlock করে a
const queue = [];
for (let c = 0; c < numCourses; c++) if (indeg[c] === 0) queue.push(c);
let head = 0, done = 0;
while (head < queue.length) {
const c = queue[head++];
done++;
for (const nxt of adj[c]) if (--indeg[nxt] === 0) queue.push(nxt);
}
return done === numCourses; // সব বের হলে DAG
}
// ---- test cases (example + edge) ----
for (const canFinish of [canFinishDFS, canFinishKahn]) {
assert(canFinish(2, [[1, 0]]) === true, "simple");
assert(canFinish(2, [[1, 0], [0, 1]]) === false, "mutual-cycle");
assert(canFinish(3, []) === true, "no-prereq"); // edge
assert(canFinish(4, [[1, 0], [2, 1], [3, 2]]) === true, "chain");
assert(canFinish(3, [[0, 1], [1, 2], [2, 0]]) === false, "triangle");
assert(canFinish(4, [[1, 0], [2, 0], [3, 1], [3, 2]]) === true, "diamond");
}
console.log("সব JS test pass!");
```
> **JS টীকা:** adjacency list বানাতে `Array.from({length: n}, () => [])` ব্যবহার করো — `new Array(n).fill([])` দিলে **সব index একই array reference** পায়, এক node-এ push করলে সবার গায়ে দেখা যায় (নীরব ভয়ংকর bug)। প্রতিটা `() => []` call নতুন array দেয়। `for...of` দিয়ে `[a, b]` destructure করায় edge unpack পরিষ্কার।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
function canFinish(numCourses: number, prerequisites: number[][]): boolean {
const adj: number[][] = Array.from({ length: numCourses }, () => []);
const indeg: number[] = new Array(numCourses).fill(0);
for (const [a, b] of prerequisites) { adj[b].push(a); indeg[a]++; }
const queue: number[] = [];
for (let c = 0; c < numCourses; c++) if (indeg[c] === 0) queue.push(c);
let head = 0, done = 0;
while (head < queue.length) {
const c: number = queue[head++];
done++;
for (const nxt of adj[c]) if (--indeg[nxt] === 0) queue.push(nxt);
}
return done === numCourses;
}
function expect