Problem: You are given an undirected unweighted graph with N vertices and M edges that contains neither self-loops nor double edges.   Here, a _self-loop_ is an edge where a_i = b_i (1≤i≤M), and _double edges_ are two edges where (a_i,b_i)=(a_j,b_j) or (a_i,b_i)=(b_j,a_j) (1≤i<j≤M).   How many different paths start from vertex 1 and visit all the vertices exactly once?   Here, the endpoints of a path are considered visited.  For example, let us assume that the following undirected graph shown in Figure 1 is given.    Figure 1: an example of an undirected graph  The following path shown in Figure 2 satisfies the condition.    Figure 2: an example of a path that satisfies the condition  However, the following path shown in Figure 3 does not satisfy the condition, because it does not visit all the vertices.    Figure 3: an example of a path that does not satisfy the condition  Neither the following path shown in Figure 4, because it does not start from vertex 1.    Figure 4: another example of a path that does not satisfy the condition

Submission attempts (in order):

class Graph():
    def __init__(self):
        
        self.adjacency_dict = {}
    
    def add_vertex(self, v):
        
        self.adjacency_dict[v] = []
    def add_edge(self, v1, v2):
        
        
        self.adjacency_dict[v1].append(v2)
        self.adjacency_dict[v2].append(v1)
    def remove_edge(self, v1, v2):
        
        self.adjacency_dict[v1].remove(v2)
        self.adjacency_dict[v2].remove(v1)
    def remove_vertex(self,v):
        
        while self.adjacency_dict[v] != []:
            adjacent_vertex = self.adjacency_dict[v][-1]
            self.remove_edge(v, adjacent_vertex)
        del self.adjacency_dict[v]
    
    def print_graph(self):
        print(self.adjacency_dict)

    def _init_internal_graph(self, graph_dict):
        self.adjacency_dict = graph_dict
    
    def get_edge(self, v):
        
        return self.adjacency_dict[v]

def dprint(*args):
  if len(args)==1:
    print(args[0])
  else:
    print(args)

debug = False
if debug:
  g = Graph()
  # N,M = [7, 7]
  # g._init_internal_graph({0: [2], 1: [6], 2: [0, 3], 3: [2, 4, 5], 4: [3, 5], 5: [3, 4, 6], 6: [1, 5]})
  
  N,M = [3, 3]
  g._init_internal_graph({0: [1, 2], 1: [0, 2], 2: [0, 1]})
else:
  N, M = map(int, input().split())
  g = Graph()
  dprint(N,M)

  for n in range(N):
    g.add_vertex(n)

  # 0-origin    
  for m in range(M):
      v1,v2 = list(map(int, input().split()))
      g.add_edge(v1-1,v2-1)                     

# g.print_graph()

seen = [False] * N
count = 0

def dfs(node, depth):
    dprint(node,depth)        
    if seen[node]:
        return 0
    if depth == N - 1:
        dprint('count-up',seen)
        return 1

    seen[node] = True
    dprint(seen)
    
    total_paths = 0
    for next_node in g.get_edge(node):
      total_paths += dfs(next_node, depth + 1)

    
    seen[node] = False

    return total_paths

count = dfs(0, 0)
print(count)


class Graph():
    def __init__(self):
        
        self.adjacency_dict = {}
    
    def add_vertex(self, v):
        
        self.adjacency_dict[v] = []
    def add_edge(self, v1, v2):
        
        
        self.adjacency_dict[v1].append(v2)
        self.adjacency_dict[v2].append(v1)
    def remove_edge(self, v1, v2):
        
        self.adjacency_dict[v1].remove(v2)
        self.adjacency_dict[v2].remove(v1)
    def remove_vertex(self,v):
        
        while self.adjacency_dict[v] != []:
            adjacent_vertex = self.adjacency_dict[v][-1]
            self.remove_edge(v, adjacent_vertex)
        del self.adjacency_dict[v]
    
    def print_graph(self):
        print(self.adjacency_dict)

    def _init_internal_graph(self, graph_dict):
        self.adjacency_dict = graph_dict
    
    def get_edge(self, v):
        
        return self.adjacency_dict[v]

def dprint(*args):
  if debug:
    if len(args)==1:
      print(args[0])
    else:
      print(args)

debug = False
if debug:
  g = Graph()
  # N,M = [7, 7]
  # g._init_internal_graph({0: [2], 1: [6], 2: [0, 3], 3: [2, 4, 5], 4: [3, 5], 5: [3, 4, 6], 6: [1, 5]})
  
  N,M = [3, 3]
  g._init_internal_graph({0: [1, 2], 1: [0, 2], 2: [0, 1]})
else:
  N, M = map(int, input().split())
  g = Graph()
  dprint(N,M)

  for n in range(N):
    g.add_vertex(n)

  # 0-origin    
  for m in range(M):
      v1,v2 = list(map(int, input().split()))
      g.add_edge(v1-1,v2-1)                     

# g.print_graph()

seen = [False] * N
count = 0

def dfs(node, depth):
    dprint(node,depth)        
    if seen[node]:
        return 0
    if depth == N - 1:
        dprint('count-up',seen)
        return 1

    seen[node] = True
    dprint(seen)
    
    total_paths = 0
    for next_node in g.get_edge(node):
      total_paths += dfs(next_node, depth + 1)

    
    seen[node] = False

    return total_paths

count = dfs(0, 0)
print(count)


Verdicts: Wrong Answer

Accepted