Given a connected undirected graph of N edges and M vertices. The task is the find the total number of spanning trees possible in the graph.
Note: A spanning tree is a subset of Graph G, which has all the vertices covered with the minimum possible number of edges. Hence, a spanning tree does not have cycles and it cannot be disconnected. By this definition, we can draw a conclusion that every connected and undirected Graph G has at least one spanning tree.
Example 1:
Input:
N = 6, M = 5
graph = {{0, 3}
         {0, 1}
         {1, 2}.
         {1, 5},
         {3, 4}}
Output: 1
Explanation: 
Only one spanning tree is possible,i.e. the graph itself.
{{0, 1},
 {0, 3},
 {1, 2},
 {1, 5},
 {3, 4}}
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function countSpanningTrees() which takes two integers N and M and a 2D matrix denoting the connected edges and returns an integers as output.
 
Expected Time Complexity: O(N^{4})
Expected Auxiliary Space: O(N^{2})
 
Constraints:
1 <= N <= 10
N - 1 <= M <= N *(N - 1) / 2
0 <= graph[i][0], graph[i][1] <= N - 1

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: from typing import List





from typing import List





class Solution:

    def countSpanningTrees(self, graph : List[List[int]],n : int,m : int) -> int:

        # code here

        



Solutions:
from typing import List
from typing import List
import numpy as np

class Solution:

	def countSpanningTrees(self, graph, n, m):
		edges = graph
		indegree = [0 for i in range(n)]
		laplacian = np.zeros(shape=(n, n))
		for edge in edges:
			indegree[edge[0]] += 1
			indegree[edge[1]] += 1
			laplacian[edge[0]][edge[1]] = -1
			laplacian[edge[1]][edge[0]] = -1
		for i in range(n):
			laplacian[i, i] = indegree[i]
		cofactor = round(np.linalg.det(laplacian[1:, 1:]))
		return int(cofactor)


from typing import List
from typing import List
import numpy as np

class Solution:

	def countSpanningTrees(self, graph: List[List[int]], m: int, n: int) -> int:
		M = np.zeros(shape=(m, m))
		indegree = [0 for _ in range(m)]
		for edge in graph:
			(u, v) = edge
			M[u, v] = -1
			M[v, u] = -1
			indegree[u] += 1
			indegree[v] += 1
		for i in range(m):
			M[i, i] = indegree[i]
		noOfSpanningTrees = np.linalg.det(M[1:, 1:])
		return int(round(noOfSpanningTrees))


from typing import List
import numpy as np

class Solution:

	def countSpanningTrees(self, graph: List[List[int]], m: int, n: int) -> int:
		mat = np.zeros(shape=(m, m))
		indeg = [0 for _ in range(m)]
		for e in graph:
			(u, v) = e
			mat[u][v] = -1
			mat[v][u] = -1
			indeg[u] += 1
			indeg[v] += 1
		for i in range(m):
			mat[i][i] = indeg[i]
		mst = np.linalg.det(mat[1:, 1:])
		return int(round(mst))


from typing import List
from collections import *
from typing import List
import numpy as np
import math

class Solution:

	def countSpanningTrees(self, graph: List[List[int]], n: int, m: int) -> int:
		g = defaultdict(set)
		indegree = defaultdict(int)
		for i in graph:
			g[i[0]].add(i[1])
			g[i[1]].add(i[0])
		for i in g:
			for j in g[i]:
				indegree[j] += 1
		matrix = [[None for _ in range(n)] for _ in range(n)]
		newmatrix = [[None for _ in range(n - 1)] for _ in range(n - 1)]
		for i in range(n):
			for j in range(n):
				if i == j:
					matrix[i][j] = indegree[i]
				elif i in g[j]:
					matrix[i][j] = -1
				else:
					matrix[i][j] = 0
		for i in range(n - 1):
			for j in range(n - 1):
				newmatrix[i][j] = matrix[i][j]
		resarr = np.array(newmatrix)
		x = np.linalg.det(resarr)
		return int(round(x))


from typing import List
from typing import List
import numpy as np
import math

class Solution:

	def countSpanningTrees(self, graph: List[List[int]], n: int, m: int) -> int:
		adj = [[0 for _ in range(n)] for _ in range(n)]
		deg = [0] * n
		for (u, v) in graph:
			adj[u][v] = -1
			adj[v][u] = -1
			deg[u] += 1
			deg[v] += 1
		for i in range(n):
			for j in range(n):
				if i == j:
					adj[i][j] = deg[i]
		det = []
		for i in range(1, n):
			det.append(adj[i][1:])
		n_array = np.array(det)
		d = np.linalg.det(n_array)
		return int(round(d))


from typing import List
from typing import List

