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 sys
sys.setrecursionlimit(100000)
N,M = map(int, input().split())
path = []
for _ in range(M):
    ai, bi = map(int, input().split())
    path.append((ai, bi))
    path.append((bi, ai))
    
ans = 0
def dfs(v, visited):
    # v: now here
    # visited: set
    global ans
    print(visited)
    if v in visited:
        return
    else:
        visited.add(v)
        
    if len(visited)==N:
        ans += 1
        
    for pi in path:
        a,b = pi[0], pi[1]
        if a==b==v:
            dfs(a, visited)
        else:
            if a==v: dfs(b, visited)
            if b==v: dfs(a, visited)


dfs(1, set([]))
loop = 0
for pi in path:
    a,b = pi[0], pi[1]
    if a==b:
        loop += 1
print(ans+loop)

import sys
sys.setrecursionlimit(100000)
N,M = map(int, input().split())
path = []
for _ in range(M):
    ai, bi = map(int, input().split())
    path.append((ai, bi))
    path.append((bi, ai))
    
ans = 0
def dfs(v, visited):
    # v: now here
    # visited: set
    global ans
#     print(visited)
    if v in visited:
        return
    else:
        visited.add(v)
        
    if len(visited)==N:
        ans += 1
        
    for pi in path:
        a,b = pi[0], pi[1]
        if a==b==v:
            dfs(a, visited)
        else:
            if a==v: dfs(b, visited)
            if b==v: dfs(a, visited)


dfs(1, set([]))
loop = 0
for pi in path:
    a,b = pi[0], pi[1]
    if a==b:
        loop += 1
print(ans+loop)

def main():
    N, M = map(int, input().split())
    edges = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(lambda x: int(x)-1, input().split())
        edges[a].append(b)
        edges[b].append(a)

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

    def dfs(v: int):
        nonlocal visited
        nonlocal ans
        if all(visited):
            ans += 1
            return
        for n in edges[v]:
            if visited[n]:
                continue
            visited[n] = True
            dfs(n)
            visited[n] = False
        return

    dfs(0)
    print(ans)


if __name__ == "__main__":
    main()


Verdicts: Wrong Answer

Wrong Answer

Accepted