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):
input()

from collections import defaultdict
from collections import deque

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

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

q = deque([])
q.append(0)

ans = 0
def dfs(n, q):
  print (n, D[n], q)
  global ans
  q.append(n)
  if len(q) == N:
    ans += 1
  else:
    for b in D[n]:
      if b not in q:
        dfs(b, q)
        q.pop()

dfs(0, [])
print (ans)

from collections import defaultdict
from collections import deque

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

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

q = deque([])
q.append(0)

ans = 0
def dfs(n, q):
  global ans
  q.append(n)
  if len(q) == N:
    ans += 1
  else:
    for b in D[n]:
      if b not in q:
        dfs(b, q)
        q.pop()

dfs(0, [])
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 collections as c
n,m=map(int,input().split())
d=c.defaultdict(list)
for s in range(m):
  a,b=map(int,input().split())
  d[a].append(b)
print(d)
ans=0
movecount=0
def search(defaultdict,list):
  global movecount
  global ans
  movecount+=1
  if list==[]:
    if movecount==m:
      ans+=1
      movecount-=1
    else:
      movecount-=1
  for item in list:
 #   print(item,"i")
 
    search(defaultdict,defaultdict[item])
  return ans
print(search(d,d[1]))

from collections import *
n,m=map(int,input().split())

d=defaultdict(list)

for s in m*[0]:
    a,b=map(int,input().split())
    d[a].append(b)
    d[b].append(a)

print(d)



def DFS_dict(point,TFlist):
#    print(TFlist)
#    print(d[point])
    if not False in TFlist:
        return 1
    ans=0
    for i in d[point]:
        if TFlist[i-1]:
            continue  
        TFlist[i-1]=True 
        ans+=DFS_dict(i,TFlist)
        TFlist[i-1]=False
    return ans

TFlist=[True]+[False]*(n-1)
print(DFS_dict(1,TFlist))

from collections import *
n,m=map(int,input().split())
d=defaultdict(list)
for s in m*[0]:
    a,b=map(int,input().split())
    d[a].append(b)
    d[b].append(a)
def DFS_dict(point,TFlist):
    if all(TFlist):
        return 1
    ans=0
    for i in d[point]:
        if TFlist[i-1]:
            continue
        TFlist[i-1]=True
        ans+=DFS_dict(i,TFlist)
        TFlist[i-1]=False
    return ans
TFlist=[True]+[False]*(n-1)
print(DFS_dict(1,TFlist))

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):
# -*- coding: utf-8 -*-
N,M = map(int, input().split())
G = [[] for j in range(N)]

for i in range(M):
    a,b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
print(G)
visited = [False]*N
visited[0] = True

def DFS(v,visited):
    
    if all(visited):
        return 1
    ans = 0
    for i in G[v]:
        print('i',i)
        if visited[i]:
            continue
        visited[i] = True
        ans += DFS(i,visited)
        visited[i] = False
    return ans

print(DFS(0,visited))


# -*- coding: utf-8 -*-
N,M = map(int, input().split())
G = [[] for j in range(N)]

for i in range(M):
    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,visited):
    
    if all(visited):
        return 1
    ans = 0
    for i in G[v]:
        if visited[i]:
            continue
        visited[i] = True
        ans += DFS(i,visited)
        visited[i] = False
    return ans

print(DFS(0,visited))


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 sys
sys.setrecursionlimit(10 ** 6)
n,m=map(int,input().split())
g=[[]for i in range(n)]; ans=0
for i in range(m):
  a,b=map(int,input().split())
  a-=1; b-=1
  g[a].append(b)
  g[b].append(a)
# print(g)
def dfs(x,visited):
  global ans
  # print(x,visited)
  for p in g[x]:
    if visited[p]==0:
      visited[p]=1
      if visited.count(1)==n:
        ans+=1
        # print(ans)
        return
      dfs(p,visited)
      visited[p]=0
v=[0]*n
v[0]=1
dfs(0,v)
print(ans)

