TnT/Multi_CodeNet4Repair huggingface dataset:
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 itertools
N,M = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(M)]
r = list(range(1,N+1))
ok = 1
cnt = 0
for v in itertools.permutations(r):
    if(v[0] == 1):
        ok = 1
        for i in range(N-1):
            if(list(v[i:i+2]) not in ab and list(reversed(v[i:i+2])) not in ab):
                ok = 0
                break
        print(ok,v)
        if(ok == 1):
            cnt += 1
print(cnt)

import itertools
N,M = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(M)]
r = list(range(1,N+1))
ok = 1
cnt = 0
for v in itertools.permutations(r):
    if(v[0] == 1):
        ok = 1
        for i in range(N-1):
            if(list(v[i:i+2]) not in ab and list(reversed(v[i:i+2])) not in ab):
                ok = 0
                break
        if(ok == 1):
            cnt += 1
print(cnt)

Verdicts: Wrong Answer

Accepted
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())
G = [[] for i in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
l = [i for i in range(2,N+1)]
import itertools
ans = 0
for v in itertools.permutations(l):
    s = 1
    t = 1
    while v:
        s = t
        t = v.pop(0)
        if t not in G[s]:
            break
    if len(v) == 0:
        ans += 1
print(ans)

N,M = map(int,input().split())
G = [[] for i in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
l = [i for i in range(2,N+1)]
import itertools
ans = 0
for v in itertools.permutations(l):
    v = list(v)
    flag = 1
    s = 1
    t = 1
    while v:
        s = t
        t = v.pop(0)
        if t not in G[s]:
            flag = 0
            break
    ans += flag
print(ans)

Verdicts: Runtime Error

Accepted
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())
ls = [tuple(map(int, input().split())) for _ in range(m)]
neighborls = []
for i in range(1,n+1):
    neighbors = []
    for j in range(1, m+1):
        if (i,j) in ls or (j,i) in ls:
            neighbors.append(j)
    neighborls.append(neighbors)

ans = 0

def main():
    global ans
    visitedls = [1]
    ans = dfs(1, visitedls, ans)

    print(ans)
    
        
def dfs(a, visitedls, ans):
    global ans
    if len(visitedls) == n:
        ans += 1
    for i in range(1,n+1):
        if i not in visitedls and i in neighborls[a-1]:
            visitedls.append(i)
            ans = dfs(i, visitedls, ans)
            visitedls.remove(i)
    return ans


if __name__ == "__main__":
    main()

n,m = map(int, input().split())
ls = [tuple(map(int, input().split())) for _ in range(m)]
neighborls = []
for i in range(1,n+1):
    neighbors = []
    for j in range(1, m+1):
        if (i,j) in ls or (j,i) in ls:
            neighbors.append(j)
    neighborls.append(neighbors)

ans = 0

def main():
    visitedls = [1]
    ans = dfs(1, visitedls, ans)

    print(ans)
    
        
def dfs(a, visitedls, ans):
    if len(visitedls) == n:
        ans += 1
        return ans
    for i in range(1,n+1):
        if i not in visitedls and i in neighborls[a-1]:
            visitedls.append(i)
            ans = dfs(i, visitedls, ans)
            visitedls.remove(i)
    return ans


if __name__ == "__main__":
    main()

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

ans = 0

def dfs(n, visited):
    global ans
    visited.append(n)
    if len(visited) == N:
        ans += 1
    else:
        for i in l[n-1]:
            if i not in visited:
                dfs(i, visited)
    visited.remove(n)

l = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    l[a-1].append(b)
    l[b-1].append(a) 

dfs(1, [])
print(ans)


Verdicts: Runtime Error

Runtime Error

Accepted
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):
def dfs(i):
    if all(visited):
        global ans
        ans += 1
        return
    for j in range(N):
        if g[i][j] and not visited[j]:
            visited[j] = True
            dfs(j)
            visited[j] = False

