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=map(int,input().split())
path=[[[0]*(n+1)]*(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    path[a][b]=1
    path[b][a]=1
visited=[[0]*(n+1)]
visited[1]=1
def dfs(position,visited,n):
    all_visited=1
    for i in range(1,n+1):
        if visited[i]==0:
            all_visited=0
            break
    if all_visited==1:
        return 1
    count=0
    for next in range(1,n+1):
        if path[position][next]==0:
            continue
        if visited[next]==1:
            continue
        visited[next]=1
        count+=dfs(next,visited,n)
        visited[i]=0
    visited[position]=0

    return count
print(1,n,visited)

def dfs(v,n,visited):
    all_visited=1
      
    for i in range(n):
        if visited[i]==0:
            all_visited=0
    if all_visited==1:
        return 1
    count=0
    for i in range(n):
        if path[v][i]!=0:
            continue 
        if visited[i]==1:
            continue
        visited[i]=1
        count+=dfs(i,n,visited)
        visited[i]=0
    return count

n,m=map(int,input().split())
path=[[0]*n for i in range(n)]
for i in range(n):
    a,b=map(int,input().split())
    path[a-1][b-1]=1
    path[b-1][a-1]=1
visited=[0]*n
visited[0]=1
print(dfs(0,n,visited))



n,m=map(int,input().split())
path=[[[0]*n]*n]
for i in range(m):
    a,b=map(int,input().split())
    path[a][b]=1
    path[b][a]=1
visited=[[0]*n]
visited[0]=1
def dfs(position,visited,n):
    all_visited=1
    for i in range(n):
        if visited[i]==0:
            all_visited=0
            break
    if all_visited==1:
        return 1
    count=0
    for next in range(n):
        if path[position][next]==0:
            continue
        if visited[next]==1:
            continue
        visited[next]=1
        count+=dfs(next,visited,n)
        visited[i]=0
    visited[position]=0

    return count
print(0,n,visited)

n,m=map(int,input().split())
path=[[0]*n for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    path[a-1][b-1]=1
    path[b-1][a-1]=1
visited=[0]*n
visited[0]=1
def dfs(position,visited,n):
    all_visited=1
    for i in range(n):
        if visited[i]==0:
            all_visited=0
            break
    if all_visited==1:
        return 1
    count=0
    for next in range(n):
        if path[position][next]==0:
            continue
        if visited[next]==1:
            continue
        visited[next]=1
        count+=dfs(next,visited,n)
        
    visited[position]=0

    return count
print(dfs(0,visited,n))

n,m=map(int,input().split())
path=[[0]*n for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    path[a-1][b-1]=1
    path[b-1][a-1]=1
visited=[0]*n
visited[0]=1
def dfs(position,visited,n):
    all_visited=1
    for i in range(n):
        if visited[i]==0:
            all_visited=0
            break
    if all_visited==1:
        return 1
    count=0
    for next in range(n):
        if path[position][next]==0:
            continue
        if visited[next]==1:
            continue
        visited[next]=1
        count+=dfs(next,visited,n)
        visited[next]=0
    visited[position]=0

    return count
print(dfs(0,visited,n))


Verdicts: Runtime Error

Runtime Error

Runtime Error

Wrong Answer

Accepted