কনটেন্টে যান

015 — Course Schedule

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

numCourses টা কোর্স আছে (0 থেকে numCourses - 1)। prerequisites-এ জোড়া [a, b] মানে "কোর্স a করার আগে কোর্স b করতেই হবে"। বলো: সব কোর্স কি শেষ করা সম্ভব? সম্ভব হলে True, নাহলে False। আসলে প্রশ্নটা হলো — এই dependency-গুলোর মধ্যে কোনো চক্র (cycle) আছে কিনা; চক্র থাকলে কোনোটাই শুরু করা যায় না, তাই অসম্ভব।

উদাহরণ
0 <- 1   মানে: 1-এর আগে 0 (edge 0 -> 1? না; prereq [1,0]=1 চাই 0)
চক্র থাকলে (A চাই B, B চাই A) -> কোনোটাই করা যায় না -> False
চক্র না থাকলে (DAG) -> একটা valid order আছে -> True

Input ও output

উদাহরণ
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

চেনা উদাহরণে বোঝা

ভাবো তুমি একগুচ্ছ কাজের তালিকা সাজাচ্ছ যেখানে কিছু কাজ অন্য কাজের উপর নির্ভর করে। তুমি একটা কাজ ধরে তার নির্ভরতাগুলো খুঁজতে নামো, সেগুলোর নির্ভরতা, এভাবে গভীরে। যেসব কাজ এখন তোমার "হাতে-নেওয়া, কিন্তু শেষ হয়নি" — সেগুলো GRAY। যদি গভীরে নামতে নামতে এমন কাজে পৌঁছাও যেটা এখনই তোমার হাতে-নেওয়া (GRAY) — তুমি বৃত্তাকার নির্ভরতায় আটকেছ: "এটা শেষ করতে হলে এটাই আগে শেষ লাগে।" তখন তালিকা কখনো সম্পূর্ণ হবে না।

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

মূল ভিত হলো recursion (../../06-recursion-and-backtracking/) আর DFS coloring (../dfs.md)। prerequisites একটা directed graph বানায় (edge a -> b মানে "a-এর আগে b")। directed graph-এ চক্র খোঁজার আদর্শ উপায় হলো DFS-এর তিন-রঙ (WHITE/GRAY/BLACK) কৌশল — dfs.md-এ যেটা পড়েছ। তাই এটা চেনা DFS, কিন্তু একটা node "এখন recursion stack-এ আছে কিনা" track করে।

ভেতরের যুক্তি

লুকানো 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 শেষ, নিরীহ।

কী দিয়ে তথ্য রাখব

  • 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-এর মূল কৌশল)।

এটি কেন উপযুক্ত

তিন-রঙ 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-কেই চিহ্নিত করে।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

প্রথম সরল (ভুল) চিন্তা: directed graph-এ শুধু "visited" set দিয়ে DFS করে চক্র ধরার চেষ্টা — কোনো visited node-এ আবার পৌঁছালেই চক্র ঘোষণা।

উদাহরণ
1) adjacency list বানাও
2) প্রতিটা node থেকে DFS, একটা visited set রাখো
3) ইতিমধ্যে visited কোনো node-এ পৌঁছালে "চক্র" বলো

কোথায় বেশি কাজ হচ্ছে

এটা ধীর নয়, বরং ভুল: 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 সঠিক হয়।

যে বিষয়টি খেয়াল করতে হবে

মূল observation: directed graph-এ চক্র = DFS করতে করতে একটা GRAY (এখনো recursion stack-এ থাকা) node-এ ফিরে আসা। "visited" যথেষ্ট নয়; "এই মুহূর্তে আমার চলমান পথে আছে কিনা" — সেটাই চক্রের আসল সংকেত। GRAY থেকে BLACK-এ যাওয়ার মুহূর্তটাই বলে "এই node ও তার নিচের সব নিরাপদ"।

আরও কম কাজে সমাধান

color সব WHITE-এ শুরু। প্রতিটা node থেকে (এখনো WHITE হলে) DFS: ঢোকার সময় GRAY করো; প্রতিটা প্রতিবেশীর জন্য — GRAY হলে চক্র (return চক্র-পাওয়া-গেছে); WHITE হলে recurse, চক্র পেলে উপরে propagate; শেষে node-কে BLACK করো। কোনো DFS-এ চক্র পেলে False; সব শেষ হলে True। O(V + E)। (বিকল্প: Kahn-এ indegree 0 ছাড়াতে ছাড়াতে যদি সব node বের না হয়, চক্র আছে — #16-এ বিস্তারিত।)

ভাবনার পরিবর্তন

মোচড়: "সব কোর্স শেষ করা যায় কিনা?" — এই scheduling প্রশ্নটাকে অনুবাদ করো "prerequisite graph-এ directed চক্র আছে কিনা?"-তে। আর চক্র খুঁজতে "visited" নয়, "এখন recursion stack-এ আছে কিনা" (GRAY) দেখো। বাস্তব প্রশ্ন → graph property → সঠিক DFS state — এই তিন ধাপের অনুবাদই এখানে আসল দক্ষতা।

ছবিতে বোঝা

numCourses=4, prerequisites [[1,0],[2,1],[3,2],[1,3]] দিয়ে (edge a->b মানে a চাই b):

উদাহরণ
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-এ ধাপে ধাপে

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।)

