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):
N, M = list(map(int, input().split(" ")))

graph = [list() for i in range(N+1)]

for i in range(M):
    a, b = list(map(int, input().split(" ")))
    graph[a].append(b)
    graph[b].append(a)
    
def DFS(node, prev, visited):
    visited.append(node)
    if len(visited) == N:
        return 1
    
    res = 0
    for edge in graph[node]:
        if edge == prev:
            continue
        elif edge in visited:
            continue
        res += dfs(edge, node, visited)
        
    return res

print(DFS(1, 0, []))

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

graph = [list() for i in range(N+1)]

for i in range(M):
    a, b = list(map(int, input().split(" ")))
    graph[a].append(b)
    graph[b].append(a)
    
def DFS(node, prev, visited):
    visited.append(node)
    if len(visited) == N:
        return 1
    
    res = 0
    for edge in graph[node]:
        if edge == prev:
            continue
        elif edge in visited:
            continue
        res += DFS(edge, node, visited)
        
    return res

print(DFS(1, 0, []))

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

graph = [list() for i in range(N+1)]

for i in range(M):
    a, b = list(map(int, input().split(" ")))
    graph[a].append(b)
    graph[b].append(a)
    
def DFS(node, prev, visited):
    visited.append(node)
    if len(visited) == N:
        return 1
    
    res = 0
    for edge in graph[node]:
        if edge == prev:
            continue
        elif edge in visited:
            continue
        res += dfs(edge, node, visited)
        
    return res

print(DFS(1, 0, []))

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

graph = [list() for i in range(N+1)]

for i in range(M):
    a, b = list(map(int, input().split(" ")))
    graph[a].append(b)
    graph[b].append(a)
    
def DFS(node, prev, visited):
    visited.append(node)
    if len(visited) == N:
        return 1
    
    res = 0
    for edge in graph[node]:
        if edge == prev:
            continue
        elif edge in visited:
            continue
        res += DFS(edge, node, visited[:])
        
    return res

print(DFS(1, 0, []))

Verdicts: Runtime Error

Wrong Answer

Runtime Error

Accepted