N, M = map(int, input().split())
g = [[False] * N for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    g[a-1][b-1] = True
    g[b-1][a-1] = True

ans = 0
visited = [False] * N
visited[0] = True
dfs(0)

def dfs(i):
    if all(visited):
        global ans
        ans += 1
        return
    for j in range(N):
        if g[i][j] and not visited[j]:
            visited[j] = True
            dfs(j)
            visited[j] = False
    return

N, M = map(int, input().split())
g = [[False] * M for _ in range(M)]
for _ in range(M):
    a, b = map(int, input().split())
    g[a-1][b-1] = True
    g[b-1][a-1] = True

ans = 0
visited = [False] * N
visited[0] = True
dfs(0)

from copy import copy
N, M = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    G[b - 1].append(a - 1)
    G[a - 1].append(b - 1)

ans = 0
st = [[0, [False] * N]]
while len(st) > 0:
    _st = st.pop()
    v = _st[0]
    visited = copy(_st[1])
    if visited[v]:
        continue
    visited[v] = True
    adj_all_visit = True
    for adj in G[v]:
        if visited[adj]:
            continue
        st.append([adj, visited])
        adj_all_visit = False
    if adj_all_visit and all(visited):
        ans += 1
print(ans)


Verdicts: Wrong Answer

Runtime Error

Accepted
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())
adj_matrix = [[0] * n for _ in range(N)]

for i in range(m):
  a, b = map(int, input().split())
  adj_matrix[a-1][b-1] = 1
  adj_matrix[b-1][a-1] = 1
  
def dfs(v, used):
  if not False in used:
    return 1
  
  ans = 0
  for i in range(n):
    if not adj_matrix[v][i]:
      continue
    if used[i]:
      continue
    
    used[i] = True
    ans += dfs(i, used)
    used[i] = False
    
  return ans

used = [False] * n
used[0] = True

print(dfs(0, used))

N, M = map(int, input().split())
adj_matrix = [[0]* N for _ in range(N)]

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

def dfs(v, used):
    if not False in used:
        return 1
    
    ans = 0
    for i in range(N):
        if not adj_matrix[v][i]:
            continue
        if used[i]:
            continue
        
        used[i] = True
        ans += dfs(i, used)
        used[i] = False
    
    return ans

used = [False] * N
used[0] = True

print(dfs(0, used))

Verdicts: Runtime Error

Accepted
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):
from copy import deepcopy



def wfs(tree, root, node_num):
    lost_list = [root]

    def _wfs(tree, root, lost_list) -> int:
        if len(lost_list) == node_num:
            print(lost_list)
            return 1
        counter = 0
        for i in tree[root]:
            if i not in lost_list:
                tmp = deepcopy(lost_list)
                tmp.append(i)
                counter += _wfs(tree, i, tmp)
        return counter

    return _wfs(tree, 0, lost_list)


n, m = input().rstrip().split()
n, m = int(n), int(m)
v = [list() for i in range(n)]
for _ in range(m):
    line = [int(i) - 1 for i in input().rstrip().split()]
    v[line[0]].append(line[1])
    v[line[1]].append(line[0])

print(wfs(v, 0, n))

from copy import deepcopy

def wfs(tree, root, node_num):
    lost_list = [root]

    def _wfs(tree, root, lost_list) -> int:
        if len(lost_list) == node_num:
            return 1
        counter = 0
        for i in tree[root]:
            if i not in lost_list:
                tmp = deepcopy(lost_list)
                tmp.append(i)
                counter += _wfs(tree, i, tmp)
        return counter

    return _wfs(tree, 0, lost_list)


n, m = input().rstrip().split()
n, m = int(n), int(m)
v = [list() for i in range(n)]
for _ in range(m):
    line = [int(i) - 1 for i in input().rstrip().split()]
    v[line[0]].append(line[1])
    v[line[1]].append(line[0])

print(wfs(v, 0, n))

Verdicts: Wrong Answer

Accepted
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())
link = [[] for i in range(n)]
for _ in range(m):
    a,b = map(int, input().split())
    link[a-1].append(b-1)
    link[b-1].append(a-1)

used = [0 for i in range(n)]
ans = 0
print(link)
def dfs(now, prev):
    global ans

    if sum(used) == n:
        #print('+1')
        ans += 1

    for i in link[now]:
        #print(now,i,used)
        if i != now and used[i] == 0:
            used[i] = 1
            #print('a')
            dfs(i, now)
            #print('b')
            used[i] = 0
            #print('c')

used[0] = 1
dfs(0,-1)
print(ans)



import itertools
n,m = map(int,input().split())

a = [[] for i in range(n)]
for i in range(m):
    b = list(map(int,input().split()))
    a[b[0]-1].append(b[1]-1)
    a[b[1]-1].append(b[0]-1)

#print(a)

c = list(itertools.permutations(range(1, n)))
len_c = len(c)

#print(c)
ans = 0
for i in range(len_c):
    now = 0
    check = True
    for j in range(n - 1):
        if not c[i][j] in a[now]:
            check = False
        now = c[i][j]
    if check:
        ans += 1

print(ans)

