কনটেন্টে যান

016 — Course Schedule II

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

Problem link ও উৎস

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

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

আগের মতোই numCourses টা কোর্স আর prerequisites জোড়া [a, b] ("a-এর আগে b করতেই হবে")। কিন্তু এবার শুধু "সম্ভব কিনা" নয় — সম্ভব হলে কোর্সগুলো করার একটা valid ক্রম ফেরত দাও (এমন একটা তালিকা যেখানে প্রতিটা কোর্সের আগে তার সব prerequisite আছে)। অসম্ভব হলে (চক্র থাকলে) খালি list []। এটাই topological sort — DAG-এর nodes-কে এমন এক লাইনে সাজানো যাতে প্রতিটা edge সামনের দিকে যায়।

উদাহরণ
prereq [1,0],[2,0],[3,1],[3,2]:
  0 আগে, তারপর 1 ও 2, তারপর 3
valid order: [0,1,2,3] (বা [0,2,1,3]) -> প্রতিটা কোর্সের আগে তার prereq

Input ও output

উদাহরণ
Input : numCourses=4, prerequisites=[[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3]      (বা [0,2,1,3] — দুটোই valid)

Input : numCourses=2, prerequisites=[[1,0]]
Output: [0,1]          (0-এর পরে 1)

Edge case (চক্র): numCourses=2, prerequisites=[[1,0],[0,1]] -> []  (অসম্ভব)

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

একটা বড় প্রকল্পের কাজগুলো সাজানো ভাবো, যেখানে কিছু কাজ অন্য কাজ শেষ না হলে শুরুই করা যায় না। প্রতিটা কাজের গায়ে লিখে রাখো "এর আগে আর কয়টা কাজ বাকি" (indegree)। যাদের গায়ে 0 — সেগুলো এখনই করতে পারো, করে ফেলো। প্রতিটা শেষ করা কাজ যেসব কাজকে আনলক করে, তাদের গায়ের সংখ্যা এক কমাও; নতুন কারো গায়ে 0 হলে সেও এখন করা যায়। সব কাজ এভাবে শেষ হলে তোমার হাতে একটা বৈধ কাজের ক্রম; কিছু কাজ চিরকাল 1-এ আটকে থাকলে বুঝবে বৃত্তাকার নির্ভরতা আছে।

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

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

মূল ভিত হলো #15 Course Schedule (015-course-schedule.md) — সেই একই directed prerequisite graph, সেই একই চক্র-detection — কিন্তু এবার আমরা Kahn's algorithm ব্যবহার করি, যা চক্র ধরার পাশাপাশি আসল order produce করে। ../topological-sort.md-এ এটাই মূল কৌশল: indegree (unmet prerequisites) গোনো, যার indegree 0 তাকে এখনই নাও, তার outgoing edges সরাও, repeat। #15-এ যা ছিল হ্যাঁ/না, এখানে তা একটা সাজানো তালিকা।

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

লুকানো logic: কোনো node-এর indegree = তার দিকে আসা arrow-এর সংখ্যা = বাকি থাকা prerequisite-এর সংখ্যা। যার indegree 0, তাকে আটকানোর কিছু নেই — এখনই করা নিরাপদ। সেটা করলে তার outgoing arrows সরে যায়, যা নতুন কোর্স "মুক্ত" করতে পারে (তাদের indegree 0-তে নামে)। এভাবে layer-by-layer ছাড়াতে থাকো। যদি শেষে সব node বের হয়ে যায় — valid order পেলে; যদি কিছু আটকে থাকে (কেউ কখনো indegree 0-তে পৌঁছায় না) — সেগুলো একটা চক্রে, তাই কোনো order নেই।

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

  • adjacency list — edge b -> a ("b শেষ হলে a unlock"); সাবধান, দিকটা।
  • indegree array — প্রতিটা node-এর বাকি prerequisite সংখ্যা।
  • collections.deque — যেসব node এখন করা যায় (indegree 0), তাদের queue।
  • order list — চূড়ান্ত topological ক্রম।

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

indegree array fit করে কারণ Kahn-এর পুরো logic একটাই গণনার উপর — "এই node-এর কয়টা prerequisite বাকি"; 0-তে নামা মানেই ready। deque (queue) fit করে কারণ ready-হওয়া node-গুলো FIFO-তে process করলেই হয় (order-এর uniqueness দরকার নেই, যেকোনো valid order চলবে), আর popleft/append দুটোই O(1)। adjacency list fit করে কারণ প্রতিটা node process করার সময় তার dependents-এর indegree কমাতে হয় — O(V + E)।

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

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

প্রথম সরল চিন্তা: সব n! permutation ঘুরে দেখা, প্রতিটার জন্য যাচাই করা সেটা সব prerequisite নিয়ম মানে কিনা (প্রতিটা কোর্সের আগে তার সব prereq আছে কিনা)।

উদাহরণ
1) কোর্সগুলোর প্রতিটা সম্ভাব্য সাজানো (permutation) নাও
2) সেই সাজানোয় প্রতিটা prereq [a,b] চেক করো — b কি a-এর আগে?
3) সব prereq মানা প্রথম permutation-ই উত্তর; কোনোটাই না মানলে []

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