import sys
sys.setrecursionlimit(10 ** 6)
n,m=map(int,input().split())
g=[[]for i in range(n)]; ans=0
for i in range(m):
  a,b=map(int,input().split())
  a-=1; b-=1
  g[a].append(b)
  g[b].append(a)
# print(g)
def dfs(x,visited):
  global ans
  # print(x,visited)
  for p in g[x]:
    if visited[p]==0:
      visited[p]=1
      if visited.count(1)==n:
        ans+=1
        # print(ans)
      else: 
        dfs(p,visited)
      visited[p]=0
v=[0]*n
v[0]=1
dfs(0,v)
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 i in range(m):
    ab.append(list(map(int,input().split())))

ans=0
def dfs(start,finish):
    global ans
    finish.add(start)
   # print(finish)
    if len(finish)==n:
        ans+=1
        
    for i in adlist[start-1]:
        if i not in finish:
 #           print(i)
            dfs(i,finish)

adlist=[]
for h in range(n):    
    adlist.append([])
for j in range(m):
    x=ab[j][0]
    y=ab[j][1]
    adlist[x-1].append(y)
    adlist[y-1].append(x)
finish=set()
#print(adlist)
dfs(1,finish)
print(ans)

import copy
n,m=map(int,input().split())
ab=[]
for i in range(m):
    ab.append(list(map(int,input().split())))

ans=0
def dfs(start,finish):
    global ans
   # print(finish)
    if len(finish)==n:
        ans+=1
    else:
        for i in adlist[start-1]:
            if i not in finish:
                #print(i)
                #print(adlist)
                #print(finish,1)
                finish_1 = set([i]) | finish
                #print(finish_1,2)
                dfs(i,finish_1)

adlist=[]
for h in range(n):    
    adlist.append([])
for j in range(m):
    x=ab[j][0]
    y=ab[j][1]
    adlist[x-1].append(y)
    adlist[y-1].append(x)
finish=set()
finish.add(1)
#print(adlist)
dfs(1,finish)
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())
road = [[0] * n for i in range(n)]

graph = [[] for i in range(n)]
for j in range(m):
    x, y = map(int, input().split())
    road[x - 1][y - 1] += 1
    road[y - 1][x - 1] += 1
    graph[x-1].append(y-1)
    graph[y-1].append(x-1)
#print(road)
#print(graph)

count = 0

for can in itertools.permutations(range(n)):
    if can[0] != 0:
        break
#    print(can)
    plus = 1
    for k in range(n-1):
#        print(road[can[k]][can[k + 1]])
        plus *= road[can[k]][can[k + 1]]
    count += plus


def dfs(node, prev, visited):
    visited.append(node)
    if len(visited) == n:
        return 1

    res = 0
    for edge in graph[node]:
        if edge == prev:
            continue
        if edge in visited:
            continue
        res += dfs(edge, prev, visited)

    return res

dfs = dfs(0, -1, [])

if count == dfs:
    print(dfs)


import itertools

n, m = map(int, input().split())
road = [[0] * n for i in range(n)]

graph = [[] for i in range(n)]
for j in range(m):
    x, y = map(int, input().split())
    road[x - 1][y - 1] += 1
    road[y - 1][x - 1] += 1
    graph[x - 1].append(y - 1)
    graph[y - 1].append(x - 1)
# print(road)
# print(graph)

count = 0

for can in itertools.permutations(range(n)):
    if can[0] != 0:
        break
    # print(can)
    plus = 1
    for k in range(n - 1):
        # print(road[can[k]][can[k + 1]])
        plus *= road[can[k]][can[k + 1]]
    count += plus


def dfs(node, prev, visited):
    visited.append(node)
    if len(visited) == n:
        return 1

    res = 0
    for edge in graph[node]:
        if edge == prev:
            continue
        if edge in visited:
            continue
        res += dfs(edge, prev, visited[:])

    return res


dfs = dfs(0, -1, [])

if count == dfs:
    print(dfs)


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())
graph = [[0]*(n) for i in range(n)]

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

print(graph)
visited = [True] + [False]*(n-1)
ans = 0


