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

G = {}
for m in range(M):
    k, v = list(map(int, input().split()))
    G.setdefault(k, []).append(v)
    G.setdefault(v, []).append(k)
    # G[k] = list(set(G[k]))
    # G[v] = list(set(G[v]))

count = 0
visited = []
visited.append(1)
history = []


def dfs(graph, start, visited=[]):
    global count
    if len(visited) == M:
        print(visited)
        if visited not in history:
            count += 1
            history.append(visited)
    # visited.append(start)
    for label in graph.get(start, []):
        if label not in visited:
            visited.append(label)
            dfs(graph, label, visited)
            visited = visited[0:-2]


dfs(G, 1, visited)
print(count)

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

G = {}
for m in range(M):
    k, v = list(map(int, input().split()))
    G.setdefault(k, []).append(v)
    G.setdefault(v, []).append(k)

count = 0
visited = []
visited.append(1)


def dfs(graph, start, visited=[]):
    global count
    if len(visited) == M:
        count += 1
    # visited.append(start)
    for label in graph.get(start, []):
        if label not in visited:
            visited.append(label)
            print(visited)
            visited = dfs(graph, label, visited)
            visited.pop(-1)
    return visited


dfs(G, 1, visited)
print(count)


N, M = map(int, input().split())
r = [[] * N for i in range(N)]
reached = [0] * N
reached[0] = 1
count = 0
 
def dfs(now):
    global count
    if all(reached):
        count += 1
    for next in r[now]:
        if reached[next] == 0:
            reached[next] = 1
            dfs(next)
            reached[next] = 0
 
for i in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    r[a].append(b)
    r[b].append(a)
 
dfs(0)
 
print(count)

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().split())

X=[[] for _ in range(n)]

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

print(X)

path=[i for i in range(2,n+1)]

visited=[1]+[0]*(n-1)

def dfs(v):
    if visited==[1]*n:
        return 1
    res=0
    for x in X[v]:
        if visited[x]==0:
            visited[x]=1
            print(visited)
            res+=dfs(x)
            visited[x]=0
    return res

print(dfs(0))

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

X=[[] for _ in range(n)]

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

print(X)

path=[i for i in range(2,n+1)]

visited=[1]+[0]*(n-1)

def dfs(v):
    if visited==[1]*n:
        return 1
    res=0
    for x in X[v]:
        if visited[x]==0:
            visited[x]=1
            res+=dfs(x)
            visited[x]=0
    return res

print(dfs(0))

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

X=[[] for _ in range(n)]

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


path=[i for i in range(2,n+1)]

visited=[1]+[0]*(n-1)

def dfs(v):
    if visited==[1]*n:
        return 1
    res=0
    for x in X[v]:
        if visited[x]==0:
            visited[x]=1
            res+=dfs(x)
            visited[x]=0
    return res

