387. Total Number of Spanning Trees in a Graph

Given an undirected graph with n vertices (0-indexed, no self-loops or repeated edges) and m edges, count the total number of distinct spanning trees it has. Print 0 if the graph is disconnected.

Input: The first line contains an integer n, the number of vertices. The second line contains an integer m, the number of edges (no self-loops or repeats). Each of the next m lines contains two space-separated integers u and v, an undirected edge. Output: Print a single integer - the total number of distinct spanning trees, or 0 if the graph is disconnected.

1 <= n <= 10

A DISCONNECTED graph's Laplacian naturally produces a SINGULAR (determinant-zero) reduced matrix - this means the formula elegantly handles the 'graph is disconnected, so it has zero spanning trees' case automatically, with no separate connectivity check needed at all.

Count the total number of distinct spanning trees a graph has. Brute force: Try every possible SUBSET of (n-1) edges and check if it forms a valid, connected, acyclic spanning tree - this is combinatorially expensive (choosing n-1 out of m edges), completely impractical beyond tiny graphs, when Kirchhoff's theorem computes the exact count directly via linear algebra. Optimised: Kirchhoff's Matrix Tree Theorem is a genuinely elegant, non-obvious result connecting GRAPH structure to LINEAR ALGEBRA - a single determinant computation (after building the Laplacian and deleting one row/column) directly yields the exact spanning tree count, completely sidestepping any need to enumerate or search through possible trees.

Build the graph's Laplacian matrix L (degree matrix minus adjacency matrix), delete any one row and the corresponding column, and compute the determinant of the resulting (n-1) x (n-1) matrix via Gaussian elimination; that determinant equals the exact number of spanning trees, a direct consequence of the Matrix Tree Theorem. This replaces exponential combinatorial search entirely with a single polynomial-time linear-algebra computation, and naturally yields 0 when the graph is disconnected since the Laplacian becomes singular in that case. Time: O(n^3) Space: O(n^2)

Since a spanning tree of an n-vertex graph has exactly n-1 edges, enumerate every subset of the m edges of size n-1, and for each subset check whether it forms a tree - that is, it connects all n vertices and contains no cycle. Counting the subsets that pass this test gives the answer directly. This checks every candidate combination exhaustively, so it is correct for any graph but its cost explodes combinatorially with the number of edges. Time: O(C(m, n-1) * n) Space: O(n)

Generate the same (n-1)-sized edge combinations, but instead of building each candidate subgraph from scratch and checking connectivity with a traversal, add edges one at a time into a Union-Find (disjoint set) structure and abandon the combination the moment an edge would connect two vertices already in the same component (a cycle). This lets most invalid combinations be discarded after only a few edges rather than after all n-1 have been chosen, and the final connectivity check becomes an O(1)-per-edge union operation instead of a full graph traversal, meaningfully cutting the constant factor even though the technique is still fundamentally combinatorial enumeration. Time: O(C(m, n-1) * alpha(n)) Space: O(n)

1. Apply KIRCHHOFF'S MATRIX TREE THEOREM: build the graph's LAPLACIAN MATRIX (diagonal entries = each vertex's degree, off-diagonal = -1 if an edge exists between that pair, else 0). 2. Delete any ONE row and the MATCHING column from this matrix. 3. The DETERMINANT of what remains equals the exact spanning tree count - compute it with INTEGER-ONLY arithmetic (like the Bareiss algorithm) to avoid floating-point rounding errors on this combinatorial count.

Time: O(n³) - computing the determinant of an (n-1)x(n-1) matrix via Gaussian elimination (or the integer-safe Bareiss algorithm). Space: O(n²), for the Laplacian matrix.

a disconnected graph (answer 0), n = 1 (a single vertex with no edges), and n at its maximum of 10 to confirm the determinant computation is exact.

Be ready to mention WHY integer-only arithmetic (like Bareiss's algorithm) matters here specifically - since the answer is a COUNT (must be an exact integer), floating-point determinant computation risks small rounding errors that could silently produce a wrong final count.