Verdicts: Wrong Answer

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

def dfs(v, visited):
    global adjacency_list, ans
    # copy
    visited_copy = visited[:]
    print("v;%d" % v)
    print(visited)
    
    visited_copy[v] = True
    for a in adjacency_list[v]:
        
        if sum(visited_copy) == N:
            ans += 1
            continue
        
        if visited[a] == True:
            continue
        
        else:
        
            visited_copy[a] = True
            dfs(a, visited_copy)    
        
            visited_copy[a] = False

if __name__ == "__main__":
    # input
    N, M = map(int, input().split())
    
    adjacency_list = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        adjacency_list[a-1].append(b-1)
        adjacency_list[b-1].append(a-1)
	
    visited = [False] * N
    print(visited)
    ans = 0 
    dfs(0, visited)
    print(ans)


def dfs_mat(v):
    global adjacency_mat, ans, visited
    
    if sum(visited) == N:
        ans += 1
        return
    for i in range(N):
        if adjacency_mat[v][i]:
            
            if visited[i] == True:
                continue
            
            else:
            
                visited[i] = True
                dfs_mat(i)    
            
                visited[i] = False


if __name__ == "__main__":
    # input
    N, M = map(int, input().split())
    
    adjacency_mat = [[None]* N for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        adjacency_mat[a-1][b-1] = 1
        adjacency_mat[b-1][a-1] = 1
    
    visited = [False] * N
    visited[0] = True 
    ans = 0 
    dfs_mat(0)
    print(ans)




Verdicts: Wrong Answer

Accepted
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):
def dfs(g,v,depth):
    if seen[v]==True:return 0
    if depth==n:return 1
    seen[v] = True
    paths = 0
    for next_v in g[v]:
        paths += dfs(g,next_v,depth+1)
    seen[v] = False
    return paths
        
n,m = map(int,input().split())

g = [[]*(n+1) for _ in range(n+1)]

for _ in range(m):
    a,b = map(int,input().split())
    g[a].append(b)
    g[b].append(a)

seen = [False]*(n+1)
    
dfs(g,1,1)

def dfs(g,v,depth):
    if seen[v]==True:return 0
    if depth==n:return 1
    seen[v] = True
    paths = 0
    for next_v in g[v]:
        paths += dfs(g,next_v,depth+1)
    seen[v] = False
    return paths
        
n,m = map(int,input().split())

g = [[]*(n+1) for _ in range(n+1)]

for _ in range(m):
    a,b = map(int,input().split())
    g[a].append(b)
    g[b].append(a)

seen = [False]*(n+1)
    
print(dfs(g,1,1))

Verdicts: Wrong Answer

Accepted
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):
from itertools import permutations
n,m = map(int,input().split())
e = [tuple(sorted(map(int,input().split()))) for _ in range(m)]

ans = 1
for i in permutations(range(2, n+1), n-1):
  l = [1] + list(i)
  ans += sum(1 for j in zip(l, l[1:]) if tuple(sorted(j)) in e) == n-1

print(ans)

from itertools import permutations
n,m = map(int,input().split())
e = {tuple(sorted(map(int,input().split()))) for _ in range(m)}

ans = 1
for i in permutations(range(2, n+1), n-1):
  l = [1] + list(i)
  ans += sum(1 for j in zip(l, l[1:]) if tuple(sorted(j)) in e) == n-1

print(ans)

from itertools import permutations
n,m = map(int,input().split())
e = [tuple(sorted(map(int,input().split()))) for _ in range(m)]

ans = 0
for i in permutations(range(2, n+1), n-1):
  l = [1] + list(i)
  ans += sum(1 for j in zip(l, l[1:]) if tuple(sorted(j)) in e) == n-1

print(ans)

Verdicts: Wrong Answer

Wrong Answer

Accepted
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 itertools

n,m = map(int,input().split())
li = [[0 for _ in range(n)] for _ in range(n)]

for i in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    li[a][b] = 1
    li[b][a] = 1

num = [i for i in range(1,n)]
ans = 0

for v in itertools.permutations(num):
    print(v)
    if li[0][v[0]] == 0:
        continue
    for i in range(len(v)-1):
        if li[v[i]][v[i+1]] == 0:
            break
        elif i==len(v)-2:
            ans += 1
print(ans-1)






import itertools

n,m = map(int,input().split())
li = [[0 for _ in range(n)] for _ in range(n)]

for i in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    li[a][b] = 1
    li[b][a] = 1

num = [i for i in range(1,n)]
ans = 0