print(dfs(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().split())
lis = [0 for i in range(m)]
for i in range(m):
    lis[i] = list(map(int,input().split()))
    
seen = []
count = 0
visited = [0 for i in range(m)]
r = 0
def route(x=1):
    for i in range(m):
        if lis[i][0] == x and visited[i] == 0:
            visited[i] = 1
            r += 1
            route(lis[i][1])
            visited[i] = 0
            r -= 1
        elif lis[i][1] == x and visited[i] == 0:
            visited[i] = 1
            r += 1
            route(lis[i][0])
            visited[i] = 0
            r -= 1
        if r == n-1:
            global count
            count += 1
            return
        
            
        
route(1)
print(count)

n, m = map(int,input().split())
lis = [0 for i in range(m)]
for i in range(m):
    lis[i] = list(map(int,input().split()))
    
seen = []
count = 0
def route(x=1):
    for i in range(m):
        if lis[i][0] == x and visited[i] == 0:
            visited[i] = 1
            route(lis[i][1])
            visited[i] = 0
        elif lis[i][1] == x and visited[i] == 0:
            visited[i] = 1
            route(lis[i][0])
            visited[i] = 0
        r = 0
        for j in visited:
            r += j
        if r == n-1:
            global count
            count += 1
            return
        
            
        
route(1)
print(count)

n, m = map(int,input().split())
lis = [0 for i in range(m)]
for i in range(m):
    lis[i] = list(map(int,input().split()))
    
seen = []
count = 0
visited = [0 for i in range(n)]
def route(x=1):
    visited[x-1] = 1
    if [1]*n == visited:
        global count
        count +=1
        return
    for i in range(m):
        if lis[i][0] == x and visited[lis[i][1]-1] == 0:
            route(lis[i][1])
            visited[lis[i][1]-1] = 0
        elif lis[i][1] == x and visited[lis[i][0]-1] == 0:
            route(lis[i][0])
            visited[lis[i][0]-1] = 0
    return
            
        
route(1)
print(count)

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

def dfs(now,depth):
    if visited[now]==1:
        return 0
    elif depth==n-1:
        return 1
    else:
        visited[now]=1
        total=0
        for i in range(n):
            if paths[now][i]==1:
                total+=dfs(i,depth+1)
                print(total)
        visited[now]=0
        return total

print(dfs(0,0))

n,m=map(int,input().split())
paths=[]

for i in range(n):
    paths.append([0]*n)

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

def dfs(now,depth):
    if visited[now]==1:
        return 0
    elif depth==n-1:
        return 1
    else:
        visited[now]=1
        total=0
        for i in range(n):
            if paths[now][i]==1:
                total+=dfs(i,depth+1)
        visited[now]=0
        return total
print(dfs(0,0))

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 = list(map(int, input().split()))
paths = [list(map(int, input().split())) for _ in range(m)]

visited = [1]
rest = [i for i in range(2, n + 1)]
ans = 0

def dfs(num):
    if rest == []:
        print(visited)
        global ans
        ans += 1
    for i in range(m):
        if num in paths[i]:
            other = paths[i][1 - paths[i].index(num)]
            if other in rest:
                # print(other)
                visited.append(other)
                rest.remove(other)
                # print(visited, rest)
                dfs(other)
                visited.remove(other)
                rest.append(other)

dfs(1)
print(ans)

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

visited = [1]
rest = [i for i in range(2, n + 1)]
ans = 0

def dfs(num):
    if rest == []:
        # print(visited)
        global ans
        ans += 1
    for i in range(m):
        if num in paths[i]:
            other = paths[i][1 - paths[i].index(num)]
            if other in rest:
                # print(other)
                visited.append(other)
                rest.remove(other)
                # print(visited, rest)
                dfs(other)
                visited.remove(other)
                rest.append(other)

dfs(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):
n,m=map(int,input().split())
ab = []
for _ in range(n):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  ab.append({a,b})
import itertools

cnt = 0
for v in itertools.permutations(range(1,n)):
  l = 0
  ok = True
  for v2 in v:
    if {l,v2} not in ab:
      ok = False
      break
    l = v2
  if ok:
    print(v)
    cnt += 1
  
print(cnt)

n,m=map(int,input().split())
ab = []
for _ in range(m):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  ab.append({a,b})
import itertools

cnt = 0
for v in itertools.permutations(range(1,n)):
  l = 0
  ok = True
  for v2 in v:
    if {l,v2} not in ab:
      ok = False
      break
    l = v2
  if ok:
    #print(v)
    cnt += 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):
import itertools
N, M = map(int, input().split())

G = {k: set() for k in range(N+1)}
for _ in range(M):
    a, b = map(int, input().split())
    
    G[a].add(b)
    G[b].add(a)
print(G)

ans = 0
for p in itertools.permutations(range(2, N+1)):
    print(p)
    c = 1
    for n in p:
        if n not in G[c]:
            break
        c = n
    else:
        ans += 1

print(ans)


N, M = map(int, input().split())
G = {k: [] for k in range(N+1)}
for _ in range(N):
    a, b = map(int, input().split())
    
    G[a-1].append(b-1)
    G[b-1].append(a-1)

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


def dfs(v):
    if all(visited):
        ans += 1
        return
    for nv in G[i]:
        if visited[nv] is False:
            visited[nv] = True
            dfs(nv)
            visited[nv] = False
    return


ans = 0
dfs(0)
print(ans)


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

G = {k: [] for k in range(N)}  # 0-indexed
for _ in range(M):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)


def dfs(p, arrived):
    if arrived == 2**N-1:
        return 1

    ret = 0
    for n in G[p]:
        if (arrived >> n) & 1 == 0:
            ret += dfs(n, arrived+2**n)
    return ret


arrived = 1
print(dfs(0, arrived))


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())
edge=[n*[0]for _ in range(n)]
for i in range(m):
	a,b=map(int,input().split())
	a-=1
	b-=1
	edge[a][b]=edge[b][a]=1
