37.01Intermediate / Advanced5 topics16 min5 interactive animations

DAG DP patterns

Dynamic programming on a DAG: the topological order is the order of the states, and the same loop counts paths, finds the heaviest or cheapest path, and counts reachable vertices.

Learning goals

Treat vertices as DP states and a topological order as the evaluation order
Count paths, with and without a modulus
Find the heaviest path anywhere and the cheapest path between two vertices
Count how many vertices each vertex can reach

Prerequisites

Topological sortDAG algorithmsDynamic programming basics

Dynamic programming needs states whose dependencies form no cycle. A DAG is exactly that: the vertices are the states and the arrows are the dependencies, so the topological order tells you what to compute first.

37.01.1

Topological state order

In a DP over a DAG, the value of a vertex depends on its predecessors (a *forward* DP) or on its successors (a *backward* DP). A topological order lists vertices so that every predecessor comes first; evaluate forward DPs in that order and backward DPs in the reverse order. Either way, when a vertex is computed everything it needs is ready.

The code counts the paths from every vertex **to** a target t: a backward DP over the reverse topological order, ways[u] = sum of ways[v] over the arrows u → v. Without a topological order the same recurrence would need memoised recursion.

Java

1static long[] pathsToTarget(int n, int[][] edges, int t) {         // ways[u] = number of paths from u to t in a DAG
2    int[] order = topoOrder(n, edges);
3    long[] ways = new long[n];
4    ways[t] = 1;                                                    // the empty path
5    for (int i = n - 1; i >= 0; i--) {                              // successors first: reverse topological order
6        int u = order[i];
7        for (int[] e : edges) if (e[0] == u) ways[u] += ways[e[1]];
8    }
9    return ways;
10}
11
12static int[] topoOrder(int n, int[][] edges) {                      // Kahn's order of a DAG
13    int[] indeg = new int[n], order = new int[n];
14    for (int[] e : edges) indeg[e[1]]++;
15    Deque<Integer> q = new ArrayDeque<>();
16    for (int v = 0; v < n; v++) if (indeg[v] == 0) q.add(v);
17    int k = 0;
18    while (!q.isEmpty()) {
19        int u = q.poll();
20        order[k++] = u;
21        for (int[] e : edges) if (e[0] == u && --indeg[e[1]] == 0) q.add(e[1]);
22    }
23    return order;
24}

Dynamic programming over a topological order: longest, shortest, count of paths

Interactive · edit the input

directed graph · 6 vertices · 9 edges

d=0

Vertex being processedSourceReachable (value shown)Done

topological order

best[v]

-1

-2

-3

-4

-5

Setup

A DAG has a topological order: 0 → 1 → 2 → 3 → 5 → 4. Processing vertices in that order means every arrow into a vertex has been handled before the vertex is used, so its value is final. The source starts at 0.

Step 1 / 11

Java

1long[] dagBest(int n, List<int[]>[] adj, int[] order, int s, boolean longest) {   // adj[u] = {v, weight}
2    long NONE = longest ? Long.MIN_VALUE : Long.MAX_VALUE;
3    long[] best = new long[n]; Arrays.fill(best, NONE);
4    best[s] = 0;
5    for (int u : order) {                        // topological order: best[u] is final when u is reached
6        if (best[u] == NONE) continue;           // not reachable from s
7        for (int[] e : adj[u]) {
8            long cand = best[u] + e[1];
9            if (best[e[0]] == NONE || (longest ? cand > best[e[0]] : cand < best[e[0]])) best[e[0]] = cand;
10        }
11    }
12    return best;
13}
14long[] countPaths(int n, List<int[]>[] adj, int[] order, int s) {
15    long[] ways = new long[n]; ways[s] = 1;
16    for (int u : order) for (int[] e : adj[u]) ways[e[0]] += ways[u];   // paths into u extend along every arrow out of u
17    return ways;
18}

Live state

0 arrows relaxed

order

[0, 1, 2, 3, 5, 4]

source

No condition evaluated on this step

Execution trace (dry run table)Show 11 steps

