A Hamiltonian path, is a path in an undirected graph that visits each vertex exactly once. Given an undirected graph, the task is to check if a Hamiltonian path is present in it or not.
Example 1:
Input:
N = 4, M = 4
Edges[][]= { {1,2}, {2,3}, {3,4}, {2,4} }
Output:
1 
Explanation: 
There is a hamiltonian path: 
1 -> 2 -> 3 -> 4 
Example 2:
Input:
N = 4, M = 3 
Edges[][] = { {1,2}, {2,3}, {2,4} } 
Output: 
0 
Explanation: 
It can be proved that there is no 
hamiltonian path in the given graph
Your task:
You don't need to read input or print anything. Your task is to complete the function check() which takes the N (the number of vertices), M (Number of edges) and the list of Edges[][] (where Edges[i] denotes the undirected Edge between vertices Edge[i][0] and Edges[i][1] ) as input parameter and returns true (boolean value) if the graph contains Hamiltonian path,otherwise returns false. 
Expected Time Complexity: O(N!).
Expected Auxiliary Space: O(N+M).
Constraints:
1 ≤ N ≤ 10
1 ≤ M ≤ 15
Size of Edges[i] is 2
1 ≤ Edges[i][0],Edges[i][1] ≤ N

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Graph algorithms

Data structures

Graph traversal

Complete search

Starter code: #User function Template for python3

class Solution:

    def check(self, N, M, Edges): 

        #code here

Solutions:
class Solution:

	def check(self, N, M, Edges):
		adj = [[] for _ in range(N + 1)]
		for i in range(M):
			adj[Edges[i][0]].append(Edges[i][1])
			adj[Edges[i][1]].append(Edges[i][0])
		visit = [0] * (N + 1)
		ans = [False] * 1

		def fun(i, c):
			if c == N - 1:
				ans[0] = True
				return
			if ans[0] == True:
				return
			visit[i] = 1
			for j in adj[i]:
				if visit[j] == 0:
					fun(j, c + 1)
			visit[i] = 0
		for i in range(1, N + 1):
			fun(i, 0)
			if ans[0] == True:
				return True
		return False


from collections import defaultdict

class Solution:

	def check(self, N, M, Edges):

		def findHamiltonPath(node, visited):
			if node in visited:
				return
			visited.add(node)
			if len(visited) == N:
				output.append(True)
			for item in adj[node]:
				findHamiltonPath(item, visited.copy())
		adj = defaultdict(list)
		for (i, j) in Edges:
			adj[i].append(j)
			adj[j].append(i)
		output = [False]
		for i in range(N):
			findHamiltonPath(i, set())
			if output[-1] == True:
				return True
		return False


class Solution:

	def check(self, N, M, Edges):
		adj = [[] for i in range(N)]
		for edge in Edges:
			adj[edge[0] - 1].append(edge[1] - 1)
			adj[edge[1] - 1].append(edge[0] - 1)
		for node in range(N):
			visited = set()
			if self.check_util(N, M, adj, node, visited):
				return True
		return False

	def check_util(self, N, M, adj, node, visited):
		visited.add(node)
		for child in adj[node]:
			if child in visited:
				if len(visited) == N:
					return True
				else:
					continue
			if self.check_util(N, M, adj, child, visited):
				return True
		if len(visited) == N:
			return True
		visited.remove(node)
		return False