from itertools import permutations
ans=0
for i in permutations([j for j in range(1,n)],n-1):
	f=True
	t=[0]+i
	for j in range(1,n):
		if edge[t[j-1]][t[j]]==0:f=False
	if f:ans+=1
print(ans)

n,m=map(int,input().split());a=[[],[]];ans=0
for i in range(m):aa,bb=map(int,input().split());a[0].append(aa);a[1].append(bb)
def d(n,nl,ml):
  if sorted(nl+[n])==[i+1for i in range(n)]:return 1
  if n in nl:return 0
  l=len(ml[0]);ans=0
  for i in range(l):
    c=[ml[0][:i]+ml[0][i+1:],ml[1][:i]+ml[1][i+1:]]
    if ml[0][i]==n:ans+=d(ml[1][i],nl+[n],c)
    if ml[1][i]==n:ans+=d(ml[0][i],nl+[n],c)
  return ans
for i in range(m):
  if a[0][i]==1:
    c=[a[0][:i]+a[0][i+1:],a[1][:i]+a[1][i+1:]]
    ans+=d(a[1][i],[1],c)
print(ans)

n,m=map(int,input().split())
edge=[n*[0]for _ in range(n)]
for i in range(m):
	a,b=map(int,input().split())
	a-=1
	b-=1
	edge[a][b]=edge[b][a]=1
from itertools import permutations
ans=0
for i in permutations([j for j in range(1,n)],n-1):
	f=True
	t=[0]+list(i)
	for j in range(1,n):
		if edge[t[j-1]][t[j]]==0:f=False
	if f:ans+=1
print(ans)

Verdicts: Runtime Error

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

    
    #g[a][] = b
    #g[a].append(b)
    #g[b].append(a)

#g[4].sort()
    
ans = 0

def dfs(x,check):
    #print(check,x)
    ans = 0
    if not False in check:
        print(ans)
        return 1
        #check[x] = 0
        #print(x)
    #print(check)
    for i in g[x]:
        if check[i] == True:
            continue
        #print(i,check)
        check[i] = True
        ans += dfs(i,check)
        check[i] = False
    
    return ans
    
check = [False] * (n+1)
check[0] = True
check[1] = True

print(dfs(1,check))



import bisect
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)

    
    #g[a][] = b
    #g[a].append(b)
    #g[b].append(a)

#g[4].sort()
    
ans = 0

def dfs(x,check):
    #print(check,x)
    ans = 0
    if not False in check:
        #print(ans)
        return 1
        #check[x] = 0
        #print(x)
    #print(check)
    for i in g[x]:
        if check[i] == True:
            continue
        #print(i,check)
        check[i] = True
        ans += dfs(i,check)
        check[i] = False
    
    return ans
    
check = [False] * (n+1)
check[0] = True
check[1] = True

print(dfs(1,check))



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())
Neighbor_list = [[] for _ in range(N)]
for _ in range(M):
    s, t = map(int, input().split())
    Neighbor_list[s-1].append(t-1)
    Neighbor_list[t-1].append(s-1)


def dfs(cur, path):
    if len(path) == N:
        return 1
    else:
        ret = 0
        for neighbor in Neighbor_list[cur]:
            if neighbor not in path:
                next_list = path[:]
                next_list.append(neighbor)
                ret += dfs(neighbor, next_list)
        return ret


print(dfs(0, []))




N, M = map(int, input().split())
Neighbor_list = [[] for _ in range(N)]
for _ in range(M):
    s, t = map(int, input().split())
    Neighbor_list[s-1].append(t-1)
    Neighbor_list[t-1].append(s-1)


def dfs(cur, path):
    if len(path) == N:
        return 1
    else:
        ret = 0
        for neighbor in Neighbor_list[cur]:
            if neighbor not in path:
                next_list = path[:]
                next_list.append(neighbor)
                ret += dfs(neighbor, next_list)
        return ret


print(dfs(0, [0]))


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 copy

N, M = [ int(x) for x in input().split()]

class Node:
    def __init__(self, id):
        self.id = id
        self.path = []
        self.passed = False
    def __str__(self):
        return "id: " + str(self.id) + " path: " + str(self.path) + " passed: " + str(self.passed)

