DAG Reachability DP

Problem

Compute the set of nodes reachable from src in a DAG with n nodes.

Process nodes in reverse topological order and union each node's reachability with the reachability of its out-neighbors. Return the sorted list of reachable nodes, including src itself. edges is a list of [u, v] pairs.

Hint

Reverse topological order makes every successor already computed.

Test cases

case 1

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

expected: [0,1,2,3]

case 2

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

expected: [0]

case 3

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

expected: [2]

Starter codePython

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

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