n! permutation ঘুরে দেখা factorial — সামান্য বেশি কোর্সেই অসম্ভব (n=15-এই 10^12 পেরোয়)। অথচ order বানাতে এত search লাগে না: যেকোনো মুহূর্তে কোন কোর্স "এখন করা যায়" তা indegree-ই বলে দেয়, কোনো guessing নেই। Kahn প্রতিটা node একবার, প্রতিটা edge একবার ছোঁয় — O(V + E)। permutation-search পুরো অপচয়, কারণ সিদ্ধান্তটা স্থানীয় (indegree 0?), global trial-and-error নয়।

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

মূল observation: indegree 0 মানে "এই কোর্স এখনই করা যায়" — কোনো guess বা backtrack লাগে না। একটা কোর্স করলে তার dependents-এর indegree কমে, যা ক্রমে আরও কোর্স মুক্ত করে। আর শেষে output-এর দৈর্ঘ্য < numCourses হলেই চক্র — এটাই universal চক্র-alarm, আলাদা detection লাগে না।

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

সব indegree গোনো। যাদের indegree 0, তাদের queue-তে দাও। বারবার: queue থেকে একটা node নাও, order-এ যোগ করো; তার প্রতিটা dependent-এর indegree 1 কমাও, কেউ 0-তে নামলে queue-তে দাও। queue খালি হলে থামো। len(order) == numCourses হলে order-ই উত্তর; নাহলে চক্র, ফেরত []। O(V + E)।

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

মোচড়: "কোন ক্রমে সাজাব?" ভেবে সব সাজানো try না করে ভাবো "এই মুহূর্তে কে নির্ভরতা-মুক্ত (indegree 0)? তাকেই নিই, তারপর দেখি কে মুক্ত হলো।" Global ordering-এর প্রশ্নটাকে বারবার একটা স্থানীয় "এখন কে ready" প্রশ্নে ভেঙে দাও — সেটাই Kahn।

ছবিতে বোঝা

numCourses=4, prereq [[1,0],[2,0],[3,1],[3,2]] (edge b->a):

উদাহরণ
   0 ──> 1 ──┐
   │         v
   └──> 2 ──> 3        indegree: 0:0  1:1  2:1  3:2

queue=[0]            order=[]
pop 0 -> order=[0];  1:1->0 (enq), 2:1->0 (enq)   queue=[1,2]
pop 1 -> order=[0,1]; 3:2->1                        queue=[2]
pop 2 -> order=[0,1,2]; 3:1->0 (enq)               queue=[3]
pop 3 -> order=[0,1,2,3]   queue খালি, 4==4 -> valid

ছোট input-এ ধাপে ধাপে

numCourses=3, prereq [[1,0],[2,1]] (0→1→2):

  1. edge 0->1, 1->2। indegree: 0:0, 1:1, 2:1। queue = [0] (শুধু 0-এর indegree 0)। order = []।
  2. pop 0 → order [0]। 0-এর dependent 1: indegree 1->0 → enqueue। queue = [1]।
  3. pop 1 → order [0,1]। 1-এর dependent 2: indegree 1->0 → enqueue। queue = [2]।
  4. pop 2 → order [0,1,2]। 2-এর dependent নেই। queue খালি। len(order)=3 == numCourses → ফেরত [0,1,2]।

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

Python

Python
from collections import deque


def find_order(num_courses, prerequisites):
    adj = [[] for _ in range(num_courses)]
    indeg = [0] * num_courses
    for a, b in prerequisites:           # a করার আগে b -> edge b -> a (b unlock করে a)
        adj[b].append(a)
        indeg[a] += 1

    q = deque(c for c in range(num_courses) if indeg[c] == 0)   # এখন করা যায়
    order = []
    while q:
        c = q.popleft()
        order.append(c)
        for nxt in adj[c]:               # c শেষ -> dependents-এর এক prereq কমল
            indeg[nxt] -= 1
            if indeg[nxt] == 0:          # পুরো মুক্ত
                q.append(nxt)

    return order if len(order) == num_courses else []   # ছোট হলে চক্র


def is_valid_order(num_courses, prerequisites, order):
    # যাচাই: প্রতিটা prereq [a,b]-তে b কি a-এর আগে?
    if len(order) != num_courses:
        return False
    pos = {c: i for i, c in enumerate(order)}
    return all(pos[b] < pos[a] for a, b in prerequisites)


# ---- tests ----
o1 = find_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])
assert is_valid_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]], o1)

