Walk Count Length K

Problem

Count directed walks of length exactly k that start at src in a directed graph with n nodes.

Return the number of walks ending at each node, using dynamic programming over k steps: start with one walk at src and extend every walk along each outgoing edge. edges is a list of [u, v] pairs.

Hint

The DP vector is exactly the row of A^k corresponding to the source.

Test cases

case 1

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

expected: [1,0,0]

case 2

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

expected: [0,1,0]

case 3

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

expected: [1,0]

case 4

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

expected: [0,1,0]

Starter codePython

def walk_count_dp(n, edges, src, k):
    # Your code here
    pass

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