Count Paths in a DAG

01 · Question

Given a directed adjacency list and a valid source vertex, return the number of paths from the source to every vertex. Count the empty path from the source to itself once. Unreachable vertices have count zero. Assume there are no duplicate edges and counts fit signed 64-bit integers. Reject a cycle anywhere in the graph (None in Python, a false status in Go).

Example: graph=[[1,2],[3],[3],[]], source=0 returns [1,1,1,2].

02 · Analysis

Initialize ways[source]=1. Kahn's queue guarantees all predecessors are processed before a vertex; when removing u, add ways[u] along every outgoing edge, then decrement indegrees. Each path to a neighbor has one final incoming edge, so the additions count disjoint possibilities. Compare processed count with V to reject cycles, including disconnected ones. O(V+E) time and O(V) auxiliary space. This counts paths, not possible topological orderings.

03 · Solution

Reference solution

1from collections import deque
2
3def dag_path_counts(graph, source):
4    indegree = [0] * len(graph)
5    for neighbors in graph:
6        for node in neighbors:
7            indegree[node] += 1
8    ready = deque(i for i, count in enumerate(indegree) if count == 0)
9    ways = [0] * len(graph)
10    ways[source] = 1
11    processed = 0
12    while ready:
13        node = ready.popleft()
14        processed += 1
15        for neighbor in graph[node]:
16            ways[neighbor] += ways[node]
17            indegree[neighbor] -= 1
18            if indegree[neighbor] == 0:
19                ready.append(neighbor)
20    return ways if processed == len(graph) else None

Find All Possible Recipes from Given Supplies