কোড ও ব্যাখ্যা

Python

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!")

কোডের প্রতিটি অংশ

  • 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 মিলিয়ে দেখা

দুই 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

দুই 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

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<T>(actual: T, exp: T, msg = ""): void {
  if (actual !== exp) throw new Error(`FAIL ${msg}: got ${actual}`);
}
expect(canFinish(2, [[1, 0]]), true, "simple");
expect(canFinish(2, [[1, 0], [0, 1]]), false, "mutual-cycle");
expect(canFinish(3, []), true, "no-prereq");
expect(canFinish(3, [[0, 1], [1, 2], [2, 0]]), false, "triangle");
console.log("সব TS test pass!");

TS টীকা: prerequisites: number[][] declare করায় প্রতিটা edge যে ঠিক দুই-সংখ্যার জোড়া, তা type-এ পরিষ্কার; adj: number[][] typing-এ adjacency list-এর আকৃতি locked, ভুল করে string push করলে compile-error।

খরচ ও সাধারণ ভুল

সময়

O(V + E) — V = numCourses, E = len(prerequisites)। প্রতিটা node একবার রঙ পায়, প্রতিটা edge একবার দেখা হয় (DFS বা Kahn উভয়ে)।

অতিরিক্ত জায়গা

O(V + E) — adjacency list O(V + E), color/indegree array O(V), DFS recursion stack বা Kahn queue worst case O(V)।

যে ভুলগুলো এড়াতে হবে

  • দুই-state "visited" দিয়ে directed চক্র ধরার চেষ্টা — diamond-এর মতো reconvergent path-এ false positive; তিন রঙ লাগবে।
  • edge দিক উল্টো বসানো — prereq [a, b] মানে a -> b; DFS-এ এটাই চাই, Kahn-এ ইচ্ছাকৃতভাবে উল্টো (b -> a)। দিক গুলিয়ে ফেললে নীরব ভুল।
  • BLACK node-এ পৌঁছানোকে চক্র ভাবা — BLACK নিরীহ, সে সম্পূর্ণ explored; শুধু GRAY-ই চক্র।
  • disconnected/multi-component graph-এ প্রতিটা node থেকে শুরুর বাইরের loop ভুলে যাওয়া — কিছু component-এর চক্র miss হয়।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

ভিত্তি: recursion (../../06-recursion-and-backtracking/) আর DFS coloring (../dfs.md)। এটা প্রথম problem যেখানে একটা বাস্তব scheduling প্রশ্নকে graph property-তে অনুবাদ করতে হয় ("সব শেষ করা যায়?" = "directed চক্র নেই?"), আর directed চক্র ধরতে তিন-রঙ DFS শিখতে হয় — দুই-state visited যেখানে যথেষ্ট নয়। মূল নতুন শিক্ষা: GRAY = current path, যা পরে topological sort, strongly-connected-components, সবেতেই ভিত্তি। পরের ধাপ: শুধু "সম্ভব?" নয়, আসল ordering produce করা — Kahn দিয়ে #16।

পরের অনুশীলন

কৌশলটি মনে রাখুন

Directed cycle detection: "এই dependency/constraint গুলো একসাথে সম্ভব কিনা" = directed graph-এ চক্র আছে কিনা। DFS-এ তিন রঙ ব্যবহার করো — GRAY (এখন recursion stack-এ) node-এ ফিরে আসা মানেই চক্র; BLACK নিরীহ। বিকল্পে Kahn: indegree 0 ছাড়াতে ছাড়াতে সব node বের না হলে চক্র আছে। খরচ O(V + E)।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "Course Schedule = directed চক্র-detection; 'সব কোর্স শেষ?' মানে 'graph কি DAG?'; DFS-এ GRAY node-এ ফিরলেই চক্র, নাহলে True।" যখনই 'এই dependency/constraint গুলো একসাথে পূরণযোগ্য কিনা' দেখবে — directed graph বানাও আর তিন-রঙ DFS (বা Kahn) দিয়ে চক্র খোঁজো; দুই-state visited-এ ভরসা কোরো না।

কোথায় কাজে লাগে

  • Build systems / package managers: source file বা package-এর dependency graph-এ চক্র মানে build অসম্ভব (circular dependency); cycle-detection সেটা আগে ধরে।
  • Task / job scheduling: কাজগুলোর "X-এর আগে Y" নির্ভরতা একসাথে পূরণযোগ্য কিনা — চক্র থাকলে deadlock, কোনো order নেই।
  • Spreadsheet / formula engine: cell A = B+1, B = A+1 ধরনের circular reference detect করা — directed cycle-check।
  • Course / curriculum planning: prerequisite মেনে সব কোর্স শেষ করা সম্ভব কিনা (literally এই problem)।
  • Deadlock detection in OS/DB: resource allocation graph-এ চক্র = deadlock; একই তিন-রঙ DFS।

মূল pattern: "এই dependency/constraint গুলো একসাথে সম্ভব কিনা" = directed graph-এ চক্র আছে কিনা; তিন-রঙ DFS বা Kahn।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।