কনটেন্টে যান

017 — Course Schedule (CSES)

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

Problem link ও উৎস

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

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

n টা course আছে আর m টা প্রয়োজন (requirement)। প্রতিটা requirement (a, b) মানে "course a শেষ করার আগে course b শেষ করতে হবে" — মানে একটা directed edge a -> b। তোমাকে এমন একটা ক্রমে সব course সাজাতে হবে যাতে প্রতিটা requirement মানা হয় (যা আগে লাগে তা আগে আসে)। সম্ভব হলে যেকোনো একটা valid ক্রম ছাপাও; অসম্ভব হলে IMPOSSIBLE। এটাই topological sort, এবার CP scale-এ (n, m 10^5 অবধি)।

উদাহরণ
n=4, requirements: (1,2),(2,3),(1,4)
edge: 1->2, 2->3, 1->4
valid orders: 1 2 4 3 এবং 1 2 3 4
দুটিতেই প্রতিটি prerequisite তার dependent course-এর আগে আছে।

Input ও output

উদাহরণ
Input : n=4, requirements=[(1,2),(2,3),(1,4)]
Output: [1,2,4,3]      (বা অন্য valid order; প্রতিটা course-এর আগে তার prereq)

Input : n=2, requirements=[(1,2)]
Output: [1,2]          (1-এর পরে 2)

Edge case (চক্র): n=2, requirements=[(1,2),(2,1)] -> IMPOSSIBLE

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

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

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

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

মূল ভিত হলো #16 Course Schedule II (016-course-schedule-ii.md) — হুবহু Kahn's algorithm: indegree গোনো, indegree-0 node ছাড়ো, dependents-এর indegree কমাও, repeat (../topological-sort.md)। নতুন কিছু নেই algorithm-এ; শুধু input বড় (CP scale, 1-indexed courses), recursion নয় বরং deque ব্যবহার নিরাপদ, আর output হয় একটা সম্পূর্ণ valid ক্রম নয়তো IMPOSSIBLE।

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

লুকানো logic একই: কোনো course-এর indegree = তার আগে যত course লাগে তার সংখ্যা। indegree 0 মানে কিছুই আটকাচ্ছে না — এখনই করা যায়। সেটা করলে তার outgoing edges সরে, dependents-এর indegree কমে, নতুন course মুক্ত হয়। valid topological order exist করে iff graph-এ কোনো directed cycle নেই (DAG)। যদি Kahn শেষে সব n course বের করতে পারে — order পেলে; না পারলে কিছু course একটা চক্রে আটকে — IMPOSSIBLE।

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

  • adjacency list — n বড়, তাই adj[a] = [b, ...] (requirement (a,b) → edge a -> b)।
  • indegree array — প্রতিটা course-এর বাকি prerequisite সংখ্যা।
  • collections.deque — ready (indegree 0) course-গুলোর queue; CP depth-এ recursion এড়াতে।
  • order list — চূড়ান্ত ক্রম।

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

adjacency list fit করে কারণ CP-তে n, m বড়, matrix হলে O(n^2) memory ফাটে; list-এ O(V + E) traversal হয়। indegree array fit করে কারণ Kahn-এর পুরো সিদ্ধান্ত একটাই গণনায় — "কয়টা prereq বাকি", 0 হলেই ready। deque fit করে কারণ ready course-গুলো FIFO-তে process করলেই যেকোনো valid order মেলে, আর popleft/append O(1); সবচেয়ে গুরুত্বপূর্ণ, deque-ভিত্তিক Kahn-এ recursion-ই নেই, তাই CP-scale depth-এ stack overflow হয় না (DFS topo-sort-এর সম্ভাব্য সমস্যা)।

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

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

প্রথম সরল চিন্তা: course-গুলোর সব n! permutation ঘুরে দেখা, প্রতিটার জন্য যাচাই করা সব requirement মানা হচ্ছে কিনা।

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

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

n! permutation factorial — CP-scale-এ n 10^5, এটা চিন্তারও বাইরে; এমনকি n=15-এও অসম্ভব। Kahn প্রতিটা node ও edge একবার ছোঁয় — O(V + E), 10^5 node/edge-এ অনায়াসে time limit-এর ভেতর। permutation-search পুরো অপচয়, কারণ "এখন কে ready" সিদ্ধান্তটা indegree থেকেই স্থানীয়ভাবে পাওয়া যায়, কোনো global trial-and-error লাগে না।

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