for v in itertools.permutations(num):
    bre = False
    if li[0][v[0]] == 0:
        continue
    for i in range(len(v)-1):
        if li[v[i]][v[i+1]] == 0:
            bre = True
            break
    if bre:
        continue
    else:
        ans += 1
print(ans)






Verdicts: Wrong Answer

Accepted
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 itertools
n,m=map(int,input().split())
p=[[False]*n for i in range(n)]

for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    p[a][b]=True
    p[b][a]=True
ans=0
for i in itertools.permutations(range(1,n),n-1):
    list=[0]+[i]
    if all(p[list[j]][list[j+1]]==True for j in range(n)):
        ans+=1
print(ans)   

import itertools
n,m=map(int,input().split())
p=[[False]*n for i in range(n)]

for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    p[a][b]=True
    p[b][a]=True
ans=0
for i in itertools.permutations(range(1,n),n-1):
    list=[0]+[k for k in i]
    if all(p[list[j]][list[j+1]]==True for j in range(n-1)):
        ans+=1
print(ans)   


Verdicts: Runtime Error

Accepted
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):
from itertools import permutations
N, M = map(int, input().split())
edge = []
for _ in range(M):
    a, b = map(int, input().split())
    edge.append(set((a, b)))

p = list(map(lambda x: [1] + list(x), permutations([i for i in range(2, N + 1)])))

ans = 0

for root in p:
    for i in range(len(root) - 1):
        if not set((root[i], root[i + 1])) in edge:
            break
    else:
        print(root)
        ans += 1

print(ans)


from itertools import permutations
N, M = map(int, input().split())
edge = []
for _ in range(M):
    a, b = map(int, input().split())
    edge.append(set((a, b)))

p = list(map(lambda x: [1] + list(x), permutations([i for i in range(2, N + 1)])))

ans = 0

for root in p:
    for i in range(len(root) - 1):
        if not set((root[i], root[i + 1])) in edge:
            break
    else:
        ans += 1

print(ans)


Verdicts: Wrong Answer

Accepted
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):
m, n = map(int, input().split())
edge = [[False for j in range(n)] for i in range(n)]
for _ in range(m):
	a, b = map(int, input().split())
	edge[a-1][b-1] = edge[b-1][a-1] = True
visited = [False for _ in range(n)]
ans = 0
def dfs(v):
	visited[v] = True
	if all(x==True for x in visited):
		global ans
		ans += 1
		return
	for i in range(0, n):
		if edge[v][i]==True and visited[i]==False:
			dfs(i)
			visited[i] = False
			return
dfs(0)
print(ans)

n, m = map(int, input().split())
edge = [[False for j in range(n)] for i in range(n)]
for _ in range(m):
	a, b = map(int, input().split())
	edge[a-1][b-1] = edge[b-1][a-1] = True
visited = [False for _ in range(n)]
ans = 0
def dfs(v):
	visited[v] = True
	if all(x==True for x in visited):
		global ans
		ans += 1
		return
	for i in range(0, n):
		if edge[v][i]==True and visited[i]==False:
			dfs(i)
			visited[i] = False
dfs(0)
print(ans)

Verdicts: Runtime Error

Accepted
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 itertools
n,m=map(int,input().split())
s=[set(map(int,input().split())) for _ in range(n)]

ans=0
x=[i for i in range(2,n+1)]
print(x)
cand=itertools.permutations(x)
print(cand)
for i in cand:
  crnt=1
  for nxt in i:
    if set([crnt,nxt]) in s:
      crnt=nxt
    else:
      break
  else:
    ans+=1
print(ans)

from itertools import permutations
n,m=map(int,input().split())
s=[set(map(int,input().split())) for _ in range(m)]

ans=0
x=[i for i in range(2,n+1)]
cand=permutations(x)
for i in cand:
  crnt=1
  for nxt in i:
    if set([crnt,nxt]) in s:
      crnt=nxt
    else:
      break
  else:
    ans+=1
print(ans)

Verdicts: Runtime Error

Accepted
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):
cnt = 0

def dfs(v, n, used, linked_list):
    global cnt
    if len(used) == n:
        cnt += 1
        return
    else:
        for next_v in linked_list[v]:
            if next_v not in used:
                used.append(next_v)
                dfs(next_v, n, used, linked_list)
                #used.remove(next_v)
        return

def main():
    global cnt
    n, m = map(int, input().split())
    linked_list = [[] for _ in range(n+1)]
    for i in range(m):
        a, b = map(int, input().split())
        linked_list[a].append(b)
        linked_list[b].append(a)
    used = [1]
    dfs(1, n, used, linked_list)
    print(cnt)