o2 = find_order(2, [[1, 0]])
assert o2 == [0, 1]

assert find_order(2, [[1, 0], [0, 1]]) == []          # চক্র -> খালি

o3 = find_order(3, [])                                 # prereq নেই
assert sorted(o3) == [0, 1, 2] and len(o3) == 3

o4 = find_order(3, [[1, 0], [2, 1]])                   # সরল chain
assert o4 == [0, 1, 2]

assert find_order(3, [[0, 1], [1, 2], [2, 0]]) == []  # ত্রিভুজ চক্র
print("সব test pass!")

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

  • adj[b].append(a) + indeg[a] += 1 — prereq [a, b] ("a-এর আগে b") মানে edge b -> a; b শেষ হলে a-এর একটা prereq মেটে।
  • q = deque(... if indeg[c] == 0) — যেসব কোর্স শুরুতেই prerequisite-মুক্ত।
  • order.append(c) — ready node-কে ক্রমে বসাই।
  • indeg[nxt] -= 1 — c শেষ হওয়ায় তার প্রতিটা dependent-এর একটা prereq কমল।
  • if indeg[nxt] == 0: q.append(nxt) — পুরো মুক্ত হলে সেও এখন করা যায়।
  • return order if len(order) == num_courses else [] — সব বের না হলে চক্র, খালি list।

Output মিলিয়ে দেখা

find_order(4, [[1,0],[2,0],[3,1],[3,2]]): indegree গোনে (0:0,1:1,2:1,3:2); 0 দিয়ে শুরু, তারপর 1 ও 2 মুক্ত হয়, শেষে 3 — একটা valid order (যেমন [0,1,2,3])। is_valid_order যাচাই করে প্রতিটা prereq মানা হয়েছে। chain 0->1->2 → [0,1,2]। পরস্পর-নির্ভর [[1,0],[0,1]]-এ কেউ indegree 0-তে পৌঁছায় না → []। ত্রিভুজ চক্র → []। prereq নেই → তিন node যেকোনো order, length 3। সব assert pass, শেষে print: সব test pass!।

JavaScript ও test cases

Kahn JS-এ: indegree গোনো, 0-গুলো queue-তে, একে একে order-এ; valid order একাধিক, তাই helper দিয়ে যাচাই।

JavaScript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// prereq [a,b] মানে "a-এর আগে b" -> edge b -> a (b unlock করে a)
function findOrder(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]++; }
  const queue = [];
  for (let c = 0; c < numCourses; c++) if (indeg[c] === 0) queue.push(c);
  let head = 0;
  const order = [];
  while (head < queue.length) {
    const c = queue[head++];
    order.push(c);
    for (const nxt of adj[c]) if (--indeg[nxt] === 0) queue.push(nxt);
  }
  return order.length === numCourses ? order : [];   // ছোট হলে চক্র
}
// helper: প্রতিটা prereq [a,b]-তে b কি a-এর আগে?
function isValidOrder(numCourses, prerequisites, order) {
  if (order.length !== numCourses) return false;
  const pos = new Map();
  order.forEach((c, i) => pos.set(c, i));
  return prerequisites.every(([a, b]) => pos.get(b) < pos.get(a));
}
// ---- test cases (example + edge) ----
const p1 = [[1, 0], [2, 0], [3, 1], [3, 2]];
assert(isValidOrder(4, p1, findOrder(4, p1)), "diamond-order");
assert(JSON.stringify(findOrder(2, [[1, 0]])) === JSON.stringify([0, 1]), "two");
assert(findOrder(2, [[1, 0], [0, 1]]).length === 0, "cycle -> empty");   // edge
const o3 = findOrder(3, []);
assert(o3.length === 3 && [...o3].sort().join() === "0,1,2", "no-prereq");
assert(JSON.stringify(findOrder(3, [[1, 0], [2, 1]])) === JSON.stringify([0, 1, 2]), "chain");
assert(findOrder(3, [[0, 1], [1, 2], [2, 0]]).length === 0, "triangle-cycle");
console.log("সব JS test pass!");

JS টীকা: Array.from({length: n}, () => []) দিয়ে adjacency বানাও — new Array(n).fill([]) সব index-এ একই array share করিয়ে দেয় (push একটায় = সবার গায়ে)। array সমান কিনা মেলাতে === চলে না (reference তুলনা), তাই JSON.stringify(a) === JSON.stringify(b); valid order একাধিক বলে isValidOrder helper দিয়ে যাচাই, hard-coded একটা order-এর সাথে নয়।

TypeScript ও test cases

