DP on a DAG (Topological Order & Relaxation)

If states form a DAG (edges only forward in topological order), DP is just relaxing edges in topo order—no cycles, no extra SCC work.

Why this shows up in the real world

Course prerequisite chains compute longest path length. Build systems layer tasks.

Core idea (explained for students)

Topo sort nodes, then dp[v] = max(dp[u]+w) for each edge u→v. For counting paths, sum instead of max.

Try this in Python

from collections import deque


def longest_path_on_dag(n: int, edges: list[tuple[int, int, int]]) -> int:
    indeg = [0] * n
    adj: list[list[tuple[int, int]]] = [[] for _ in range(n)]
    for u, v, w in edges:
        adj[u].append((v, w))
        indeg[v] += 1
    q = deque([i for i in range(n) if indeg[i] == 0])
    dp = [0] * n
    while q:
        u = q.popleft()
        for v, w in adj[u]:
            dp[v] = max(dp[v], dp[u] + w)
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return max(dp)


print(longest_path_on_dag(4, [(0, 1, 3), (1, 2, 2), (0, 2, 5), (2, 3, 1)]))

Common mistakes

• Hidden back-edge creating a cycle—DP invalid.
• Wrong topo when graph disconnected.

Key takeaways

• Detect cycles first if constraints allow dependencies both ways.
• Run from every source if multiple sources exist.