nodes = []
for i in range(N):
    nodes.append(Node(i))

for i in range(M):
    from_id, to_id = [ int(x) - 1 for x in input().split()]
    nodes[from_id].path.append(to_id)
    nodes[to_id].path.append(from_id)

def if_all_passed(nodes_current):
    for node in nodes_current:
        if not node.passed:
            return False
    return True

def go_child(id_new, nodes_current):
    print(id_new, nodes_current[0])
    nodes_current[id_new].passed = True
    if if_all_passed(nodes_current):
        return 1

    count = 0
    for i in nodes[id_new].path:
        if not nodes_current[i].passed:
            count += go_child(i, copy.deepcopy(nodes_current))
    return count

count = go_child(0, nodes)
print(count)


import copy

N, M = [ int(x) for x in input().split() ]

class Node:
    def __init__(self, id):
        self.id = id
        self.path = []
    def __str__(self):
        return "id: " + str(self.id) + " path: " + str(self.path)

nodes = []
for i in range(N):
    nodes.append(Node(i))

for i in range(M):
    from_id, to_id = [ int(x) - 1 for x in input().split() ]
    nodes[from_id].path.append(to_id)
    nodes[to_id].path.append(from_id)

def if_all_passed(passed_nodes):
    if len(passed_nodes) == N:
        return True
    else:
        return False

def go_child(id_new, passed_nodes):
    passed_nodes.append(id_new)
    if if_all_passed(passed_nodes):
        return 1

    count = 0
    for i in nodes[id_new].path:
        if not i in passed_nodes:
            count += go_child(i, copy.deepcopy(passed_nodes))
    return count

count = go_child(0, [])
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):
def abc054c_one_stroke_path():
    import itertools
    n, m = map(int, input().split())
    e = [set() for _ in range(n + 1)]
    for _ in range(m):
        a, b = map(int, input().split())
        e[a].add(b)
        e[b].add(a)
    pattern = itertools.permutations(range(2, n + 1))
    cnt = 0
    for p in pattern:
        p_m = [1] + list(p)
        for i in range(n - 1):
            if p_m[i+1] not in e[p_m[i]]:
                break
        else:
            cnt += 1
    print(cnt)

def abc054c_one_stroke_path():
    import itertools
    n, m = map(int, input().split())
    e = [set() for _ in range(n + 1)]
    for _ in range(m):
        a, b = map(int, input().split())
        e[a].add(b)
        e[b].add(a)
    pattern = itertools.permutations(range(2, n + 1))
    cnt = 0
    for p in pattern:
        p_m = [1] + list(p)
        for i in range(n - 1):
            if p_m[i+1] not in e[p_m[i]]:
                break
        else:
            cnt += 1
    print(cnt)


abc054c_one_stroke_path()

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())
D = [[0]*n for i in range(n)]
for i in range(m):
	a,b = map(int,input().split())
	D[a-1][b-1] = 1
	D[b-1][a-1] = 1
print(D)

cnt = 0
for a in permutations(range(n)):
	print(a)
	if a[0] != 0:
		break
	tmp = 1
	for i in range(n-1):
		tmp = tmp * D[a[i]][a[i+1]]
	cnt += tmp
print(cnt)

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

d = [0]*n
d[0] = 1
cnt = 0

def dfs(x):
  global cnt
  if all(d):
    cnt += 1
    return
  for i in D[x]:
    if d[i] == 0:
      d[i] = 1
      dfs(i)
      d[i] = 0

dfs(0)
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):
import itertools as it

n, m = map(int, input().split())
a = list(list(map(int, input().split())) for _ in range(m))

print(a)


for i in range(len(a)):
    a.append([a[i][1],a[i][0]])
print(a)



lis  = list(it.permutations(range(2, n + 1)))
#print(lis)
for i in range(len(lis)):
    lis[i] = (1,) + lis[i]
#print(lis)


lis2 = []
for i in range(len(lis)):
    lis[i] = list(lis[i])
    lis2.append(lis[i])
print(lis2)


for i in range(len(lis2)):
    flag = 0
    for j in range(len(lis2[i]) - 1):
        for k in range(len(a)):
            if lis2[i][j : j + 2] == a[k]:
                flag += 1
                #print(lis[i][j : j + 2], a[k])
        #print(lis[i][j : j + 2])
print(flag)


import itertools as it