if __name__ == '__main__':
    main()
    


cnt = 0

def dfs(v, n, used, linked_list):
    global cnt
    if len(used) == n:
        cnt += 1
        return
    else:
        for next_v in linked_list[v]:
            if next_v not in used:
                used.append(next_v)
                dfs(next_v, n, used, linked_list)
                used.remove(next_v)
        return

def main():
    global cnt
    n, m = map(int, input().split())
    linked_list = [[] for _ in range(n+1)]
    for i in range(m):
        a, b = map(int, input().split())
        linked_list[a].append(b)
        linked_list[b].append(a)
    used = [1]
    dfs(1, n, used, linked_list)
    print(cnt)

if __name__ == '__main__':
    main()
    


Verdicts: Wrong Answer

Accepted
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_matrix = []


for n in range(N):
    path_matrix.append([False] * N)


for m in range(M):
    line = map(int, input().split())
    paths = [x - 1 for x in line]
    path_matrix[paths[0]][paths[1]] = True
    path_matrix[paths[1]][paths[0]] = True


visited = [False] * N



def dfs(now, depth):
    if visited[now]:
        return 0
    if depth == N - 1:
        return 1

    visited[now] = True
    total_paths = 0
    for i in range(0, N):
        if path_matrix[now][i]:
            total_paths += dfs(i, depth + 1)


    return total_paths

print(dfs(0, 0))


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

path_matrix = []


for n in range(N):
    path_matrix.append([False] * N)


for m in range(M):
    line = map(int, input().split())
    paths = [x - 1 for x in line]
    path_matrix[paths[0]][paths[1]] = True
    path_matrix[paths[1]][paths[0]] = True


visited = [False] * N



def dfs(now, depth):
    if visited[now]:
        return 0
    if depth == N - 1:
        return 1

    visited[now] = True
    total_paths = 0
    for i in range(0, N):
        if path_matrix[now][i]:
            total_paths += dfs(i, depth + 1)

    return total_paths

print(dfs(0, 0))


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

path_matrix = []


for n in range(N):
    path_matrix.append([False] * N)


for m in range(M):
    line = map(int, input().split())
    paths = [x - 1 for x in line]
    path_matrix[paths[0]][paths[1]] = True
    path_matrix[paths[1]][paths[0]] = True


visited = [False] * N



def dfs(now, depth):
    if visited[now]:
        return 0
    if depth == N - 1:
        return 1

    visited[now] = True
    total_paths = 0
    for i in range(0, N):
        if path_matrix[now][i]:
            total_paths += dfs(i, depth + 1)

    visited[now] = False

    return total_paths

print(dfs(0, 0))

Verdicts: Wrong Answer

Wrong Answer

Accepted
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(),aplit())

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

for _ in range(M):
	a,b = map(int,input(),split())
	path[a-1],append(b-1)
    path[b-1],append(a-1)
vis = [0 for i in range(N)]
cnt = 0

def dfs(now,path):
	global cnt
  	if depth == N: cnt+=1
	for new in path[now]:
    	if vis[new] == 0:
			vis[new] = 1
        	dfs(new,depth+1)
          	vis[new] = 0

vis[0] = 1
dfs(0,1)
print(cnt)

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

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

for _ in range(M):
	a,b = map(int,input().split())
	path[a-1].append(b-1)
	path[b-1].append(a-1)
vis = [0 for i in range(N)]
cnt = 0

def dfs(now,depth):
	global cnt
	if depth == N: cnt+=1
	for new in path[now]:
		if vis[new] == 0:
			vis[new] = 1
			dfs(new,depth+1)
			vis[new] = 0

vis[0] = 1
dfs(0,1)
print(cnt)


Verdicts: Runtime Error

Accepted
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())
m=[]
for i in range(M):
  m.append(list(map(int, input().split())))


import copy
def check(c):
  if len(c) != N-1:
    return False

  for k in range(2**len(c)):
    f=False
    cc=copy.deepcopy(c)
    for l in range(len(c)):
      if k>>l&1==1:
        tmp=cc[l][0]
        cc[l][0]=cc[l][1]
        cc[l][1]=tmp
    

    start_table = [0]*N
    end_table = [0]*N
    start = -1
    # end = -1
    # print(c)

    for l in cc:
      start_table[l[0]-1] += 1
      if start_table[l[0]-1] == 2:
        f=True
        break
    if f:
      continue
    
    
    for l in cc:
      end_table[l[1]-1] += 1
      if end_table[l[1]-1] == 2:
        f=True
        break
    if f:
      continue
    
    for i in range(len(cc)):
      if cc[i][0] == 1:
        start = i
      # if c[i][1]==N:
      #   end = i


    if start==-1:
      continue

    # if end == -1:
      # return False
      
    # print(cc)
    return True


