Total number of Spanning Trees in a Graph Hard 0 attempts
GeeksforGeeks ↗

Total number of Spanning Trees in a Graph

Hard GraphBFSDFS GeeksforGeeks

Given an undirected graph, count how many distinct spanning trees it has — that is, how many ways you can pick a subset of its edges that connects all vertices with no cycles. Compute this using Kirchhoff's theorem (the matrix-tree theorem).

Input Format
Implement countSpanningTrees(adj, V). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
adj = [[1,2],[0,2],[0,1]]
V = 3
Output
3

Example 2

Input
adj = [[],[],[]]
V = 3
Output
0

Example 3

Input
adj = [[]]
V = 1
Output
1
Constraints
  • 1 <= V <= 10
  • 0 <= E <= V*(V-1)/2
Test Cases (3)
Case 1
Args: [[[1,2],[0,2],[0,1]],3] Expected: 3
Case 2
Args: [[[],[],[]],3] Expected: 0
Case 3
Args: [[[]],1] Expected: 1
Topics
GraphBFSDFS

Kirchhoff's Matrix Tree Theorem

Compute any cofactor of the Laplacian matrix (degree matrix - adjacency matrix).

javascript
function countSpanningTrees(adj, V) {
  const L = Array.from({length:V}, ()=>Array(V).fill(0));
  for (let i=0;i<V;i++) for (let j=0;j<V;j++) {
    if (i===j) L[i][j] = adj[i].length;
    else if (adj[i].includes(j)) L[i][j] = -1;
  }
  const n = V-1, M = L.slice(0,n).map(r=>r.slice(0,n));
  // Gaussian elimination for determinant
  let det = 1;
  for (let i=0;i<n;i++) {
    let pivot = i;
    for (let j=i+1;j<n;j++) if (Math.abs(M[j][i])>Math.abs(M[pivot][i])) pivot=j;
    if (pivot!==i) { [M[i],M[pivot]]=[M[pivot],M[i]]; det*=-1; }
    if (Math.abs(M[i][i]) < 1e-12) return 0;
    det *= M[i][i];
    for (let j=i+1;j<n;j++) {
      const f=M[j][i]/M[i][i];
      for (let k=i;k<n;k++) M[j][k]-=f*M[i][k];
    }
  }
  return Math.round(det);
}

Time: O(V³) | Space: O(V²)

Saved in this browser only. Private to you.

JavaScript