Problem link ও উৎস
- **Original source:** Self-exercise — build on [../../09-graphs/topological-sort.md](../../09-graphs/topological-sort.md)
- **Platform:** self-exercise (no external judge; verify with your own asserts)
- **Topic:** dynamic programming on a DAG
- **Difficulty:** Hard
- **Pattern:** DP on DAG
- **Basic idea inherited from:** folder 09 (Graphs)-এর topological order — DAG-এ "fill order" আর কিছু নয়, একটা topological sort; প্রতিটা table-DP আসলে গোপনে state-গুলোর একটা DAG
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা **DAG** (directed acyclic graph — কোনো cycle নেই, এমন directed graph) দেওয়া। প্রতিটা edge `u -> v` মানে "`u`-এর পরে `v`"। তোমাকে graph-এর **longest path**-এর length (edge-সংখ্যা, বা চাইলে edge-weight-এর যোগফল) বের করতে হবে — যেকোনো node থেকে শুরু করে edge ধরে ধরে যত দূর যাওয়া যায়।
```text
edges: 0->1, 0->2, 1->3, 2->3, 3->4
সবচেয়ে লম্বা path: 0 -> 1 -> 3 -> 4 (বা 0->2->3->4) -> 4 edges
```
### Input ও output {#8-example-input-and-output}
```text
Input : n=5, edges=[(0,1),(0,2),(1,3),(2,3),(3,4)] -> Output: 3
(longest path 0->1->3->4: edges 0-1, 1-3, 3-4 = 3 edges)
Input : n=4, edges=[(0,1),(1,2),(2,3)] -> Output: 3 (straight chain)
Input : n=3, edges=[] -> Output: 0 (কোনো edge নেই)
Edge case 1: n=1, edges=[] -> Output: 0 (একা node)
Edge case 2: n=2, edges=[(0,1)] -> Output: 1
Edge case 3: forest -> দুই আলাদা chain, লম্বাটা গোনা হয়
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একগুচ্ছ কাজ, কিছু কাজ অন্য কাজ শেষ না হলে শুরুই করা যায় না (prerequisite chain — যেমন কোর্সের prerequisite)। তুমি জানতে চাও সবচেয়ে লম্বা নির্ভরতা-শেকল কত লম্বা (critical path)। প্রতিটা কাজের জন্য বলো: "আমার পরে যেসব কাজ আসে, তাদের সবচেয়ে লম্বা শেকল + আমি নিজে।" Cycle নেই বলে এই হিসাব সবসময় শেষ হয়।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত্তি folder 09-এর **topological sort**। সেখানে শেখা যায় DAG-এর node-গুলোকে এমন এক রেখায় সাজানো যায় যাতে প্রতিটা edge সবসময় বাঁ-থেকে-ডানে যায়। এটাই DP-র "fill order": কোনো node-এর উত্তর গুনতে হলে তার সব predecessor (বা successor) আগে গোনা থাকতে হবে — topological order ঠিক সেটাই নিশ্চিত করে। আসলে আগের প্রতিটা table-DP-ও গোপনে state-গুলোর একটা DAG; এখানে graph-টা explicit, ব্যস।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একটা সরল recurrence: কোনো node `v` থেকে শুরু হওয়া longest path = 1 + (তার সব out-neighbor থেকে শুরু হওয়া longest path-এর মধ্যে সবচেয়ে বড়টা), বা 0 যদি `v`-এর কোনো outgoing edge না থাকে। যেহেতু graph-এ cycle নেই, এই recurrence সবসময় থামে — কোনো node নিজের উপর ঘুরে ফিরে নির্ভর করে না। গোটা graph-এর উত্তর = সব node-এর `dp[v]`-এর max।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
- graph-টা **adjacency list** হিসেবে (`adj[u]` = `u`-এর out-neighbor-দের list)।
- একটা **array/dict** `dp`, `dp[v]` = `v` থেকে শুরু হওয়া longest path-এর length।
- order ঠিক করতে হয় একটা **topological sort** (Kahn-এর in-degree queue), নয়তো memoized DFS — যেটায় order implicit।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
State একটামাত্র node-id — কারণ `v` থেকে longest path শুধু `v`-এর downstream-এর উপর নির্ভর করে, কোন path দিয়ে `v`-তে এলাম তা নয়। তাই `dp[v]` flat array নিখুঁত। DAG হওয়ায় dependency-গুলো একটা valid linear order-এ সাজানো যায়, আর সেই order-এই (বা তার উল্টোয়) ভরলে যা পড়ি তা আগেই লেখা থাকে — ঠিক grid-DP-র row-order যেমন।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা node থেকে সব path ধরে ধরে DFS করে সবচেয়ে লম্বাটা নাও।
```text
longest_from(v): # memo ছাড়া
best = 0
for w in adj[v]:
best = max(best, 1 + longest_from(w))
return best
answer = max(longest_from(v) for all v)
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
memo ছাড়া একই node বহুবার পরিদর্শিত হয় — যদি অনেক path একই sub-DAG-এ মিলে যায়, কাজ exponential পর্যন্ত ফুলে যায় (diamond-আকৃতির graph-এ স্পষ্ট)। অথচ `dp[v]` মাত্র `n`-টা আলাদা মান; প্রতিটা একবার গুনলেই হয়, প্রতিটা edge একবার দেখা — মোট O(V + E)।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: `dp[v]` (v থেকে longest path) শুধু `v`-এর out-neighbor-দের `dp`-র উপর নির্ভর করে — পেছনের history নয়। আর cycle না থাকায় এই নির্ভরতাগুলো একটা valid order-এ সাজানো যায়। তাই প্রতিটা node একবার করে গোনা যথেষ্ট।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
**State (শব্দে):** `dp[v]` = node `v` থেকে শুরু করে DAG-এ যাওয়া যায় এমন longest path-এর length (edge-সংখ্যা)।
**Transition:**
```text
dp[v] = max( 1 + dp[w] for every edge v -> w ), or 0 if v has no out-edge
```
**Base case:** sink node (out-degree 0) → `dp[v] = 0`।
**Answer location:** `max(dp[v] for all v)` — longest path যেকোনো node থেকে শুরু হতে পারে।
**Fill order:** **reverse topological order** (sink আগে), যাতে `dp[w]` সবসময় `dp[v]`-এর আগে computed। সমতুল্যভাবে memoized DFS — সেখানে recursion নিজেই এই order তৈরি করে।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "সব path enumerate করব" — এই বিস্ফোরক চিন্তা ছাড়ো। বদলে প্রতিটা node-কে একটা ছোট প্রশ্নে নামাও: "আমার থেকে এক ধাপ এগিয়ে best কতদূর যাওয়া যায়?" Cycle না থাকা গ্যারান্টি দেয় উত্তরগুলো একটা order-এ গুছিয়ে নেওয়া যায়। এটাই সেই বড় উপলব্ধি: **প্রতিটা DP আসলে একটা DAG-এর উপর DP; topological sort সেই লুকানো order-কে দৃশ্যমান করে।**
### ছবিতে বোঝা {#7-visual-explanation}
`edges: 0->1, 0->2, 1->3, 2->3, 3->4`। `dp[v]` = `v` থেকে longest path (edges):
```text
graph: 0
/ \
1 2
\ /
3
|
4
reverse topo order: 4, 3, 1, 2, 0 (sink আগে গোনা)
dp[4] = 0 (sink, কোনো out-edge নেই)
dp[3] = 1 + dp[4] = 1
dp[1] = 1 + dp[3] = 2
dp[2] = 1 + dp[3] = 2
dp[0] = 1 + max(dp[1], dp[2]) = 3
answer = max(dp) = 3 edges (path 0 -> 1 -> 3 -> 4: edge 0-1, 1-3, 3-4)
```
খেয়াল করো `dp[v]` গুনতে গেলে তার সব successor আগে গুনতে হয় — তাই reverse topological (sink-first) order।
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`n=4`, `edges=[(0,1),(1,2),(2,3)]` (সরল chain), memoized DFS:
1. `longest(3)`: out-neighbor নেই → 0
2. `longest(2)`: `1 + longest(3) = 1`
3. `longest(1)`: `1 + longest(2) = 2`
4. `longest(0)`: `1 + longest(1) = 3`
5. answer = `max(3, 2, 1, 0) = 3`
হাতে মিলিয়ে: path `0->1->2->3` = 3 edges. ✔
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
from collections import deque
# ---- way 1: memoized DFS (order implicit) ----
def longest_path_dfs(n, edges):
adj = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
memo = [-1] * n
def dp(v): # v থেকে longest path (edges)
if memo[v] != -1:
return memo[v]
best = 0
for w in adj[v]:
best = max(best, 1 + dp(w))
memo[v] = best
return best
return max((dp(v) for v in range(n)), default=0)
# ---- way 2: Kahn topo sort + DP in reverse order ----
def longest_path_topo(n, edges):
adj = [[] for _ in range(n)]
indeg = [0] * n
for u, v in edges:
adj[u].append(v)
indeg[v] += 1
# forward topological order (source-first)
q = deque(v for v in range(n) if indeg[v] == 0)
topo = []
while q:
u = q.popleft()
topo.append(u)
for w in adj[u]:
indeg[w] -= 1
if indeg[w] == 0:
q.append(w)
dp = [0] * n
# reverse order: sink আগে process হয়, তাই dp[w] আগে ready
for u in reversed(topo):
for w in adj[u]:
dp[u] = max(dp[u], 1 + dp[w])
return max(dp) if n else 0
# ---- tests ----
cases = [
(5, [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)], 3),
(4, [(0, 1), (1, 2), (2, 3)], 3),
(3, [], 0),
(1, [], 0),
(2, [(0, 1)], 1),
(6, [(0, 1), (1, 2), (3, 4)], 2), # দুই chain, লম্বাটা 0->1->2
(4, [(0, 1), (0, 2), (0, 3)], 1), # star, প্রতিটা path 1 edge
]
for n, edges, want in cases:
assert longest_path_dfs(n, edges) == want, (n, edges, longest_path_dfs(n, edges))
assert longest_path_topo(n, edges) == want, (n, edges, longest_path_topo(n, edges))
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `longest_path_dfs`: adjacency list বানায়; `dp(v)` recursion-এ `v`-এর প্রতিটা out-neighbor-এর longest + 1-এর max নেয়; `memo` repeat এড়ায়; `default=0` খালি/edge-less graph সামলায়।
- `longest_path_topo`: in-degree গুনে Kahn algorithm-এ forward topo order বানায়; তারপর `reversed(topo)` (sink-first) ধরে `dp[u] = max(dp[u], 1 + dp[w])` — reverse order বলে `dp[w]` আগেই ready; answer `max(dp)`।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`cases`-এ সাতটা input: diamond DAG (3), straight chain (3), edge-less (0), single node (0), single edge (1), দুই বিচ্ছিন্ন chain যেখানে লম্বাটা গোনা হয় (2), আর star (প্রতি path 1 edge → 1)। প্রতিটার জন্য দুই function-ই (DFS-memo + topo) একই উত্তর দিতে হবে — DAG-এ memoized DFS আর topological DP যে সমতুল্য, এটাই তার প্রমাণ। সব pass হলে শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
দুই version-ই **O(V + E)** — প্রতিটা node একবার, প্রতিটা edge একবার দেখা হয়। (memo ছাড়া brute ছিল exponential।)
### অতিরিক্ত জায়গা {#19-space-complexity}
- দুই version-ই **O(V + E)** — adjacency list; এর সাথে DFS-এ recursion stack O(V), topo-তে queue O(V)।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- cycle থাকলে এই DP ভাঙে — recurrence থামে না (DFS infinite, Kahn-এ কিছু node কখনো queue-তে ঢোকে না)। এটা শুধু **DAG**-এর জন্য; cycle থাকলে আগে detect করো।
- answer `dp[0]` ধরা — longest path যেকোনো node থেকে শুরু হতে পারে, তাই `max(dp)` লাগে (LIS-এর মতোই)।
- forward topo order-এ সরাসরি `dp[u]=max(1+dp[w])` করা — তখন `dp[w]` এখনো গোনা হয়নি; reverse order (sink-first) লাগে, নয়তো predecessor-based ভিন্ন recurrence।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: folder 09-এর topological sort ([../../09-graphs/topological-sort.md](../../09-graphs/topological-sort.md))। [../patterns.md](../patterns.md)-এর "DP on DAG" family বলে — topological order ঠিক সেই ভূমিকা পালন করে যা table-DP-তে "fill order" করে; প্রতিটা DP-ই গোপনে state-গুলোর একটা DAG।
### পরের অনুশীলন {#22-similar-harder-problems}
- Longest Increasing Path in a Matrix (grid-কে DAG ধরা) —