# Topological Sort — Dependencies-এর দুনিয়াকে Order করা

> Data structure: directed graph + queue (Kahn) অথবা DFS post-order। Thinking tweak: যার আর কোনো prerequisite বাকি নেই, সেটা *এখনই* করা নিরাপদ।

---

## Analogy: একটা recipe রান্না করা, একটা degree schedule করা

একটা recipe বলে: ডিম ফাটাও → ডিম ফেটাও → batter-এ মেশাও; oven preheat করো → bake করো। কিছু step অন্যদের আগে আসতেই হবে; অনেক জোড়ার কিছুই যায় আসে না (ডিম ফাটানোর আগে বা পরে — যখন খুশি preheat করতে পারো)। **Topological order** হলো এমন যেকোনো complete step list, যেটা কোনো arrow ভাঙে না।

একই shape: university-র courses। Calculus 1, তারপর Calculus 2, তারপর Calculus 3; Intro Programming, তারপর Data Structures। তোমার degree plan টা আসলে prerequisite graph-এর একটা topological sort।

Formal version: একটা **directed** graph দেওয়া আছে, nodes-গুলোকে এক লাইনে output করো যাতে প্রতিটা edge `u → v`-তে `u` আসে `v`-র **আগে**। মাথায় গেঁথে নেওয়ার দুটো fact:

- Order টা সাধারণত **unique না** — independent steps যেকোনো relative order-এ যেতে পারে। "A valid order", "the order" না।
- এটা exist করে **iff** graph-এ কোনো directed cycle নেই (একটা DAG)। "A requires B requires C requires A" কখনোই linearize করা যাবে না — cycle-টা একটা deadlock।

## Kahn's algorithm: zero-indegree layer-টা ছাড়িয়ে নাও

কোনো node-এর **indegree** = ঢুকতে থাকা arrows-এর সংখ্যা = unmet prerequisites-এর সংখ্যা। Kahn-এর insight: indegree 0-ওয়ালা node-কে আটকানোর *কিছুই* নেই — এখনই করো। সেটা করলে তার outgoing arrows সরে যায়, যা নতুন nodes মুক্ত করতে পারে। Repeat।

```python
from collections import deque

def topo_sort(nodes, adj):
    indeg = {n: 0 for n in nodes}
    for u in nodes:
        for v in adj[u]:
            indeg[v] += 1

    q = deque(n for n in nodes if indeg[n] == 0)    # everything doable NOW
    order = []
    while q:
        node = q.popleft()
        order.append(node)
        for nxt in adj[node]:
            indeg[nxt] -= 1                          # one prerequisite cleared
            if indeg[nxt] == 0:                      # fully unblocked!
                q.append(nxt)

    return order if len(order) == len(nodes) else None   # None = cycle
```

Cost: O(V + E) — প্রতিটা node একবার enqueue হয়, প্রতিটা edge একবার decrement হয়।

### একটা course graph-এ queue-র frames

```text
   intro ──> ds ──> algo
     │               ^
     └────> math ────┘          (algo needs both ds and math)

indegrees:  intro:0  ds:1  math:1  algo:2
```

```text
Frame 0: queue = [intro]                 order = []
Frame 1: pop intro -> order=[intro]
         ds: 1->0  (enqueue)   math: 1->0  (enqueue)
         queue = [ds, math]
Frame 2: pop ds    -> order=[intro, ds]
         algo: 2->1            queue = [math]
Frame 3: pop math  -> order=[intro, ds, math]
         algo: 1->0 (enqueue)  queue = [algo]
Frame 4: pop algo  -> order=[intro, ds, math, algo]   queue empty. Done.
```

`[intro, math, ds, algo]`-ও সমানভাবে valid হতো — ds আর math পরস্পরকে constrain করে না। (*Alphabetically smallest* valid order চাও — একটা common competitive-programming twist? Queue-টা বদলে [../08-heap-priority-queue/](../08-heap-priority-queue/README.md)-এর একটা min-heap বসাও।)

### Cycle = queue-টা আগেভাগেই অনাহারে থাকে

```text
   a ──> b
   ^     │        indegrees: a:1  b:1  c:1
   └── c <┘       NOBODY starts at indegree 0
```