মূল observation: indegree 0 = "এই course এখনই করা যায়", কোনো guess নয়। একটা course করলে dependents-এর indegree কমে, ক্রমে আরও মুক্ত হয়। আর শেষে বের-হওয়া course সংখ্যা < n হলেই চক্র → IMPOSSIBLE। CP-তে বাড়তি observation: এই পুরোটা recursion-হীন (deque), তাই বিশাল depth-এও নিরাপদ।

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

সব indegree গোনো; indegree-0 course-গুলো deque-তে দাও। বারবার: একটা নাও, order-এ যোগ করো; তার dependents-এর indegree 1 কমাও, কেউ 0-তে নামলে enqueue। deque খালি হলে থামো। len(order) == n হলে order-ই উত্তর; নাহলে চক্র, IMPOSSIBLE। সম্পূর্ণ iterative, O(V + E)।

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

মোচড়: "কোন ক্রমে সাজাব?" — সব permutation try না করে ভাবো "এখন কে নির্ভরতা-মুক্ত (indegree 0)? তাকেই নিই, তারপর দেখি কে মুক্ত হলো।" CP-তে এক ধাপ যোগ: recursion নয়, deque — depth 10^5 হলেও stack নিরাপদ। Global ordering → বারবার স্থানীয় "এখন কে ready" + iterative loop।

ছবিতে বোঝা

n=4, requirements (1,2),(2,3),(1,4) (edge a->b):

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

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

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

n=3, requirements (1,2),(1,3) (1 আগে, তারপর 2 ও 3):

  1. edge 1->2, 1->3। indegree: 1:0, 2:1, 3:1। deque = [1]। order = []।
  2. pop 1 → order [1]। dependents 2 (indeg 1->0, enq), 3 (indeg 1->0, enq)। deque = [2,3]।
  3. pop 2 → order [1,2]। 2-এর dependent নেই। deque = [3]।
  4. pop 3 → order [1,2,3]। deque খালি। len(order)=3 == n → ফেরত [1,2,3]।

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

Python

Python
from collections import deque


def course_schedule(n, requirements):
    # 1-indexed courses; requirement (a, b) -> edge a -> b (a-এর আগে b... )
    # CSES: (a, b) মানে a শেষ করার আগে b; তাই b আগে আসবে, edge b -> a ধরি
    adj = [[] for _ in range(n + 1)]
    indeg = [0] * (n + 1)
    for a, b in requirements:
        adj[b].append(a)             # b শেষ হলে a unlock (b আগে আসে)
        indeg[a] += 1

    q = deque(c for c in range(1, n + 1) 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) == n else None   # ছোট হলে চক্র


def format_answer(n, requirements):
    res = course_schedule(n, requirements)
    return "IMPOSSIBLE" if res is None else res


def is_valid(n, requirements, order):
    # যাচাই: প্রতিটা requirement (a,b)-তে b কি a-এর আগে? (b আগে লাগে)
    if order is None or len(order) != n:
        return False
    pos = {c: i for i, c in enumerate(order)}
    return all(pos[b] < pos[a] for a, b in requirements)


# ---- tests ----
reqs = [(1, 2), (2, 3), (1, 4)]
o1 = course_schedule(4, reqs)
assert is_valid(4, reqs, o1)

assert course_schedule(2, [(1, 2)]) == [2, 1]         # 2 আগে, তারপর 1
assert format_answer(2, [(1, 2), (2, 1)]) == "IMPOSSIBLE"  # চক্র

o3 = course_schedule(3, [])                            # requirement নেই
assert sorted(o3) == [1, 2, 3] and len(o3) == 3

assert format_answer(3, [(1, 2), (2, 3), (3, 1)]) == "IMPOSSIBLE"  # ত্রিভুজ চক্র

