Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 21 Feb, 2021

Hard

```
A spanning tree T of an undirected graph G is a subgraph that is a tree that includes all of the vertices of G. A graph that is not connected will not contain a spanning tree.
```

```
The first line of the input contains an integer T denoting the number of test cases.
The first line of each test case contains two space-separated integers N and M, the number of nodes, and the edges.
The next ‘M’ line of each test case contains two space-separated integers X and Y, denoting an edge between X and Y.
```

```
For every test case, the only output line should contain an integer X, the total number of spanning trees in a graph.
The output of each test case should be printed in a new line.
```

```
You do not need to print anything; it has already been taken care of. Just implement the given function.
```

```
1 <= T <= 5
1 <= N <= 10
N-1 <= M <= N*(N-1)/2
0 <= 'X', 'Y' <= N - 1
Where 'T' denotes the number of test cases, 'N' and 'M' denotes the number of nodes and edges, respectively. And, 'X', 'Y' denotes the node in the graph.
Time limit : 1 sec
```

First, check if the given graph is a tree or a complete graph.

- If the given graph is a tree, then the number of spanning-tree will be 1.
- If the given graph is a complete graph, then the number of spanning trees will be equal to N^(N-2) (Cayley’s Theorem), where N is the number of nodes in the graph.

**Algorithm : **

**Make an adjacency matrix ‘adj’ for the given graph.****Then, calculate the degree of each node by counting the number of non-zero entries in its row in the adjacency matrix.****Replace the diagonal entry(Primary Diagonal) of each row with its respective degree that we calculated in Step 2.****Replace all the non-diagonal values = 1 with -1 by traversing the adjacency matrix.****Then, calculate the cofactor of any one element since all the elements’ cofactors will be equal.****Cofactor = ((adj[i][j])^(i+j))* |D|,**

**where |D| is the determinant of the matrix we get by deleting ith row and jth column from the adjacency matrix.**

** **

**For calculating the determinant of the N*N matrix, we can break this into subproblems of the determinant of submatrices ((N-1)*(N-1)). |D| will be equal to Summation of ((-1)^(i+j))) * (Determinant of the matrix we get by deleting 1st row and jth column from the adjacency matrix) where j goes from 1 to N.****Hence, we can make a recursive function for calculating the Determinant in which matrix[ ][ ] and N will be argument with base condition of N=2, in which the determinant is a[1][1]*a[2][2] - a[1][2]*a[2][1].****Return the cofactor, which will be equal to the number of spanning trees.**

Similar problems

Minimum Swaps To Make Identical Array

Moderate

Posted: 22 Jan, 2022

Find Center of Star Graph

Easy

Posted: 26 Jan, 2022

Critical Connections in a Network

Hard

Posted: 27 Jan, 2022

Critical Connections in a Network

Hard

Posted: 27 Jan, 2022

Critical Connections in a Network

Hard

Posted: 27 Jan, 2022

Critical Connections in a Network

Hard

Posted: 27 Jan, 2022

COUNT ISLANDS

Moderate

Posted: 14 Sep, 2022

Distance to a Cycle in Undirected Graph

Moderate

Posted: 7 Nov, 2022