Step	Line	State	What happens
1	L3	order=[0, 1, 2, 3, 5, 4] source=0	A DAG has a topological order: 0 → 1 → 2 → 3 → 5 → 4. Processing vertices in that order means every arrow into a vertex has been handled before the vertex is used, so its value is final. The source starts at 0.
2	L9	u=0 v=1 cand=5 best[v]=5	0 → 1: 0 + 5 = 5. That beats the old value, so best[1] = 5.
3	L9	u=0 v=2 cand=3 best[v]=3	0 → 2: 0 + 3 = 3. That beats the old value, so best[2] = 3.
4	L9	u=1 v=3 cand=11 best[v]=11	1 → 3: 5 + 6 = 11. That beats the old value, so best[3] = 11.
5	L9	u=1 v=2 cand=7 best[v]=7	1 → 2: 5 + 2 = 7. That beats the old value, so best[2] = 7.
6	L9	u=2 v=4 cand=11 best[v]=11	2 → 4: 7 + 4 = 11. That beats the old value, so best[4] = 11.
7	L9	u=2 v=5 cand=9 best[v]=9	2 → 5: 7 + 2 = 9. That beats the old value, so best[5] = 9.
8	L9	u=2 v=3 cand=14 best[v]=14	2 → 3: 7 + 7 = 14. That beats the old value, so best[3] = 14.
9	L9	u=3 v=5 cand=15 best[v]=15	3 → 5: 14 + 1 = 15. That beats the old value, so best[5] = 15.
10	L9	u=3 v=4 cand=15 best[v]=15	3 → 4: 14 + 1 = 15. That beats the old value, so best[4] = 15.
11	L11	return=[0, 5, 7, 14, 15, 15] arrows relaxed=9	Values: [0, 5, 7, 14, 15, 15] ('-' = not reachable). Every arrow was used exactly once, so the whole computation is O(n + m). The longest path ends at 4 with length 15: 0 → 1 → 2 → 3 → 4 (read back through the parent links).

37.01.2

Number of paths

To count the paths from s to v, add up the counts of all predecessors: ways[v] = sum of ways[u] over arrows u → v, with ways[s] = 1. Parallel arrows count separately, since they are different paths. The number of paths can grow exponentially, so answers are often asked modulo a prime such as 1_000_000_007.

Take the remainder after each addition to avoid overflow. The *Count the paths* option of the DAG animation shows the counts building up along the topological order.

Java

1static long countPathsModulo(int n, int[][] edges, int s, int t, long mod) {   // paths s -> t in a DAG, modulo mod
2    int[] order = topoOrder(n, edges);
3    long[] ways = new long[n];
4    ways[s] = 1 % mod;
5    for (int u : order)
6        for (int[] e : edges)
7            if (e[0] == u) ways[e[1]] = (ways[e[1]] + ways[u]) % mod;       // every path to u extends along this arrow
8    return ways[t];
9}
10
11static int[] topoOrder(int n, int[][] edges) {                      // Kahn's order of a DAG
12    int[] indeg = new int[n], order = new int[n];
13    for (int[] e : edges) indeg[e[1]]++;
14    Deque<Integer> q = new ArrayDeque<>();
15    for (int v = 0; v < n; v++) if (indeg[v] == 0) q.add(v);
16    int k = 0;
17    while (!q.isEmpty()) {
18        int u = q.poll();
19        order[k++] = u;
20        for (int[] e : edges) if (e[0] == u && --indeg[e[1]] == 0) q.add(e[1]);
21    }
22    return order;
23}

Dynamic programming over a topological order: longest, shortest, count of paths

Interactive · edit the input

directed graph · 6 vertices · 9 edges

d=0

Vertex being processedSourceReachable (value shown)Done

topological order

best[v]

-1

-2

-3

-4

-5

Setup

Step 1 / 11

Java

1long[] dagBest(int n, List<int[]>[] adj, int[] order, int s, boolean longest) {   // adj[u] = {v, weight}
2    long NONE = longest ? Long.MIN_VALUE : Long.MAX_VALUE;
3    long[] best = new long[n]; Arrays.fill(best, NONE);
4    best[s] = 0;
5    for (int u : order) {                        // topological order: best[u] is final when u is reached
6        if (best[u] == NONE) continue;           // not reachable from s
7        for (int[] e : adj[u]) {
8            long cand = best[u] + e[1];
9            if (best[e[0]] == NONE || (longest ? cand > best[e[0]] : cand < best[e[0]])) best[e[0]] = cand;
10        }
11    }
12    return best;
13}
14long[] countPaths(int n, List<int[]>[] adj, int[] order, int s) {
15    long[] ways = new long[n]; ways[s] = 1;
16    for (int u : order) for (int[] e : adj[u]) ways[e[0]] += ways[u];   // paths into u extend along every arrow out of u
17    return ways;
18}

Live state

0 arrows relaxed

order

