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):


import copy


N, M = map(int, input().split())



Graph_list = [[] for i in range(N)]


for i in range(M):
    a, b = map(int, input().split())
    a += -1
    b += -1

    
    Graph_list[a].append(b)
    Graph_list[b].append(a)

ans_count = 0
throwgh_point_list = [-1 for i in range(N)]

def dfs(i, current, throwgh_point_list, ans_point_list):   
    
    if i >= N:
        
        if throwgh_point_list in ans_point_list:
            print('カウント済み')
            print(throwgh_point_list)
            return

        
        
        if set(throwgh_point_list) == set(list(range(N))):
            global ans_count
            ans_count += 1
            ans_point_list.append(copy.copy(throwgh_point_list))
            print(throwgh_point_list)
        return

    for j in range(len(Graph_list[current])):
        
        throwgh_point_list[i] = current

        
        dfs(i + 1, Graph_list[current][j], throwgh_point_list, ans_point_list)

dfs(0, 0, throwgh_point_list, [])
print(ans_count)



import copy
import sys
input = sys.stdin.readline


N, M = map(int, input().split())



Graph_list = [[] for i in range(N)]


for i in range(M):
    a, b = map(int, input().split())
    a += -1
    b += -1

    
    Graph_list[a].append(b)
    Graph_list[b].append(a)

ans_count = 0           
visited = [False] * N
visited[0] = True

def dfs(i, current, visited):   
    
    if i >= N-1:

        
        
        if all(visited):
            global ans_count
            ans_count += 1
            return 
        return 

    for j in Graph_list[current]:
        if visited[j] == False:
            
            visited[j] = True
            
            dfs(i + 1, j, visited)

dfs(0, 0, visited)
print(ans_count)



import copy


N, M = map(int, input().split())



Graph_list = [[] for i in range(N)]


for i in range(M):
    a, b = map(int, input().split())
    a += -1
    b += -1

    
    Graph_list[a].append(b)
    Graph_list[b].append(a)

ans_count = 0
throwgh_point_list = [-1 for i in range(N)]

def dfs(i, current, throwgh_point_list, ans_point_list):   
    
    if i >= N:
        
        if throwgh_point_list in ans_point_list:
            return

        
        
        if set(throwgh_point_list) == set(list(range(N))):
            global ans_count
            ans_count += 1
            ans_point_list.append(copy.copy(throwgh_point_list))
            print(throwgh_point_list)
        return

    for j in range(len(Graph_list[current])):
        
        throwgh_point_list[i] = current

        
        dfs(i + 1, Graph_list[current][j], throwgh_point_list, ans_point_list)

dfs(0, 0, throwgh_point_list, [])
print(ans_count)



import copy
import sys
input = sys.stdin.readline


N, M = map(int, input().split())



Graph_list = [[] for i in range(N)]


for i in range(M):
    a, b = map(int, input().split())
    a += -1
    b += -1

    
    Graph_list[a].append(b)
    Graph_list[b].append(a)

ans_count = 0           
visited = [False] * N
visited[0] = True

def dfs(i, current, visited):   
    
    if i >= N-1:

        
        if all(visited):
            global ans_count
            ans_count += 1
            return 
        return 

    for j in Graph_list[current]:
        if visited[j] == False:
            
            visited[j] = True
            
            dfs(i + 1, j, visited)

            visited[j] = False

dfs(0, 0, visited)
print(ans_count)

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Accepted