023 — Longest Path in a DAG

Source

• Original source: Self-exercise — build on ../../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

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 ধরে ধরে যত দূর যাওয়া যায়।

edges: 0->1, 0->2, 1->3, 2->3, 3->4
সবচেয়ে লম্বা path: 0 -> 1 -> 3 -> 4  (বা 0->2->3->4) -> 4 edges

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 যেমন।

6. Real-life analogy

ভাবো একগুচ্ছ কাজ, কিছু কাজ অন্য কাজ শেষ না হলে শুরুই করা যায় না (prerequisite chain — যেমন কোর্সের prerequisite)। তুমি জানতে চাও সবচেয়ে লম্বা নির্ভরতা-শেকল কত লম্বা (critical path)। প্রতিটা কাজের জন্য বলো: "আমার পরে যেসব কাজ আসে, তাদের সবচেয়ে লম্বা শেকল + আমি নিজে।" Cycle নেই বলে এই হিসাব সবসময় শেষ হয়।

7. Visual explanation

edges: 0->1, 0->2, 1->3, 2->3, 3->4। dp[v] = v থেকে longest path (edges):

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।

8. Example input and output

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, লম্বাটা গোনা হয়

9. Brute force thinking

প্রথম সরল চিন্তা: প্রতিটা node থেকে সব path ধরে ধরে DFS করে সবচেয়ে লম্বাটা নাও।

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:

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-কে দৃশ্যমান করে।

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. ✔

15. Python solution

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

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

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।

21. Which basic problem this inherits from

ভিত্তি: folder 09-এর topological sort (../../09-graphs/topological-sort.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 ধরা) — https://leetcode.com/problems/longest-increasing-path-in-a-matrix/
• Course Schedule II (topological order বের করা) — https://leetcode.com/problems/course-schedule-ii/
• Parallel Courses (DAG-এ shortest "levels"/critical path) — https://leetcode.com/problems/parallel-courses/

23. Pattern learned

DP on DAG: state dp[v] = node v-এর উত্তর; transition dp[v] = combine(dp[w] for edge v->w); fill order = topological sort (বা reverse)। মূল অন্তর্দৃষ্টি: প্রতিটা DP-ই state-গুলোর একটা DAG, আর topological sort সেই লুকানো dependency-order-কে explicit করে দেয়।

24. Final summary

ভবিষ্যতের আমাকে: "DAG longest path = DP on topological order।" State dp[v] = v থেকে longest path, transition max(1 + dp[w]) over out-edges, base sink=0, fill reverse-topo, answer max(dp)। মনে রেখো: cycle নেই বলেই order বের করা যায় — আর এই "fill order = topo sort" অন্তর্দৃষ্টি গোটা DP folder-কে graph-এর সাথে বেঁধে দেয়।

---

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