Counting Routes in a DAG — Solution & Editorial

Back to the Problem

Topologically sort, then DP: ways[v] = ∑ ways[u] over predecessors, seeded with ways[1] = 1.

Complexity: O(N + M)