def dfs(x):
    global ans
    global visited
    
    if all(visited):
        ans += 1
        return
    
        
    for j in [j for j,v2 in enumerate(graph[x]) if v2 == 1 and not visited[j]]:
        visited[j] = True
        dfs(j)
        visited[j] = False

dfs(0)
print(ans)

n,m = map(int,input().split())
graph = [[0]*(n) for i in range(n)]

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


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


def dfs(x):
    global ans
    global visited
    
    if all(visited):
        ans += 1
        return
    
        
    for j in [j for j,v2 in enumerate(graph[x]) if v2 == 1 and not visited[j]]:
        visited[j] = True
        dfs(j)
        visited[j] = False

dfs(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):
N,M=map(int,input().split())
tbl=[[0]*(N+1) for _ in range(N+1)]
for i in range(M):
  a,b=map(int,input().split())
  tbl[a][b]=1
  tbl[b][a]=1            
def dfs(s,visited):
  if len(visited)==N:
    return 1
  
  ans=0
  for i in range(1,N+1):
    if i==s: continue     
    if tbl[s][i]==1 and (i not in visited):
      visited.append(i)
      ans+=dfs(i,visited)
      visited.pop()　　　　　
  return ans 

answer=dfs(1,[1,])
print(answer)
      

N,M=map(int,input().split())
tbl=[[0]*(N+1) for _ in range(N+1)]
for i in range(M):
  a,b=map(int,input().split())
  tbl[a][b]=1
  tbl[b][a]=1            
def dfs(s,visited):
  if len(visited)==N:
    return 1
  
  ans=0
  for i in range(1,N+1):
    if i==s: continue     
    if tbl[s][i]==1 and (i not in visited):
      visited.append(i)
      ans+=dfs(i,visited)
      visited.pop() 
  return ans 

answer=dfs(1,[1,])
print(answer)
      

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

for i in itertools.permutations(range(n),n):
    if i[0]==0:
        for j in range(n):
            if j==n-1:
                ans+=1
                break
            if not path[i[j]][i[j]+1]:
                break
print(ans)

def dfs(a,count,seen):
    nseen=seen[:]
    ans=0
    nseen[a] = 1;
    if count==n-1:
        return 1
    else:
        for i in g[a]:
            if not seen[i]:
                ans+=dfs(i,count+1,nseen)
        return ans
n,m=map(int,input().split())
g=[[]*n for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
seen=[0]*n
print(dfs(0,0,seen))


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):
def dfs(i):
  global count
  global seen
  global G

  print(seen)
  end = True
  for n in range(N):
    if seen[n] == 0 and n != i:
      end = False

  if (end):
    count += 1
    return

  seen[i] = 1
  for g in G:
    if g[0] == i:
      if seen[g[1]] == 1:
        continue
      dfs(g[1])
  
    if g[1] == i:
      if seen[g[0]] == 1:
        continue
      dfs(g[0])

  seen[i] == 0

N, M = map(int, input().split())
li = [list(map(int, input().split())) for n in range(M)]

G = []

for i in li:
  G.append([i[0]-1, i[1]-1])

count = 0
seen = [0] * N
dfs(0)

print(count)

def dfs(i):
  global count
  global seen
  global G

  end = True
  for n in range(N):
    if seen[n] == 0 and n != i:
      end = False

  if (end):
    count += 1
    return

  seen[i] = 1
  for g in G:
    if g[0] == i:
      if seen[g[1]] == 1:
        continue
      dfs(g[1])
  
    if g[1] == i:
      if seen[g[0]] == 1:
        continue
      dfs(g[0])

  seen[i] = 0

N, M = map(int, input().split())
li = [list(map(int, input().split())) for n in range(M)]

G = []

for i in li:
  G.append([i[0]-1, i[1]-1])

count = 0
seen = [0] * N
dfs(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):
n,m=list(map(int,input().split()))

import sys
sys.setrecursionlimit(10**7)


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

  


def dfs(v,visited):
  ans=0
  
  
  visited[v-1]=1
  print(visited)
  
  if visited==check:
    visited[v-1]=0
    return 1
  
  
  for i in range(n):
    
    if visited[i]==0 and es[v-1][i]==1:
      ans=ans+dfs(i+1,visited)
  
  visited[v-1]=0
   
  return ans





