Spanning Tree Count via Matrix-Tree

Problem

Count the spanning trees of a connected undirected graph with the Matrix-Tree theorem.

Build the Laplacian L, delete the first row and column, and compute the determinant of the cofactor with exact integer elimination. Return the count, or 0 when the graph is disconnected. edges is a list of [u, v] pairs.

Hint

Cayley's formula gives n^(n-2) trees for the complete graph.

Test cases

case 1

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

expected: 3

case 2

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

expected: 4

case 3

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

expected: 16

case 4

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

expected: 1

case 5

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

expected: 0

Starter codePython

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

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