Problem link ও উৎস
- **Original source:** Classic topological-ordering exercise (competitive-programming scale)
- **Platform:** CSES Problem Set —
- **Topic:** graphs
- **Difficulty:** Medium
- **Pattern:** topological sort, CP scale (Kahn)
- **Basic idea inherited from:** Course Schedule II ([016-course-schedule-ii.md](016-course-schedule-ii.md), এই tracker-এর #16); topological sort ([../topological-sort.md](../topological-sort.md))
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#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 অবধি)।
```text
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 {#8-example-input-and-output}
```text
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
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা বড় সিলেবাস ভাবো যেখানে কিছু বিষয় আগের বিষয় শেষ না করলে পড়া যায় না। প্রতিটা বিষয়ের পাশে লিখে রাখো "এর আগে আর কয়টা বিষয় বাকি"। যেগুলোর পাশে 0 — সেগুলো এখনই পড়তে পারো, পড়ে ফেলো। প্রতিটা শেষ-করা বিষয় যাদের আনলক করে, তাদের পাশের সংখ্যা এক কমাও; নতুন কারো পাশে 0 হলে সেও এখন পড়া যায়। সব বিষয় এভাবে শেষ হলে তোমার হাতে একটা বৈধ পড়ার ক্রম; কিছু বিষয় চিরকাল আটকে থাকলে বুঝবে বৃত্তাকার নির্ভরতা — সিলেবাসটা অসম্ভব।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
মূল ভিত হলো #16 Course Schedule II ([016-course-schedule-ii.md](016-course-schedule-ii.md)) — হুবহু **Kahn's algorithm**: indegree গোনো, indegree-0 node ছাড়ো, dependents-এর indegree কমাও, repeat ([../topological-sort.md](../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-এর সম্ভাব্য সমস্যা)।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: course-গুলোর সব `n!` permutation ঘুরে দেখা, প্রতিটার জন্য যাচাই করা সব requirement মানা হচ্ছে কিনা।
```text
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।
### ছবিতে বোঝা {#7-visual-explanation}
`n=4`, requirements `(1,2),(2,3),(1,4)` (edge a->b):
```text
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-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`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]`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```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!")
```
### কোডের প্রতিটি অংশ {#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`)।
### Output মিলিয়ে দেখা {#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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: #16 Course Schedule II ([016-course-schedule-ii.md](016-course-schedule-ii.md)) আর topological sort theory ([../topological-sort.md](../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) —