visited=[0 for i in range(n)]
check=[1 for i in range(n)]
print(dfs(1,visited))






      

  

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

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


import sys
sys.setrecursionlimit(10**7)




visited=[0 for i in range(n)]
check=[1 for i in range(n)]

def dfs(v,visited):
  
  ans=0
  
  visited[v-1]=1

  if visited==check:
    visited[v-1]=0
    return 1
  
  for i in range(n):
    
    if es[v-1][i]==1 and visited[i]==0:
        ans+=dfs(i+1,visited)
  
  visited[v-1]=0
  return ans

print(dfs(1,visited))


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):
# -*- coding: utf-8 -*-
import numpy as np

n,m = map(int, input().split())
graph = [[0 for i in range(n)] for j in range(n)]
graph = np.array(graph)

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

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

def DFS(v,used):
    if all(used):
        return 1
    ans = 0
    for i in graph(v):
        if used[i]:
            continue
        used[i] = True
        ans += DFS(i,used)
        used[i] = False
    return ans
  
print(DFS(0,used))

# -*- coding: utf-8 -*-
import numpy as np

n,m = map(int, input().split())
graph = [[] for j in range(n)]
graph = np.array(graph)

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

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

def DFS(v,used):
    if all(used):
        return 1
    ans = 0
    for i in graph(v):
        if used[i]:
            continue
        used[i] = True
        ans += DFS(i,used)
        used[i] = False
    return ans
  
print(DFS(0,used))

# -*- coding: utf-8 -*-
n,m = map(int, input().split())
graph = [[] for j in range(n)]

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

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

def DFS(v,used):
    if all(used):
        return 1
    ans = 0
    for i in graph[v]:
        if used[i]:
            continue
        used[i] = True
        ans += DFS(i,used)
        used[i] = False
    return ans
  
print(DFS(0,used))

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 sys
sys.setrecursionlimit(10**20)

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

Map = [[] for _ in range(M)]
reached = [False]*N

for _ in range(M):
    aa, bb = map(int, input().split())
    Map[aa-1].append(bb-1)
    Map[bb-1].append(aa-1)

cnt = 0

def DFS(x):
    global cnt
    reached[x] = True

    if all(reached):
        cnt += 1

    for i in range(N):
        if reached[i]:
            continue

        if i in Map[x]:
            DFS(i)

    reached[x] = False
    return

DFS(0)
print(cnt)


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

Map = [[] for _ in range(N)]
reached = [False]*N

for _ in range(M):
    aa, bb = map(int, input().split())
    Map[aa-1].append(bb-1)
    Map[bb-1].append(aa-1)

cnt = 0

def DFS(x):
    global cnt
    global reached

    reached[x] = True

    if all(reached):
        cnt += 1
        reached[x] = False

        return

    for i in Map[x]:
        if reached[i]:
            continue

        else:
            DFS(i)

    reached[x] = False


DFS(0)
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 sys
sys.setrecursionlimit(1000000)

N, M = map(int, input().split())
edge = [[] for _ in range(N + 1)]
ab = [list(map(int, input().split())) for _ in range(M)]
for i in range(M):
    a, b = ab[i][0], ab[i][1]
    edge[a].append(b)
    edge[b].append(a)


def f(now, v):
    v = v & (1 << now)
    for to in edge[now]:
        if v >> to == 0:
            f(to, v)
    if v == int('0b11111111', 0):
        ans += 1

ans = 0
f(1, 1)

print(ans)


import sys
sys.setrecursionlimit(1000000)

N, M = map(int, input().split())
edge = [[] for _ in range(N + 1)]
ab = [list(map(int, input().split())) for _ in range(M)]
for i in range(M):
    a, b = ab[i][0] - 1, ab[i][1] - 1
    edge[a].append(b)
    edge[b].append(a)

ans = 0

def f(now, v):
    global ans
    v |= (1 << now)
    for to in edge[now]:
        if not (v & (1<<to)):
            f(to, v)
    if bin(v).count("1") == N:
        ans += 1

