Closed Walk Count

Problem

Count closed walks of length exactly k in an undirected graph: walks that start and end at the same node.

The count equals the trace of A^k, where A is the adjacency matrix. A length-0 walk counts once per node. If k is 0 return n. edges is a list of [u, v] pairs with each edge listed once.

Hint

The trace of A^k counts closed walks because the diagonal restricts start and end to the same node.

Test cases

case 1

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

expected: 6

case 2

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

expected: 2

case 3

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

expected: 32

case 4

in: [1,[],5]

expected: 0

case 5

in: [1,[],0]

expected: 1

Starter codePython

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

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