Queue শুরুই হয় খালি অবস্থায়, `order` শেষ হয় 3-টার মধ্যে 0-টা node নিয়ে, আর length check টা `None` return করে। আংশিক cyclic graph-এ acyclic অংশটা process হয়ে যায় আর cycle-এর সদস্যরা কখনোই indegree 0-তে পৌঁছায় না — `len(order) < len(nodes)` হলো universal cycle alarm। ঠিক এভাবেই [Course Schedule](https://leetcode.com/problems/course-schedule/) "possible?" এর উত্তর দেয় আর [Course Schedule II](https://leetcode.com/problems/course-schedule-ii/) plan-টা produce করে।

## DFS alternative: উল্টানো post-order

[dfs.md](dfs.md) থেকে: কোনো node-এর **post-order timestamp** বাজে কেবল তখন, যখন *তার থেকে reachable সবকিছু* পুরোপুরি explore হয়ে গেছে। তাই একটা DAG-এ যেকোনো edge `u → v`-র জন্য, `v` finish করে `u`-র **আগে** — মানে finish order টা হলো একটা valid topological order, *উল্টো করে*।

```python
def topo_sort_dfs(nodes, adj):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {n: WHITE for n in nodes}
    out = []

    def dfs(node):
        color[node] = GRAY
        for nxt in adj[node]:
            if color[nxt] == GRAY:          # back edge: cycle
                return False
            if color[nxt] == WHITE and not dfs(nxt):
                return False
        color[node] = BLACK
        out.append(node)                    # POST-order: appended when finished
        return True

    for n in nodes:
        if color[n] == WHITE and not dfs(n):
            return None                     # cycle found
    return out[::-1]                        # reverse the finish order
```

একই O(V + E), একই cycle detection ([dfs.md](dfs.md)-এর GRAY trick)। কোনটা ব্যবহার করবে?

| | Kahn (BFS-style) | DFS post-order |
| --- | --- | --- |
| Mental model | unblocked nodes-কে layer by layer ছাড়িয়ে নাও | dependents শেষ করো, তারপর নিজের নাম ঘোষণা করো |
| Cycle signal | output V-এর চেয়ে ছোট | একটা GRAY node-এর সাথে দেখা |
| Easy extras | lexicographic order (heap), প্রতিটা task-এর "level" | পরের algorithms-এর জন্য preorder/postorder timestamps |
| Recursion risk | নেই | গভীর graph overflow করতে পারে (iterative-এ যাও) |

দুটোই interview-standard; একটা পুরোপুরি ঠোঁটস্থ রাখো, অন্যটা sketch করার মতো ভালোভাবে জানো।

## DP-on-DAG teaser

Topological order শুধু একটা scheduling-এর উত্তর না — এটা **graph-এ dynamic programming-এর একটা নিরাপদ processing order**। Topo order-এ nodes process করো, তাহলে node `v`-তে পৌঁছানোর সময় প্রতিটা predecessor-এর answer ইতিমধ্যেই final:

```python
# longest path ending at each node of a DAG (impossible on cyclic graphs!)
longest = {n: 0 for n in nodes}
for u in topo_order:
    for v in adj[u]:
        longest[v] = max(longest[v], longest[u] + 1)
```

Paths গোনা, *DAG-এ* negative weights সহ shortest paths, project-duration (critical path) calculation — সবই একটা topological order-এর উপর এক relaxation loop। পরে এই repo-তে dynamic programming-এ পৌঁছালে মনে রেখো: **DP-র "solve subproblems first" আসলে subproblems-এর মধ্যকার dependency graph-এর একটা topological order।** যে idea-টা এইমাত্র শিখলে, সেটাই চুপচাপ পুরো DP-র নিচে শুয়ে আছে।

## Common mistakes (সাধারণ ভুল)

- **Undirected** graph-এ topological sort চালানো — concept-টা শুধু directed graph-এর জন্যই exist করে।
- শেষের `len(order) == len(nodes)` check টা ভুলে যাওয়া — cyclic input তখন নিঃশব্দে একটা অসম্পূর্ণ "order" দেয়।
- Edges উল্টো বানানো: "course A requires B" মানে edge **B → A** (B unlock করে A-কে)। উল্টানো edges একটা নিখুঁত valid *reverse* schedule produce করে — classic silent bug।
- DFS post-order list উল্টাতে ভুলে যাওয়া।
- Output unique ধরে নিয়ে tests-এ একটা expected order hard-code করা।

## Trigger words

"Prerequisites", "dependencies", "build/install order", "schedule with constraints", "must come before", "is it possible to finish everything", "derive an ordering from constraints" (Alien Dictionary), "longest chain of dependent tasks"।

## Representative problems

- [Course Schedule](https://leetcode.com/problems/course-schedule/) — শুধু cycle detection ("কোনো order possible?")।
- [Course Schedule II](https://leetcode.com/problems/course-schedule-ii/) — আসল order-টা produce করো; প্রায় হুবহু Kahn।
- [CSES Course Schedule](https://cses.fi/problemset/task/1679) — scale-এ competitive-programming version।
- [Alien Dictionary](https://leetcode.com/problems/alien-dictionary/) — আগে sorted words থেকে constraint graph *বানাও*, তারপর topo-sort করো; sorting-এর চেয়ে বেশি modeling পরীক্ষা করে।
- [Longest Increasing Path in a Matrix](https://leetcode.com/problems/longest-increasing-path-in-a-matrix/) — increasing moves-এর implicit DAG-এ DP।

Reference treatment: [cp-algorithms topological sort](https://cp-algorithms.com/graph/topological-sort.html)। Course-graph dry run সহ runnable Kahn আছে [implementation.py](implementation.py)-তে। চারটা theory file পড়া শেষ — এবার তুমি [problems/README.md](problems/README.md)-এর জন্য তৈরি।