f(0, 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):
n,m = map(int,input())
path = [map(int,input()) for x in range(m)]

table = [[] for x in range(n)]
for x in path:
    table[int(x[0])-1].append(int(x[1])-1)
    table[int(x[1])-1].append(int(x[0])-1)
    
import itertools
count = 0
for z in itertools.permutations(range(0,n)):
    if z[0] == 0:
        print(z)
        for y in range(len(z)-1):
            if z[y+1] in table[z[y]]:
                continue
            else:
                count -= 1
                break
        count += 1

n,m = map(int,input().split())
path = [input().split() for x in range(m)]

table = [[] for x in range(n)]
for x in path:
    table[int(x[0])-1].append(int(x[1])-1)
    table[int(x[1])-1].append(int(x[0])-1)
    
import itertools
count = 0
for z in itertools.permutations(range(0,n)):
    if z[0] == 0:
        for y in range(len(z)-1):
            if z[y+1] in table[z[y]]:
                continue
            else:
                count -= 1
                break
        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):
N,M = map(int,input().split())
edge_list = [list() for i in range(N)]
for i in range(M):
        a,b = map(int,input().split())
        edge_list[a-1].append(b-1)
        edge_list[b-1].append(a-1)
done = [0] * n
chk = 0
def dfs(s,done):
    done = done[:]
    global chk
    done[s] = True 
    if all(done):
        chk += 1
    for i in edges[u]:
        if not done[i]:
            dfs(i.done)
    return 0
dfs(0,done)
print(chk)

N,M = map(int,input().split())
edge_list = [list() for i in range(N)]
for i in range(M):
        a,b = map(int,input().split())
        edge_list[a-1].append(b-1)
        edge_list[b-1].append(a-1)
done = [0] * N
chk = 0
def dfs(s,done):
    done = done[:]
    global chk
    done[s] = True
    if all(done):
        chk += 1
    for i in edge_list[s]:
        if not done[i]:
            dfs(i,done)
    return 0
dfs(0,done)
print(chk)

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

ans=0

for v in itertools.permutations(li):
  pas=0
  ch=0
  st=1
  for x in range(n-1):
    if v[x]-1 not in rin[st-1]:
      ch+=1
      break
    else:
      st=v[x]
  if ch==0:
    ans+=1
    
print(ans)

import itertools

n,m=map(int,input().split())
rin=[[]for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  rin[a-1].append(b-1)
  rin[b-1].append(a-1)
  
li=[ i for i in range(2,n+1)]

ans=0

for v in itertools.permutations(li):
  pas=0
  ch=0
  st=1
  for x in range(n-1):
    if v[x]-1 not in rin[st-1]:
      ch+=1
      break
    else:
      st=v[x]
  if ch==0:
    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 sys
import itertools
n,m=map(int,input().split())
ab=[]
for _ in range(m):
    ab.append(list(map(int,input().split())))

lis=[i for i in range(1,n+1)]
per_lis = itertools.permutations(lis) 

ans=0
for one_case in per_lis:
    if one_case[0]==1:
        tmp=0
        for j in range(n-1):
            for num in ab:
                if one_case[j]==num[0] and one_case[j+1]==num[1]:
                    tmp+=1
                    break        
        if tmp==n-1:
            ans+=1

print(ans)

import sys
import itertools
n,m=map(int,input().split())
ab=[]
for _ in range(m):
    ab.append(list(map(int,input().split())))

lis=list(range(1,n+1))
per_lis =[i for i in list(itertools.permutations(lis)) if i[0]==1]

ans=0

for one_case in per_lis:
    tmp=0
    for j in range(n-1):
        for num in ab:
            if one_case[j]==num[0] and one_case[j+1]==num[1]:
                tmp+=1
            elif one_case[j]==num[1] and one_case[j+1]==num[0]:
                tmp+=1
                    

        if tmp==n-1:
            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):
n, m = [int(x) for x in input().split(' ')]

edges = set([tuple(input().split(' ')) for _ in range(n)])
edges.update([(x[1], x[0]) for x in list(edges)])