TypeScript
function findOrder(numCourses: number, prerequisites: number[][]): number[] {
  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;
  const order: number[] = [];
  while (head < queue.length) {
    const c: number = queue[head++];
    order.push(c);
    for (const nxt of adj[c]) if (--indeg[nxt] === 0) queue.push(nxt);
  }
  return order.length === numCourses ? order : [];
}
function isValidOrder(numCourses: number, prerequisites: number[][], order: number[]): boolean {
  if (order.length !== numCourses) return false;
  const pos = new Map<number, number>();
  order.forEach((c, i) => pos.set(c, i));
  return prerequisites.every(([a, b]) => (pos.get(b) as number) < (pos.get(a) as number));
}
const p1: number[][] = [[1, 0], [2, 0], [3, 1], [3, 2]];
if (!isValidOrder(4, p1, findOrder(4, p1))) throw new Error("FAIL diamond");
if (findOrder(2, [[1, 0], [0, 1]]).length !== 0) throw new Error("FAIL cycle");
console.log("সব TS test pass!");

TS টীকা: return type number[] স্পষ্ট করে দেয় ফাংশন একটা order (বা খালি list) দেয়; Map<number, number> typing position-lookup-কে type-safe রাখে। pos.get number | undefined দেয় বলে compare-এ as number দিয়ে narrow করতে হয় — strict mode-এ এই null-safety-ই TS-এর সুবিধা।

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

সময়

O(V + E) — প্রতিটা node একবার enqueue/dequeue হয়, প্রতিটা edge একবার করে indegree-decrement-এ দেখা হয়। V = numCourses, E = len(prerequisites)।

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

O(V + E) — adjacency list O(V + E), indegree array O(V), queue ও order list worst case O(V)।

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

  • শেষের len(order) == num_courses check ভুলে যাওয়া — চক্র থাকলে নীরবে একটা অসম্পূর্ণ "order" ফেরত যায়।
  • edge দিক উল্টো বসানো — prereq [a, b] মানে b -> a (b unlock করে a)। উল্টো করলে একটা নিখুঁত reverse order বেরোয় — classic নীরব bug।
  • indegree বাড়ানোর সময় ভুল node-এ বাড়ানো (a-এর বদলে b) — শুরুর ready-set ভুল হয়।
  • push করার সময়েই node-কে order-এ যোগ করা — শুধু popleft-এর সময় order-এ দিতে হয়, নাহলে একাধিকবার বা ভুল ক্রমে ঢোকে।

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

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

ভিত্তি: #15 Course Schedule (015-course-schedule.md) আর topological sort theory (../topological-sort.md)। #15-এ শুধু "সম্ভব?" (হ্যাঁ/না) ছিল; এখানে একই directed graph থেকে আসল ক্রম produce করি Kahn দিয়ে — আর Kahn-এর len(order) < numCourses নিজেই চক্র ধরে, তাই detection আর ordering এক algorithm-এই মেলে। মূল নতুন শিক্ষা: "indegree 0 = এখন ready" দিয়ে layer-by-layer ক্রম বানানো, যা পরে DP-on-DAG-এও processing order দেয়। পরের ধাপ: এই Kahn-ই CP scale-এ — #17।

পরের অনুশীলন

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

Topological sort (Kahn): DAG-এর nodes-কে এমন ক্রমে সাজাতে হলে যাতে প্রতিটা edge সামনে যায় — indegree গোনো, indegree-0 node-গুলো queue-তে দাও, একটা করে নিয়ে order-এ বসাও আর dependents-এর indegree কমাও; নতুন 0 হলে enqueue। len(order) < V হলে চক্র (order নেই)। detection + ordering এক pass-এ, O(V + E)।

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

ভবিষ্যতের আমাকে: "Course Schedule II = Kahn topological sort; indegree 0 মানে এখন ready, একটা করে ছাড়ো আর dependents-এর indegree কমাও; order ছোট হলে চক্র, ফেরত []।" যখনই 'dependency মেনে একটা valid ক্রম বের করো' দেখবে — Kahn চালাও, edge দিক সাবধানে বসাও (prereq উল্টো), আর length-check দিয়ে চক্র ধরো।

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

  • Build / compile order: Makefile, Bazel, webpack — কোন module আগে compile/link হবে তার valid order Kahn দিয়ে বের হয়।
  • Task scheduler / CI pipeline: dependent job-গুলো এমন ক্রমে চালানো যাতে প্রতিটা job-এর আগে তার সব নির্ভরতা শেষ।
  • Package installation: apt/npm/pip dependency resolve করে install order ঠিক করা; চক্র থাকলে error।
  • Course/curriculum sequencing: prerequisite মেনে সেমিস্টার-ক্রম সাজানো (এই problem নিজেই)।
  • DP on DAG / data pipeline: node-গুলো topological order-এ process করলে প্রতিটা গণনার আগে তার input তৈরি থাকে (ETL stage ordering)।

মূল pattern: "dependency মেনে একটা valid ক্রম বের করো" = topological sort; len(order) < V হলে চক্র।

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