[0, 1, 2, 3, 5, 4]

source

No condition evaluated on this step

Execution trace (dry run table)Show 11 steps

Step	Line	State	What happens
1	L3	order=[0, 1, 2, 3, 5, 4] source=0	A DAG has a topological order: 0 → 1 → 2 → 3 → 5 → 4. Processing vertices in that order means every arrow into a vertex has been handled before the vertex is used, so its value is final. The source starts at 0.
2	L9	u=0 v=1 cand=5 best[v]=5	0 → 1: 0 + 5 = 5. That beats the old value, so best[1] = 5.
3	L9	u=0 v=2 cand=3 best[v]=3	0 → 2: 0 + 3 = 3. That beats the old value, so best[2] = 3.
4	L9	u=1 v=3 cand=11 best[v]=11	1 → 3: 5 + 6 = 11. That beats the old value, so best[3] = 11.
5	L9	u=1 v=2 cand=7 best[v]=7	1 → 2: 5 + 2 = 7. That beats the old value, so best[2] = 7.
6	L9	u=2 v=4 cand=11 best[v]=11	2 → 4: 7 + 4 = 11. That beats the old value, so best[4] = 11.
7	L9	u=2 v=5 cand=9 best[v]=9	2 → 5: 7 + 2 = 9. That beats the old value, so best[5] = 9.
8	L9	u=2 v=3 cand=14 best[v]=14	2 → 3: 7 + 7 = 14. That beats the old value, so best[3] = 14.
9	L9	u=3 v=5 cand=15 best[v]=15	3 → 5: 14 + 1 = 15. That beats the old value, so best[5] = 15.
10	L9	u=3 v=4 cand=15 best[v]=15	3 → 4: 14 + 1 = 15. That beats the old value, so best[4] = 15.
11	L11	return=[0, 5, 7, 14, 15, 15] arrows relaxed=9	Values: [0, 5, 7, 14, 15, 15] ('-' = not reachable). Every arrow was used exactly once, so the whole computation is O(n + m). The longest path ends at 4 with length 15: 0 → 1 → 2 → 3 → 4 (read back through the parent links).

37.01.3

Maximum path weight

The heaviest path **anywhere** in a weighted DAG (it may start and end at any vertices) uses best[v] = the heaviest path ending at v. A path may start at v itself, so best[v] = max(0, best[u] + w) over arrows u → v. The answer is the largest best[v]. With negative weights the zero lets a path restart where it would otherwise lose weight.

