017 — Course Schedule (CSES)¶

Source¶

Original source: Classic topological-ordering exercise (competitive-programming scale)
Platform: CSES Problem Set — https://cses.fi/problemset/task/1679
Topic: graphs
Difficulty: Medium
Pattern: topological sort, CP scale (Kahn)
Basic idea inherited from: Course Schedule II (016-course-schedule-ii.md, এই tracker-এর #16); topological sort (../topological-sort.md)

1. Problem in simple words¶

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 order: 1 2 4 3 (বা 1 2 3 4 -> না, 1->4 মানে... এখানে 1 আগে; 1 2 3 4 ও valid)

2. Which basic idea does this inherit from?¶

মূল ভিত হলো #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।

3. What is the hidden math or logic?¶

লুকানো 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।

4. Which data structure is needed?¶

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 — চূড়ান্ত ক্রম।

5. Why this data structure fits¶

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-এর সম্ভাব্য সমস্যা)।

6. Real-life analogy¶

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

7. Visual explanation¶

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

8. Example input and 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

9. Brute force thinking¶

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

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

10. Why brute force is slow¶

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 লাগে না।

11. Key observation¶

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

12. Optimized intuition¶

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

13. Thinking tweak¶

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

14. Step-by-step dry run¶

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

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

15. Python solution¶

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

16. Line-by-line code explanation¶

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

17. Output walkthrough¶

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

18. Time complexity¶

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

19. Space complexity¶

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

20. Common mistakes¶

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।

21. Which basic problem this inherits from¶

ভিত্তি: #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।

22. Similar harder problems¶

Alien Dictionary (sorted words থেকে constraint graph + topo sort) — https://leetcode.com/problems/alien-dictionary/ (এই tracker-এর #24)
Parallel Courses (topo sort + minimum semester গোনা) — https://leetcode.com/problems/parallel-courses/
Longest Increasing Path in a Matrix (implicit DAG-এ DP, topo order) — https://leetcode.com/problems/longest-increasing-path-in-a-matrix/

23. Pattern learned¶

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-দিক সাবধানে সামলাও।

24. Final summary¶

ভবিষ্যতের আমাকে: "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।