DAG All Paths Count DP

Problem

Count the number of distinct directed paths from src to dst in a DAG with n nodes.

Process nodes in topological order and propagate the number of ways to reach each node: ways[src] starts at 1 and every edge adds ways[u] to ways[v]. If src cannot reach dst the count is 0. edges is a list of [u, v] pairs.

Hint

Path counts multiply and add along a topological order.

Test cases

case 1

in: [4,[[0,1],[0,2],[1,3],[2,3]],0,3]

expected: 2

case 2

in: [4,[[0,1],[1,2],[1,3],[2,3]],0,3]

expected: 2

case 3

in: [3,[[0,1],[1,2]],0,2]

expected: 1

case 4

in: [3,[[0,1]],0,2]

expected: 0

Starter codePython

import heapq
def dag_all_paths(n, edges, src, dst):
    # Your code here
    pass

4 test cases · run your code against them in the editor