class Solution:

	def countSpanningTrees(self, graph: List[List[int]], n: int, m: int) -> int:
		import numpy as np
		adj = [[0 for i in range(n)] for j in range(n)]
		deg = [[0 for i in range(n)] for j in range(n)]
		for edge in graph:
			adj[edge[0]][edge[1]] = 1
			adj[edge[1]][edge[0]] = 1
			deg[edge[0]][edge[0]] += 1
			deg[edge[1]][edge[1]] += 1
		adj = np.array(adj)
		deg = np.array(deg)
		lap = deg - adj
		cofactor = lap[1:, 1:]
		return int(round(np.linalg.det(cofactor)))


from typing import List
from typing import List
import numpy as np

class Solution:

	def countSpanningTrees(self, graph: List[List[int]], n: int, m: int) -> int:
		M = np.zeros(shape=(n, n))
		indegree = [0 for _ in range(n)]
		for edge in graph:
			(u, v) = edge
			M[u, v] = -1
			M[v, u] = -1
			indegree[u] += 1
			indegree[v] += 1
		for i in range(n):
			M[i, i] = indegree[i]
		noOfSpanningTrees = np.linalg.det(M[1:, 1:])
		return int(round(noOfSpanningTrees))

class IntArray:

	def __init__(self) -> None:
		pass

	def Input(self, n):
		arr = [int(i) for i in input().strip().split()]
		return arr

	def Print(self, arr):
		for i in arr:
			print(i, end=' ')
		print()

class IntMatrix:

	def __init__(self) -> None:
		pass

	def Input(self, n, m):
		matrix = []
		for _ in range(n):
			matrix.append([int(i) for i in input().strip().split()])
		return matrix

	def Print(self, arr):
		for i in arr:
			for j in i:
				print(j, end=' ')
			print()
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		a = IntArray().Input(2)
		graph = IntMatrix().Input(a[1], a[1])
		obj = Solution()
		res = obj.countSpanningTrees(graph, a[0], a[1])
		print(res)


import numpy as np

class Solution:

	def countSpanningTrees(self, graph, n, m):
		adj = [[0 for i in range(n)] for j in range(n)]
		indegree = [0 for i in range(n)]
		for i in graph:
			u = i[0]
			v = i[1]
			adj[u][v] = -1
			adj[v][u] = -1
			indegree[u] += 1
			indegree[v] += 1
		for i in range(n):
			adj[i][i] = indegree[i]
		adj = np.array(adj)
		cofactor = np.linalg.det(adj[1:, 1:])
		return int(round(cofactor))


from typing import List
from typing import List

class Solution:

	def countSpanningTrees(self, graph: List[List[int]], n: int, m: int) -> int:

		def coMatrix(m, i, j):
			return [row[:j] + row[j + 1:] for row in m[:i] + m[i + 1:]]

		def det(m):
			if len(m) == 0:
				return 0
			if len(m) == 1:
				return m[0][0]
			if len(m) == 2:
				return m[0][0] * m[1][1] - m[0][1] * m[1][0]
			res = 0
			for i in range(len(m)):
				sign = (-1) ** i
				d = det(coMatrix(m, 0, i))
				res += m[0][i] * sign * d
			return res
		adjL = [[0 for i in range(n)] for j in range(n)]
		for i in graph:
			adjL[i[0]][i[1]] = -1
			adjL[i[1]][i[0]] = -1
			adjL[i[1]][i[1]] += 1
			adjL[i[0]][i[0]] += 1
		return det(coMatrix(adjL, 0, 0))


from typing import List
from typing import List
import numpy as np

class Solution:

	def countSpanningTrees(self, graph: List[List[int]], n: int, m: int) -> int:
		matrix = []
		for i in range(n):
			x = []
			for j in range(n):
				x.append(0)
			matrix.append(x)
		degree = [0] * n
		for i in graph:
			matrix[i[0]][i[1]] = -1
			matrix[i[1]][i[0]] = -1
			degree[i[0]] += 1
			degree[i[1]] += 1
		for i in range(n):
			matrix[i][i] = degree[i]
		new_mat = []
		for i in range(1, n):
			x = []
			for j in range(1, n):
				x.append(matrix[i][j])
			new_mat.append(x)
		n_arr = np.array(new_mat)
		det = np.linalg.det(n_arr)
		return int(round(det))


from typing import List

class Solution:

	def countSpanningTrees(self, graph: List[List[int]], n: int, m: int) -> int:
		import numpy as np
		adj = []
		adj2 = []
		for i in range(n):
			new = []
			for j in range(n):
				new.append(0)
			adj.append(new)
		for i in graph:
			adj[i[0]][i[1]] = 1
			adj[i[1]][i[0]] = 1
		for i in range(len(adj)):
			adj[i][i] = sum(adj[i])
		for i in range(n):
			for j in range(n):
				if i != j and adj[i][j] == 1:
					adj[i][j] = -1
		for i in range(n - 1):
			new = []
			for j in range(n - 1):
				new.append(0)
			adj2.append(new)
		for i in range(1, n):
			for j in range(1, n):
				adj2[i - 1][j - 1] = adj[i][j]
		s = str(np.linalg.det(adj2))
		return s[:-2]