# CP-scale sanity: লম্বা chain, recursion ছাড়াই চলে
chain = [(i, i + 1) for i in range(1, 1000)]           # 1 আগে 2... edge i+1->i
big = course_schedule(1000, chain)
assert is_valid(1000, chain, big)
print("সব test pass!")

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

  • adj[b].append(a) + indeg[a] += 1 — requirement (a, b) মানে "a-এর আগে b"; তাই b আগে আসে, edge b -> a, আর a-এর indegree বাড়ে।
  • q = deque(... if indeg[c] == 0) — শুরুতে যেসব course প্রয়োজন-মুক্ত (1-indexed)।
  • order.append(c) — ready course-কে ক্রমে বসাই।
  • indeg[nxt] -= 1 — c শেষ হওয়ায় dependents-এর একটা প্রয়োজন মিটল।
  • if indeg[nxt] == 0: q.append(nxt) — পুরো মুক্ত হলে enqueue।
  • return order if len(order) == n else None — সব বের না হলে চক্র (None → IMPOSSIBLE)।

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

course_schedule(4, [(1,2),(2,3),(1,4)]): edge দিক (b→a) বসিয়ে indegree গোনে, ready-গুলো ছাড়াতে ছাড়াতে একটা valid order বানায়; is_valid প্রতিটা requirement মানা যাচাই করে। (1,2)-তে 2 আগে লাগে, তাই [2,1]। পরস্পর-নির্ভর (1,2),(2,1) → কেউ indegree 0-তে পৌঁছায় না → IMPOSSIBLE। ত্রিভুজ চক্র → IMPOSSIBLE। requirement নেই → তিন course যেকোনো order। 1000-লম্বা chain recursion ছাড়াই (deque) সমাধান হয় — CP-scale sanity। সব assert pass, শেষে print: সব test pass!।

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

সময়

O(V + E) — V = n, E = m। প্রতিটা course একবার enqueue/dequeue, প্রতিটা requirement একবার indegree-decrement-এ দেখা হয়। CP-scale 10^5-এ আরামদায়ক।

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

O(V + E) — adjacency list O(V + E), indegree array O(V), deque ও order list worst case O(V)। এটাই CP-scale-এর সঠিক বাজেট।

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

  • CP-scale-এ recursive DFS topo-sort চালিয়ে stack overflow করা — deque-ভিত্তিক Kahn নিরাপদ পছন্দ।
  • শেষের len(order) == n check ভুলে যাওয়া — চক্রের ক্ষেত্রে নীরবে অসম্পূর্ণ order ফেরত।
  • edge দিক উল্টো বসানো — (a, b) "a-এর আগে b" মানে b -> a; উল্টো করলে নিখুঁত reverse order বেরোয় (নীরব bug)।
  • 1-indexed courses-এ array size n দেওয়া (n + 1 দরকার) বা loop range(n) করা — off-by-one।

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

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

ভিত্তি: #16 Course Schedule II (016-course-schedule-ii.md) আর topological sort theory (../topological-sort.md)। হুবহু একই Kahn algorithm, কিন্তু দুটো CP-নির্দিষ্ট জোর: (১) scale বড়, তাই adjacency list + deque, recursion এড়িয়ে; (২) 1-indexed I/O আর IMPOSSIBLE-ফরম্যাট। মূল শিক্ষা একই — indegree 0 = ready, length-check = চক্র-alarm — কিন্তু এখানে শিখি কীভাবে এটা বড় input-এ নিরাপদে ও দ্রুত চালাতে হয়। পরের ধাপ: weighted graph-এ shortest path — Dijkstra, #18।

পরের অনুশীলন

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

Topological sort (CP scale, Kahn): বড় DAG-এ valid ক্রম বানাতে — indegree গোনো, 0-গুলো deque-তে দাও, একটা করে ছাড়ো আর dependents-এর indegree কমাও; len(order) < n হলে চক্র (IMPOSSIBLE)। সবসময় iterative (deque) রাখো — recursion CP depth-এ overflow করে — আর 1-indexing ও edge-দিক সাবধানে সামলাও।

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

ভবিষ্যতের আমাকে: "CSES Course Schedule = Kahn topo sort, CP scale; deque দিয়ে iterative, indegree 0 ছাড়ো, dependents কমাও; order ছোট হলে IMPOSSIBLE।" যখনই 'dependency মেনে বড় scale-এ একটা ক্রম বের করো' দেখবে — adjacency list + deque-তে Kahn চালাও, recursion এড়াও, edge দিক ও 1-indexing যাচাই করো, length দিয়ে চক্র ধরো।

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