n, m = map(int, input().split())
a = list(list(map(int, input().split())) for _ in range(m))

#print(a)


for i in range(len(a)):
    a.append([a[i][1],a[i][0]])
#print(a)



lis  = list(it.permutations(range(2, n + 1)))
#print(lis)
for i in range(len(lis)):
    lis[i] = (1,) + lis[i]
#print(lis)


lis2 = []
for i in range(len(lis)):
    lis[i] = list(lis[i])
    lis2.append(lis[i])
#print(lis2)


#lis3 = []
ans = 0
for i in range(len(lis2)):
    check = True
    for j in range(len(lis2[i]) - 1):
        if lis2[i][j : j + 2] not in a:
            check = False
    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):
from copy import deepcopy as dcopy
def main():
    global count,N,M,edges,stack
    N, M = map(int, input().split())
    edges = [[0]*N for n in range(N)]
    for m in range(M):
        a,b = map(lambda x:int(x)-1,input().split())
        edges[a][b] = 1
        edges[b][a] = 1

    count = 0
    stack = [[[0], [0]]]
    while len(stack) != 0:
        tansaku = stack.pop()
        next_list = [n for n,v in enumerate(edges[tansaku[0][-1]]) if v == 1]
        search(tansaku, next_list)
    print(count)

def search(tansaku, next_list):
    global count, stack
    for node in next_list:
        tmp_tansaku = dcopy(tansaku)
        tmp_node = tmp_tansaku[0]
        houmonzumi = tmp_tansaku[1]
        if node in houmonzumi:
            pass
        else:
            houmonzumi.append(node)
            if len(houmonzumi) == N:
                count += 1
            else:
                tmp_node.append(node)
                stack.append([tmp_node, houmonzumi])


from copy import deepcopy as dcopy
def main():
    global count,N,M,edges,stack
    N, M = map(int, input().split())
    edges = [[0]*N for n in range(N)]
    for m in range(M):
        a,b = map(lambda x:int(x)-1,input().split())
        edges[a][b] = 1
        edges[b][a] = 1

    count = 0
    stack = [[[0], [0]]]
    while len(stack) != 0:
        tansaku = stack.pop()
        next_list = [n for n,v in enumerate(edges[tansaku[0][-1]]) if v == 1]
        search(tansaku, next_list)
    print(count)

def search(tansaku, next_list):
    global count, stack
    for node in next_list:
        tmp_tansaku = dcopy(tansaku)
        tmp_node = tmp_tansaku[0]
        houmonzumi = tmp_tansaku[1]
        if node in houmonzumi:
            pass
        else:
            houmonzumi.append(node)
            if len(houmonzumi) == N:
                count += 1
            else:
                tmp_node.append(node)
                stack.append([tmp_node, houmonzumi])

if __name__ == "__main__":# {{{
    try:
        import test
        test.test()
    except:
        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):
from sys import setrecursionlimit
setrecursionlimit(10 ** 10)
n, m = map(int, input().split())
P = [[] for i in range(m)]   #Pass
for i in range(m):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1  
    P[a].append(b)
    P[b].append(a)
#print(P)

c = 0   #cursol
R = [0 for i in range(m)]  #Record
tm = 1  #time

def all_search_dfs(c:int, tm:int, R:list):
    if R[c] == 0:
        R[c] = 1
        if  tm < n:
            return point_calculate(c, tm, R)
        elif tm == n:
            return 1
        else:
            return 0
    else:
        return 0

def point_calculate(c:int, tm:int, R:list):
    #print('c = ', c)
    p = 0
    #print('check = ', P[c])
    for i in range(len(P[c])):
        R2 = R[:]
        #print('before = ', R2)
        tmp = all_search_dfs(P[c][i], tm + 1, R2)
        #print('after = ', R2)
        #print('tmp = ', tmp)
        p += tmp
        #print('p = ', p)
    return p

print(all_search_dfs(c, tm, R))

from sys import setrecursionlimit
setrecursionlimit(4100000)
n, m = map(int, input().split())
P = [[] for i in range(n)]   #Pass
for i in range(m):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1  
    P[a].append(b)
    P[b].append(a)
#print(P)

c = 0   #cursol
R = [0 for i in range(n)]  #Record
tm = 1  #time

def all_search_dfs(c:int, tm:int, R:list):
    if R[c] == 0:
        R[c] = 1
        if  tm < n:
            return point_calculate(c, tm, R)
        elif tm == n:
            return 1
        else:
            return 0
    else:
        return 0

