Path Count via Matrix Powers

Problem

Count the number of walks of length exactly k from src to dst in a directed graph with n nodes.

The entry (src, dst) of the k-th power of the adjacency matrix counts such walks. edges is a list of [u, v] pairs; repeated edges are counted with multiplicity. Use fast exponentiation on 0/1 matrices.

Hint

Binary exponentiation computes the k-th matrix power in O(n^3 log k).

Test cases

case 1

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

expected: 1

case 2

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

expected: 1

case 3

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

expected: 1

case 4

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

expected: 2

case 5

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

expected: 0

Starter codePython

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

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