n=0
for i in range(2**M):
  c=[]
  for j in range(M):
    if i >> j & 1==1:
      c.append(m[j])
  if check(c):
    n += 1



print(n)



import itertools

n, m = map(int, input().split())
graph = {i + 1 : set() for i in range(n)}
for i in range(m):
    a, b = map(int, input().split())
    graph[a] |= set([b])
    graph[b] |= set([a])
count = 0
node = [i + 2 for i in range(n - 1)]
for i in itertools.permutations(node):
    route = [1] + list(i)
    flag = True
    for j in range(n - 1):
        if route[j + 1] not in graph[route[j]]:
            flag = False
            break
    if flag == True:
        count += 1
print(count)

Verdicts: Wrong Answer

Accepted
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 queue
import copy
import sys
from astropy.io.fits.convenience import append
sys.setrecursionlimit(50000000) 
input=sys.stdin.readline


N, M = map(int, input().split())
l = []

for i in range(M):
    l.append(list(map(lambda x: int(x)-1 , input().split())))

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

for i in range(M):
    lis[l[i][0]].append(l[i][1])
    lis[l[i][1]].append(l[i][0])


def dfs():
    re=0
    q1 =[[0]*N]
    q2=[0]
    while len(q1) != 0:
         
        visited=q1.pop()
        v=q2.pop()
        visited[v]=1
        if all(visited[c]==1 for c in range(N)):
            re += 1
        elif len(lis[v]) != 0:
            for i in lis[v]:
                if visited[i] == 0:
                    hoge=copy.deepcopy(visited)                    
                    q1.append(hoge)
                    q2.append(i)
    return re

print(dfs())



import copy
import sys
sys.setrecursionlimit(50000000) 


N, M = map(int, input().split())
l = []

for i in range(M):
    l.append(list(map(lambda x: int(x)-1 , input().split())))

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

for i in range(M):
    lis[l[i][0]].append(l[i][1])
    lis[l[i][1]].append(l[i][0])

def dfs():
    re=0
    q1 =[[0]*N]
    q2=[0]
    while len(q1) != 0:
         
        visited=q1.pop()
        v=q2.pop()
        visited[v]=1
        if all(visited[c]==1 for c in range(N)):
            re += 1
        elif len(lis[v]) != 0:
            for i in lis[v]:
                if visited[i] == 0:
                    hoge=copy.deepcopy(visited)                    
                    q1.append(hoge)
                    q2.append(i)
    return re

print(dfs())


Verdicts: Runtime Error

Accepted
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())
q = []
for i in range(m):
    a, b = map(int, input().split())
    q.append({a, b})
cnt = 0
while cnt != 10000:
    a = q.pop()
    for j in q:
        if len(j & a) != 0:  
            j |= a
            count = 0
            break
        else:  
            q = [a] + q
    if count > len(q):
        break
    count += 1
    for i in q:
        tmp = list(i)
        if tmp == array:
            cnt += 1
print(cnt)


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

path_matrix = []


for n in range(N):
    path_matrix.append([False] * N)


for m in range(M):
    a,b = map(int, input().split())
    path_matrix[a-1][b-1] = True
    path_matrix[b-1][a-1] = True


visited = [False] * N 

def dfs(now,depth):
    if visited[now]:
        return 0
    if depth == N-1:
        return 1
    
    visited[now] = True
    total_path = 0
    for i in range(n):
        if path_matrix[now][i]:
            total_path += dfs(i,depth+1) 

    visited[now] = False

    return total_path

print(dfs(0,0))

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

path_matrix = []


for n in range(N):
    path_matrix.append([False] * N)


for m in range(M):
    a,b = map(int, input().split())
    path_matrix[a-1][b-1] = True
    path_matrix[b-1][a-1] = True


visited = [False] * N 
def dfs(now,depth):
    if visited[now]:
        return 0
    if depth == N-1:
        return 1
    
    visited[now] = True
    total_path = 0
    for i in range(N):
        if path_matrix[now][i]:
            total_path += dfs(i,depth+1)

    visited[now] = False

    return total_path


print(dfs(0,0))

Verdicts: Runtime Error

Wrong Answer

Accepted