def dfs(node, history):
    ans = 0
    if len(history) == n - 1:
        print(history)
        return 1

    nextnodes = [
        x[1] for x in edges if x[1] not in history and x[0] == node and x[1] != node
    ]
    history.add(node)
    for next in nextnodes:
        ans += dfs(next, history)
    history.remove(node)
    return ans


print(dfs('1', set()))


n, m = [int(x) for x in input().split(' ')]
 
edges = set([tuple(input().split(' ')) for _ in range(m)])
edges.update([(x[1], x[0]) for x in list(edges)])
 
 
def dfs(node, history):
    ans = 0
    if len(history) == n - 1:
        return 1
 
    nextnodes = [
        x[1] for x in edges if x[1] not in history and x[0] == node and x[1] != node
    ]
    history.add(node)
    for next in nextnodes:
        ans += dfs(next, history)
    history.remove(node)
    return ans
 
 
print(dfs('1', set()))

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())
g=[[] for i in range(n)]
for _ in range(m):
  u,v=map(int,input().split())
  g[u-1].append(v-1)
  g[v-1].append(u-1)
ans=0
for v in permutations([int(i) for i in range(n)],n):
  for i in range(n-1):
    if not v[i+1] in g[v[i]]:
      break
  else:
    ans+=1
print(ans)

from itertools import permutations
n,m=map(int,input().split())
g=[[] for i in range(n)]
for _ in range(m):
  u,v=map(int,input().split())
  g[u-1].append(v-1)
  g[v-1].append(u-1)
ans=0
for v in permutations([int(i) for i in range(n)],n):
  if v[0]!=0:
    continue
  for i in range(n-1):
    if not v[i+1] in g[v[i]]:
      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):
import sys
sys.setrecursionlimit(1000000)

N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
for j in ab:
    if j[::-1] not in ab:
        ab.append(j[::-1])

ans = 0

#idx = [_ for _ in ab if _[0] == 1]
#idx = (ab.index(idx), 0)

searched = [0] * N
searched[0] = 1
length = 0

def dfs(n):
    
    global ans, length
    if length > N - 1:
        return
    if sum(searched) == N:
        ans += 1
        return
    idx = [_ for _ in ab if _[0] == n]
    for idx in idx:
        id1, _ = (ab.index(idx), 0)
        next = ab[id1][1]
        searched[next - 1] = 1
        length += 1
    
        dfs(next)

dfs(1)
print(ans)

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



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

ans = 0
visited = [0] * N

def dfs(now=0):
    global visited, ans
    visited[now] = 1
    if all(visited):
        ans += 1
        # visited = [0] * N
    else:
        cand = nei_L[now]
        for c in cand:
            if not visited[c]:
                dfs(c)
    visited[now] = 0

dfs()
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())
edges = {i:[] for i in range(1,M+1)}
for i in range(M):
    a,b = map(int,input().split())
    edges[a].append(b)
    edges[b].append(a)


def dfs(list):
    
    if len(list) == N:
        return 1
    else:
        x = list[-1]
        
        
        next = [n for n in edges[x] if n not in list]
        
        if len(next) == 0:
          return 0

        total = 0
        
        for n in next:
          total += dfs(list + [n])

        return total

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



edges = {i:[] for i in range(1,N+1)}
for i in range(M):
  a,b = [int(a) for a in input().split()]
  edges[a].append(b)
  edges[b].append(a)



def dfs(list):
    
  if len(list) == N:
    return 1
  else:
    a = list[-1]
    
    
    next = [n for n in edges[a] if n not in list]
    
    if len(next) == 0:
      return 0

    total = 0
    
    for n in next:
      total += dfs(list + [n])

    return total


ans = dfs([1])

print(ans)


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



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



def dfs(list):
    
  if len(list) == N:
    return 1
  else:
    a = list[-1]
    
    
    next = [n for n in edges[a] if n not in list]
    
    if len(next) == 0:
      return 0

    total = 0
    
    for n in next:
      total += dfs(list + [n])

    return total


ans = dfs([1])

print(ans)


Verdicts: Runtime Error

Runtime Error

Accepted