def point_calculate(c:int, tm:int, R:list):
    #print('c = ', c)
    p = 0
    #print('check = ', P[c])
    for i in range(len(P[c])):
        R2 = R[:]
        #print('before = ', R2)
        tmp = all_search_dfs(P[c][i], tm + 1, R2)
        #print('after = ', R2)
        #print('tmp = ', tmp)
        p += tmp
        #print('p = ', p)
    return p

print(all_search_dfs(c, tm, R))

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
import numpy as np
N, M = map(int, input().split(" "))
mat = [[0] * n for _ in range(n)]
for _ in range(M):
    v1, v2 = map(int, input().split(" "))
    mat[v1 - 1][v2 - 1] = mat[v2 - 1][v1 - 1] = 1

count = 0
for line in permutations(np.arange(N - 1) + 2):
    vtxs = [1] + list(line)
    for i in range(N - 1):
        v1, v2 = vtxs[i], vtxs[i + 1]
        if mat[v1 - 1][v2 - 1] == 0:
            break
    else:
        count += 1
print(count)

from itertools import permutations
import numpy as np
N, M = map(int, input().split(" "))
edges = []
for _ in range(M):
    edges += [list(map(int, input().split(" ")))]

count = 0
for line in permutations(np.arange(N - 1) + 2):
    vtxs = [1] + list(line)
    for i in range(N - 1):
        edge = sorted([vtxs[i], vtxs[i + 1]])
        if edge not in edges:
            break
    else:
        count += 1
print(count)

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 as it

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

for e in it.permutations(range(n)):
    count,a=0,0
    if e[0]!=0:
        break
    
    for i in range(len(e)-1):
        if [e[i]+1,e[i+1]+1] in ans:
            count=1
        else:
            count=0
            
    a+=count
    
print(a)

import itertools as it

n,m=map(int,input().split())
ans=[]
for i in range(n):
    a,b=map(int,input().split())
    ans.append([a,b])
    ans.append([b,a])
  
a=0
for e in it.permutations(range(n)):
    count=0
    if e[0]!=0:
        break
    
    for i in range(len(e)-1):
        if [e[i]+1,e[i+1]+1] in ans:
            count*=1
        else:
            count*=0
            break
            
    a+=count
    
print(a)

import itertools as it

n,m=map(int,input().split())
ans=[]
for i in range(m):
    a,b=map(int,input().split())
    ans.append([a,b])
    ans.append([b,a])
  
a=0
for e in it.permutations(range(n)):
    #print(e)
    count=1
    if e[0]!=0:
        break
    
    for i in range(n-1):
        if [e[i]+1,e[i+1]+1] in ans:
            count*=1
        else:
            count*=0
            break
            
    a+=count
    
print(a)

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


def main():
    N, M = map(int, input().split())
    node_lst = [x for x in range(N)]
    edge_lst = [list(map(int, input().split())) for _ in range(M)]
    ans = 0
    print(edge_lst)

    for route in itertools.permutations(node_lst):
        is_visited = [False] * N
        is_visited[0] = True
        if route[0] != 0:
            continue

        for i in range(N - 1):
            if [route[i] + 1, route[i + 1] + 1] in edge_lst and is_visited[route[i + 1]] == False:
                is_visited[route[i + 1]] = True
            if [route[i + 1] + 1, route[i] + 1] in edge_lst and is_visited[route[i + 1]] == False:
                is_visited[route[i + 1]] = True

        if is_visited == [True] * N:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()


import itertools


def main():
    N, M = map(int, input().split())
    node_lst = [x for x in range(N)]
    edge_lst = [list(map(int, input().split())) for _ in range(M)]
    ans = 0

    for route in itertools.permutations(node_lst):
        is_visited = [False] * N
        is_visited[0] = True
        if route[0] != 0:
            continue

        for i in range(N - 1):
            if [route[i] + 1, route[i + 1] + 1] in edge_lst and is_visited[route[i + 1]] == False:
                is_visited[route[i + 1]] = True
            if [route[i + 1] + 1, route[i] + 1] in edge_lst and is_visited[route[i + 1]] == False:
                is_visited[route[i + 1]] = True

        if is_visited == [True] * N:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()


Verdicts: Wrong Answer

Accepted