This is the DAG version of the maximum-subarray idea (Kadane's algorithm). The same pass also gives project critical paths when the weights are task durations.

Java

1static long maxPathWeight(int n, int[][] edges) {                   // heaviest path with at least one vertex; 0 for a single vertex
2    int[] order = topoOrder(n, edges);
3    long[] best = new long[n];                                      // heaviest path that ends at v
4    long answer = 0;
5    for (int u : order) {
6        answer = Math.max(answer, best[u]);
7        for (int[] e : edges)
8            if (e[0] == u) best[e[1]] = Math.max(best[e[1]], best[u] + e[2]);   // extend, or keep a fresh start at 0
9    }
10    return answer;
11}
12
13static int[] topoOrder(int n, int[][] edges) {                      // Kahn's order of a DAG
14    int[] indeg = new int[n], order = new int[n];
15    for (int[] e : edges) indeg[e[1]]++;
16    Deque<Integer> q = new ArrayDeque<>();
17    for (int v = 0; v < n; v++) if (indeg[v] == 0) q.add(v);
18    int k = 0;
19    while (!q.isEmpty()) {
20        int u = q.poll();
21        order[k++] = u;
22        for (int[] e : edges) if (e[0] == u && --indeg[e[1]] == 0) q.add(e[1]);
23    }
24    return order;
25}

Dynamic programming over a topological order: longest, shortest, count of paths

Interactive · edit the input

directed graph · 6 vertices · 9 edges

d=0

Vertex being processedSourceReachable (value shown)Done

topological order

best[v]

-1

-2

-3

-4

-5

Setup

Step 1 / 11

Java

1long[] dagBest(int n, List<int[]>[] adj, int[] order, int s, boolean longest) {   // adj[u] = {v, weight}
2    long NONE = longest ? Long.MIN_VALUE : Long.MAX_VALUE;
3    long[] best = new long[n]; Arrays.fill(best, NONE);
4    best[s] = 0;
5    for (int u : order) {                        // topological order: best[u] is final when u is reached
6        if (best[u] == NONE) continue;           // not reachable from s
7        for (int[] e : adj[u]) {
8            long cand = best[u] + e[1];
9            if (best[e[0]] == NONE || (longest ? cand > best[e[0]] : cand < best[e[0]])) best[e[0]] = cand;
10        }
11    }
12    return best;
13}
14long[] countPaths(int n, List<int[]>[] adj, int[] order, int s) {
15    long[] ways = new long[n]; ways[s] = 1;
16    for (int u : order) for (int[] e : adj[u]) ways[e[0]] += ways[u];   // paths into u extend along every arrow out of u
17    return ways;
18}

Live state

0 arrows relaxed

order

[0, 1, 2, 3, 5, 4]

source

No condition evaluated on this step

Execution trace (dry run table)Show 11 steps

Step	Line	State	What happens
1	L3	order=[0, 1, 2, 3, 5, 4] source=0	A DAG has a topological order: 0 → 1 → 2 → 3 → 5 → 4. Processing vertices in that order means every arrow into a vertex has been handled before the vertex is used, so its value is final. The source starts at 0.
2	L9	u=0 v=1 cand=5 best[v]=5	0 → 1: 0 + 5 = 5. That beats the old value, so best[1] = 5.
3	L9	u=0 v=2 cand=3 best[v]=3	0 → 2: 0 + 3 = 3. That beats the old value, so best[2] = 3.
4	L9	u=1 v=3 cand=11 best[v]=11	1 → 3: 5 + 6 = 11. That beats the old value, so best[3] = 11.
5	L9	u=1 v=2 cand=7 best[v]=7	1 → 2: 5 + 2 = 7. That beats the old value, so best[2] = 7.
6	L9	u=2 v=4 cand=11 best[v]=11	2 → 4: 7 + 4 = 11. That beats the old value, so best[4] = 11.
7	L9	u=2 v=5 cand=9 best[v]=9	2 → 5: 7 + 2 = 9. That beats the old value, so best[5] = 9.
8	L9	u=2 v=3 cand=14 best[v]=14	2 → 3: 7 + 7 = 14. That beats the old value, so best[3] = 14.
9	L9	u=3 v=5 cand=15 best[v]=15	3 → 5: 14 + 1 = 15. That beats the old value, so best[5] = 15.
10	L9	u=3 v=4 cand=15 best[v]=15	3 → 4: 14 + 1 = 15. That beats the old value, so best[4] = 15.
11	L11	return=[0, 5, 7, 14, 15, 15] arrows relaxed=9	Values: [0, 5, 7, 14, 15, 15] ('-' = not reachable). Every arrow was used exactly once, so the whole computation is O(n + m). The longest path ends at 4 with length 15: 0 → 1 → 2 → 3 → 4 (read back through the parent links).

37.01.4

Minimum cost path

For the cheapest path from s to t, set cost[s] = 0 and relax each arrow in topological order: cost[v] = min(cost[v], cost[u] + w). Vertices not reachable from s keep "unreachable". Because the order guarantees every arrow into v was tried before v is used, **negative weights** are allowed, and the work is O(n + m).

Compare with Dijkstra, which needs non-negative weights and a heap. The *Shortest path in a DAG* preset in the animation shows vertices before the source staying unreachable.

Java

1static long dagMinCost(int n, int[][] edges, int s, int t) {       // Long.MAX_VALUE when t is unreachable; weights may be negative
2    int[] order = topoOrder(n, edges);
3    long[] cost = new long[n];
4    Arrays.fill(cost, Long.MAX_VALUE);
5    cost[s] = 0;
6    for (int u : order) {
7        if (cost[u] == Long.MAX_VALUE) continue;
8        for (int[] e : edges)
9            if (e[0] == u && cost[u] + e[2] < cost[e[1]]) cost[e[1]] = cost[u] + e[2];
10    }
11    return cost[t];
12}
13
14static int[] topoOrder(int n, int[][] edges) {                      // Kahn's order of a DAG
15    int[] indeg = new int[n], order = new int[n];
16    for (int[] e : edges) indeg[e[1]]++;
17    Deque<Integer> q = new ArrayDeque<>();
18    for (int v = 0; v < n; v++) if (indeg[v] == 0) q.add(v);
19    int k = 0;
20    while (!q.isEmpty()) {
21        int u = q.poll();
22        order[k++] = u;
23        for (int[] e : edges) if (e[0] == u && --indeg[e[1]] == 0) q.add(e[1]);
24    }
25    return order;
26}

Dynamic programming over a topological order: longest, shortest, count of paths

Interactive · edit the input

directed graph · 6 vertices · 9 edges

d=0

Vertex being processedSourceReachable (value shown)Done

topological order

best[v]

-1

-2

-3

-4

-5

Setup

Step 1 / 11

Java

1long[] dagBest(int n, List<int[]>[] adj, int[] order, int s, boolean longest) {   // adj[u] = {v, weight}
2    long NONE = longest ? Long.MIN_VALUE : Long.MAX_VALUE;
3    long[] best = new long[n]; Arrays.fill(best, NONE);
4    best[s] = 0;
5    for (int u : order) {                        // topological order: best[u] is final when u is reached
6        if (best[u] == NONE) continue;           // not reachable from s
7        for (int[] e : adj[u]) {
8            long cand = best[u] + e[1];
9            if (best[e[0]] == NONE || (longest ? cand > best[e[0]] : cand < best[e[0]])) best[e[0]] = cand;
10        }
11    }
12    return best;
13}
14long[] countPaths(int n, List<int[]>[] adj, int[] order, int s) {
15    long[] ways = new long[n]; ways[s] = 1;
16    for (int u : order) for (int[] e : adj[u]) ways[e[0]] += ways[u];   // paths into u extend along every arrow out of u
17    return ways;
18}

Live state

0 arrows relaxed

order

[0, 1, 2, 3, 5, 4]

source

No condition evaluated on this step

Execution trace (dry run table)Show 11 steps

Step	Line	State	What happens
1	L3	order=[0, 1, 2, 3, 5, 4] source=0	A DAG has a topological order: 0 → 1 → 2 → 3 → 5 → 4. Processing vertices in that order means every arrow into a vertex has been handled before the vertex is used, so its value is final. The source starts at 0.
2	L9	u=0 v=1 cand=5 best[v]=5	0 → 1: 0 + 5 = 5. That beats the old value, so best[1] = 5.
3	L9	u=0 v=2 cand=3 best[v]=3	0 → 2: 0 + 3 = 3. That beats the old value, so best[2] = 3.
4	L9	u=1 v=3 cand=11 best[v]=11	1 → 3: 5 + 6 = 11. That beats the old value, so best[3] = 11.
5	L9	u=1 v=2 cand=7 best[v]=7	1 → 2: 5 + 2 = 7. That beats the old value, so best[2] = 7.
6	L9	u=2 v=4 cand=11 best[v]=11	2 → 4: 7 + 4 = 11. That beats the old value, so best[4] = 11.
7	L9	u=2 v=5 cand=9 best[v]=9	2 → 5: 7 + 2 = 9. That beats the old value, so best[5] = 9.
8	L9	u=2 v=3 cand=14 best[v]=14	2 → 3: 7 + 7 = 14. That beats the old value, so best[3] = 14.
9	L9	u=3 v=5 cand=15 best[v]=15	3 → 5: 14 + 1 = 15. That beats the old value, so best[5] = 15.
10	L9	u=3 v=4 cand=15 best[v]=15	3 → 4: 14 + 1 = 15. That beats the old value, so best[4] = 15.
11	L11	return=[0, 5, 7, 14, 15, 15] arrows relaxed=9	Values: [0, 5, 7, 14, 15, 15] ('-' = not reachable). Every arrow was used exactly once, so the whole computation is O(n + m). The longest path ends at 4 with length 15: 0 → 1 → 2 → 3 → 4 (read back through the parent links).

37.01.5

Reachability counts

How many vertices can each vertex reach? Counting paths would count a vertex several times if it is reachable in several ways, so use sets: reach[u] = {u} united with reach[v] for every successor v, computed in reverse topological order. With one BitSet per vertex each union is a few word operations; the answer is the cardinality.

Storing all sets takes O(n²) bits, which is fine for thousands of vertices. For larger graphs the exact count is hard, and approximate sketches are used. The *Descendants* option in the facts animation shows one such set.

Java

1static int[] reachableCounts(int n, int[][] edges) {                // counts[u] = vertices reachable from u, u included; edges form a DAG
2    int[] order = topoOrder(n, edges);
3    BitSet[] reach = new BitSet[n];
4    int[] counts = new int[n];
5    for (int i = n - 1; i >= 0; i--) {
6        int u = order[i];
7        reach[u] = new BitSet(n);
8        reach[u].set(u);
9        for (int[] e : edges) if (e[0] == u) reach[u].or(reach[e[1]]);   // the successors are finished already
10        counts[u] = reach[u].cardinality();
11    }
12    return counts;
13}
14
15static int[] topoOrder(int n, int[][] edges) {                      // Kahn's order of a DAG
16    int[] indeg = new int[n], order = new int[n];
17    for (int[] e : edges) indeg[e[1]]++;
18    Deque<Integer> q = new ArrayDeque<>();
19    for (int v = 0; v < n; v++) if (indeg[v] == 0) q.add(v);
20    int k = 0;
21    while (!q.isEmpty()) {
22        int u = q.poll();
23        order[k++] = u;
24        for (int[] e : edges) if (e[0] == u && --indeg[e[1]] == 0) q.add(e[1]);
25    }
26    return order;
27}

Directed graph facts: degrees, sources, sinks, descendants and ancestors

Interactive · edit the input

directed graph · 6 vertices · 6 edges

Arrow being read / vertex being expandedSource (in-degree 0)ReachedSink (out-degree 0)

in-degree

out-degree

Setup

Every vertex starts with in-degree 0 and out-degree 0. Each arrow a → b adds 1 to the out-degree of a and 1 to the in-degree of b.

Step 1 / 8

Java

1int[][] degrees(List<List<Integer>> g) {         // {in-degree, out-degree} per vertex
2    int n = g.size(); int[] in = new int[n], out = new int[n];
3    for (int u = 0; u < n; u++) for (int v : g.get(u)) { out[u]++; in[v]++; }
4    return new int[][]{in, out};                 // source: in == 0, sink: out == 0
5}
6List<Integer> descendants(List<List<Integer>> g, int s) {   // reached by one or more arrows
7    boolean[] seen = new boolean[g.size()];
8    Deque<Integer> stack = new ArrayDeque<>(g.get(s));
9    List<Integer> found = new ArrayList<>();
10    while (!stack.isEmpty()) {
11        int u = stack.pop();
12        if (seen[u]) continue;
13        seen[u] = true; found.add(u);
14        for (int v : g.get(u)) stack.push(v);
15    }
16    return found;                                // contains s only when s lies on a cycle
17}
18// ancestors(g, s) = descendants(reverse(g), s)

Live state

0 arrows read0 vertices reached

arrows

No condition evaluated on this step

Execution trace (dry run table)Show 8 steps

Step	Line	State	What happens
1	L2	n=6 arrows=6	Every vertex starts with in-degree 0 and out-degree 0. Each arrow a → b adds 1 to the out-degree of a and 1 to the in-degree of b.
2	L3	arrow=0 → 1 out[a]=1 in[b]=1	Arrow 0 → 1: out-degree of 0 is now 1, in-degree of 1 is now 1.
3	L3	arrow=0 → 2 out[a]=2 in[b]=1	Arrow 0 → 2: out-degree of 0 is now 2, in-degree of 2 is now 1.
4	L3	arrow=1 → 3 out[a]=1 in[b]=1	Arrow 1 → 3: out-degree of 1 is now 1, in-degree of 3 is now 1.
5	L3	arrow=2 → 3 out[a]=1 in[b]=2	Arrow 2 → 3: out-degree of 2 is now 1, in-degree of 3 is now 2.
6	L3	arrow=2 → 4 out[a]=2 in[b]=1	Arrow 2 → 4: out-degree of 2 is now 2, in-degree of 4 is now 1.
7	L3	arrow=3 → 5 out[a]=1 in[b]=1	Arrow 3 → 5: out-degree of 3 is now 1, in-degree of 5 is now 1.
8	L4	return=in [0, 1, 1, 2, 1, 1] out [2, 1, 2, 1, 0, 0] sources [0] sinks [4, 5]	Sources (in-degree 0): [0]. Sinks (out-degree 0): [4, 5]. The in-degrees add up to 6, the out-degrees to 6: both equal the 6 arrows.

Practice ladder

Now try it yourself

Easy

All Paths From Source to Target

Medium

Number of Ways to Arrive at Destination
Parallel Courses III
Longest Increasing Path in a Matrix

Advanced

Largest Color Value in a Directed Graph

Key takeaways

On a DAG the states are the vertices and the topological order is the evaluation order.
Forward DP follows the order, backward DP follows its reverse.
Counting paths adds predecessor counts, usually modulo a prime.
Cheapest paths on a DAG tolerate negative weights and need no heap; use sets or bitsets for reachability counts.