
#https://www.youtube.com/watch?v=jGRRBJlNtwI
class Graph():
    def __init__(self, vertices):
        self.graph = [[0 for column in range(vertices)] for row in range(vertices)]
        self.V = vertices
    def ifSafe(self, v, pos ,path):
        if self.graph[path[pos-1]][v] == 0:
            return False
        for vertex in path:
            if vertex == v:
                return False
        return True
    def hamCycleUtil(self, path, pos):
        if pos == self.V:
            if self.graph[path[pos-1]][path[0]] == 1:
                return True
            else:
                return False
        for v in range(1, self.V):
            if self.ifSafe(v, pos, path) == True:
                path[pos] = v
                if self.hamCycleUtil(path, pos+1) == True:
                    return True
                path[pos] = -1
        return False
    def hamcycle(self):
        path = [-1] * self.V
        path[0] = 0
        if self.hamCycleUtil(path, 1) == False:
            print("path doesnt exist")
            return False
        self.printsol(path)
        return True
    def printsol(self, path):
        print("Solution Exists: Following", "is one Hamiltonian Cycle")
        for vertex in path:
            print(vertex, end = " ")
        print(path[0], "\n")

g1 = Graph(5)
g1.graph = [ [0, 1, 0, 1, 0], [1, 0, 1, 1, 1], 
            [0, 1, 0, 0, 1,],[1, 1, 0, 0, 1], 
            [0, 1, 1, 1, 0], ]
g1.hamcycle();
        