Problem:


Score : 300 points

Problem Statement

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

Constraints

2≦N≦8 

0≦M≦N(N-1)/2 

1≦a_i<b_i≦N 

The given graph contains neither self-loops nor double edges.

Input

The input is given from Standard Input in the following format:

N M  
a_1 b_1  
a_2 b_2
:  
a_M b_M  

Output

Print the number of the different paths that start from vertex 1 and visit all the vertices exactly once.

Sample Input 1

3 3
1 2
1 3
2 3

Sample Output 1

2

The given graph is shown in the following figure:

The following two paths satisfy the condition:

Sample Input 2

7 7
1 3
2 7
3 4
4 5
4 6
5 6
6 7

Sample Output 2

1

This test case is the same as the one described in the problem statement.



Sample input:
3 3
1 2
1 3
2 3


Sample output:
2

Submission status: Accepted

Solution code:
import itertools
n, m = map(int,input().split())
edges = {tuple(sorted(map(int,input().split()))) for i in range(m)}
#print(edges)
ans = 0
a = 0
for i in itertools.permutations(range(2, n+1), n-1):
  l = [1] + list(i)
  #print(l, l[1:])
  ans += sum(1 for edge in zip(l,l[1:]) if tuple(sorted(edge)) in edges) == n-1
  #print(sum(1 for edge in zip(l,l[1:]) if tuple(sorted(edge)) in edges) == n-1)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return [list(map(int, input().split())) for _ in range(n)]

def main():
    n,m=inpm()
    g=[[] for _ in range(n)]
    for _ in range(m):
        a,b=inpm()
        g[a-1].append(b-1)
        g[b-1].append(a-1)
    ans = 0
    for root in permutations(range(1,n)):
        if root[0] not in g[0]:
            continue
        key=0
        for i in range(n-2):
            if root[i] not in g[root[i+1]]:
                key=1
        if key==0:
            ans+=1
    print(ans)
        

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 深さ優先探索
def dfs(V, closed): # V:探索頂点, closed:探索済み頂点リスト
 
    # 全頂点を探索したとき
    if not False in closed:
        return 1
    
    answer = 0
    for i in range(N):
        if not graph[V][i]:
            continue
        if closed[i]:
            continue
 
        # 頂点iを探索済みにする
        closed[i] = True
        answer += dfs(i,closed)
 
        # 最深まで探索したとき
        closed[i] = False
    
    return answer
 
N,M = map(int,input().split())
graph = [[False for i in range(N)] for j in range(N)]
 
for i in range(M):
    a,b = map(int,input().split())
    graph[a-1][b-1] = graph[b-1][a-1] = True
 
closed_list = [False]*N
closed_list[0] = True
 
print(dfs(0,closed_list))

Submission status: Accepted

Solution code:
#C
import itertools
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for i in range(M)]

path = [(i+1) for i in range(N)]
p_list = list(itertools.permutations(path,N))

ans = 0
for pl in p_list:
    if pl[0] == 1:
        flag = 0
        for i in range(N-1):
            ab1 = [pl[i],pl[i+1]]
            ab2 = [pl[i+1],pl[i]]
            if ab1 in AB or ab2 in AB:
                pass
            else:
                flag = 1
                break
        if flag == 0:
            ans+=1
            
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.buffer.readline
N,M = map(int,input().split())
g = defaultdict(list)

for i in [0]*M:
    a,b = (map(int,input().split()))
    g[a].append(b)
    g[b].append(a)

f = [False]*N

ans = 0
def rec(s,f_):
    global ans
    f_[s-1] = True
    if sum(f_) == N:
        ans += 1
        return
    for t in g[s]:
        if not f_[t-1]:
            rec(t,f_[:])
    return 
rec(1,f[:])
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
G=[[0]*n for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    G[a-1][b-1]=G[b-1][a-1]=1
V=[0]*n
c=0
def dfs(v):
    global c
    if sum(V)==n:
        c+=1
        return
    for v2 in range(n):
        if G[v][v2]==1 and V[v2]==0:
            V[v2]=1
            dfs(v2)
            V[v2]=0
    return
V[0]=1
dfs(0)
print(c)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
nexts=[None for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  if nexts[a]==None:
    nexts[a]=[b]
  elif b not in nexts[a]:
    nexts[a].append(b)
  if nexts[b]==None:
    nexts[b]=[a]
  elif a not in nexts[b]:
    nexts[b].append(a)

ans=0
stack=[]
stack.append([0,[]])
while stack:
  node=stack.pop()
  v=node[0]
  seen=node[1][:]
  seen.append(v)
  if len(seen)==n:
    ans+=1
    continue
  childs=nexts[v]
  if childs:
    for child in (set(childs)-set(seen)):
      stack.append([child,seen])
  
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
import numpy as np
N, M = map(int, input().split(" "))#N頂点M辺
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)

Submission status: Accepted

Solution code:
from itertools import permutations
n,m=map(int,input().split())
G=[[0]*n for i in range(n)]
for i in range(m):
	a,b=map(int,input().split())
	G[a-1][b-1]=G[b-1][a-1]=1
l=[i+1 for i in range(n-1)]
c=0
for v in permutations(l,n-1):
	L=[0]+[i for i in v]
	if all([G[L[i]][L[i+1]]==1 for i in range(n-1)]):
		c+=1
print(c)

Submission status: Accepted

Solution code:
#ABC054 C - One-stroke Path

# v：現在の頂点 seen:訪問済みの頂点
def dfs(v,seen):
    if all(seen):
        return 1
    res = 0
    # 頂点ｖに隣接しているnvを探索していく
    for nv in G[v]:
        if seen[nv]:
            continue
        seen[nv]=True
        res += dfs(nv,seen)
        # 次の隣接頂点nvを探索した時の探索経路で、
        # 今回探索した隣接頂点nv通る可能性があるので
        # 元に戻しておく
        seen[nv]=False
    return res

n,m = map(int, input().split())
G = [[] for _ in range(n)]
seen = [False]*n
res = 0

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

# 頂点1を訪問済みとして探索を開始する
seen[0]=True
print(dfs(0,seen))

Submission status: Accepted

Solution code:
import itertools as it

N,M=map(int,input().split())
e=[[False for j in range(N+1)] for i in range(N+1)]
for i in range(M):
    a,b=map(int,input().split())
    e[a][b]=e[b][a]=True
# print(e) #DB

ans=0
l=list(range(2,N+1))
for p in it.permutations(l,N-1):
    q=(1,)+p    
    # print(q) #DB
    f=True
    for i in range(N-1):
        # print((q[i],q[i+1])) #DB
        if not e[q[i]][q[i+1]]:
            f=False
            break
    if f:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

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

g = [[0] * n for _ in range(n)]
for a, b in ab:
    a -= 1
    b -= 1
    g[a][b] = 1
    g[b][a] = 1

ans = 0
for pat in permutations(range(1, n), n - 1):
    is_path = True
    u = 0
    for v in pat:
        if g[u][v] == 0:
            is_path = False
        u = v

    if is_path:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools
n, m = map(int, input().split(" "))
d = {}
for i in range(1, n+1):
  d[i] = []

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

cnt = 0
for iter in itertools.permutations(range(2, n+1)):
  bp = 0
  for i, num in enumerate(iter):
    if i == 0:
      if num in d[1]:
        pass
      else:
        bp = 1
        break
    else:
      if num in d[iter[i-1]]:
        pass
      else:
        bp = 1
        break
  if bp == 0:
    cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import itertools
N, M = map(int, input().split())
X = [[int(a) - 1 for a in input().split()] for _ in range(M)]
Y = [[0] * N for _ in range(N)]
for a, b in X:
    Y[a][b] = 1
    Y[b][a] = 1
ans = 0
for A in itertools.permutations(range(1, N)):
    A = [0] + [a for a in A]
    if all([Y[A[i]][A[i+1]] for i in range(N-1)]):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
road = [[] for _ in range(n)]
result = [0] * n
def search(loc):
    result[loc] = 1
    if sum(result) == n:
        result[loc] = 0
        return 1
    
    cnt = 0
    for r in road[loc]:
        if result[r] == 0:
            cnt += search(r)
    result[loc] = 0
    return cnt
    

for _ in range(m):
    a, b = map(int,input().split())
    road[a-1].append(b-1)
    road[b-1].append(a-1)
print(search(0))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
M = [[] for _ in range(n+1)]
for i in range(1, m+1):
    a, b = map(int, input().split())
    M[a].append(b)
    M[b].append(a)
#print(M)

S = []
Xold =[[1]]
while Xold:
    Xnew = []
    for x in Xold:
        for y in M[x[-1]]:
            if y not in x:
                z = x + [y]
                Xnew.append(z)
                if len(z)== n:
                    S.append(z)
    #print(Xnew)            
    Xold = Xnew.copy()
    
print(len(S))  
#print(S)

Submission status: Accepted

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

ans = 0

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

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

dfs(1, [])
print(ans)

Submission status: Accepted

Solution code:
import itertools
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
#print(ab)
N_list = [i for i in range(1, N + 1)]

Np_list = list(itertools.permutations(N_list))
ans = 0
for p in Np_list:
    #print(p)
    flag = True
    if p[0] != 1:
        continue
    for j in range(len(p) - 1):
        if p[j] < p[j+1] and [p[j], p[j + 1]] not in ab:
            flag = False
        elif p[j] > p[j + 1] and ([p[j + 1], p[j]] not in ab):
            flag = False
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
nmax = 8
graph = [[0]*nmax for i in range(nmax)]
visited = [0] * nmax


def dfs(v, N, visited):
    all_visited = True
    for i in range(N):
        if visited[i] == 0:
            all_visited = False
    if all_visited:
        return 1
  
    ret = 0
    for i in range(N):
        if graph[v][i] == 0:
            continue
        if visited[i] == 1:
            continue
        visited[i] = 1
        ret += dfs(i, N, visited)
        visited[i] = 0
    return ret
      

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


visited[0] = 1
print(dfs(0, N, visited))

Submission status: Accepted

Solution code:
import itertools
L=["2","3","4","5","6","7","8"]

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

L=L[:N-1]
A=list(itertools.permutations(L,N-1))
C=[]
for i in A:
    B=["1"]+list(i)
    C.append(B)
#print(C)
D={}
for i in range(M):
    a,b=input().split()
    D[(a,b)]=1
    D[(b,a)]=1
    
#print(D)

ans=0
for i in C:
    f=1
    for j in range(N-1):
        if (i[j],i[j+1]) not in D:
            f=0
            break
    if f==1:
        ans+=1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

n, m = map(int, input().split())
adlist = [[] for _ in range(n)]
for _ in range(m):
  a, b = map(lambda x:int(x)-1, input().split())
  adlist[a] += [b]
  adlist[b] += [a]

ans = 0
used = [0] * n 
used[0] = 1
def dfs(u):
  global ans
  if sum(used) == n:
    ans += 1
    return 
  for v in adlist[u]:
    if used[v] == 0:
      used[v] = 1
      dfs(v)
      used[v] = 0

  return 

dfs(0)
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=[[] for i in range(n+1)]
for i in range(m):
  a,b=map(int,input().split())
  l[a].append(b)
  l[b].append(a)
lans=[]
def dfs(i,l1):
  if len(l1)==n:
    lans.append(l1)
    return
  for j in l[i]:
    if j in l1:
      pass
    else:
      l2=l1+[j]
      dfs(j,l2)
  return
dfs(1,[1])
print(len(lans))

Submission status: Accepted

Solution code:
import itertools

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

res = 0
for sp in itertools.permutations(l):
    flag = 1
    s = 0
    for i in range(n-1):
        if not (sp[i] in g[s]):
            flag = 0
            break
        else:
            s = sp[i]
    if flag == 1:
        res += 1

print(res)

Submission status: Accepted

Solution code:
import itertools
N,M = (int(i) for i in input().split())
K = []
for i in range(M):
    J = [int(i) for i in input().split()]
    J.sort()
    K.append(J)

#1以外の頂点リストを作成
vertex = []
for i in range(N-1):
    vertex.append(i+2)
#順列作成
X = list(itertools.permutations(vertex))

#各値ごとに有無をチェック
ans = 0
for i in X:
    start = 1
    localcount = 0
    for j in i:
        tmp = [start,j]
        tmp.sort()
        if tmp in K:            
            localcount += 1   
        start = j
            
    if localcount == N-1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

a=[]
for i in range(N):
    a.append(i+1)

L=list(itertools.permutations(a))


cnt=0

for l in L:
    tmp=1
    if l[0]!=1:
        break
    for j in range(N-1):
        if ([l[j],l[j+1]] in S) or ([l[j+1],l[j]] in S):
            tmp=1
        else:
            tmp=0
            break
    if tmp==1:
        cnt+=1

print(cnt)

Submission status: Accepted

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

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

def dfs(v, used):
    #usedにFalseの値が入っていなかったら関数終了
    if not False in used:
        return 1
    
    ans = 0
    
    #adj_matrixがTrueじゃなかったら
    for i in range(N):
        #0だったら→枝がなかったら
        if not adj_matrix[v][i]:
            continue
        #usedに値があったら
        if used[i]:
            continue
        
        #used_iにTrueを代入
        used[i] = True
        #再帰
        ans += dfs(i, used)
        used[i] = False
    
    return ans
#main処理
#usedを全てFalseが詰まったリストにする
used = [False] * N
#used_0=1はTrue
used[0] = True

print(dfs(0, used))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
g = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)
 
ans = 0
def walk(cur, visited):
    global ans
    tmp = visited + [cur]
    if len(tmp) == N:
        ans += 1
        return
    for nex in g[cur]:
        if nex not in tmp:
            walk(nex, tmp)
walk(1, [])
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys

graph = {}

def solve(start, visited = set()):
    global graph

    visited = visited | set([start])
    if len(visited) == len(graph):
        return 1

    ans = 0
    for next_ in graph[start]:
        if not next_ in visited:
            ans += solve(next_, visited)
    return ans

def read_int_list():
    return [int(s) for s in sys.stdin.readline().rstrip().split(" ")]

def dprint(*args, **kwargs):
    return
    print(*args, **kwargs)

def connect(f, t):
    global graph
    if not f in graph:
        graph[f] = set()
    graph[f].add(t)

def main():
    global graph
    
    _, m = read_int_list()
    for _ in range(0, m):
        a, b = read_int_list()
        connect(a, b)
        connect(b, a)

    dprint(repr(graph))
    print(solve(1))

main()

Submission status: Accepted

Solution code:
import itertools
n,m=map(int,input().split())
data=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    data[a].append(b)
    data[b].append(a)
z=[i+2 for i in range(n-1)]
ans=0
for u in itertools.permutations(z):
    if u[0] in data[1]:
        for i in range(1,n-1):
            if u[i] in data[u[i-1]]:
                continue
            else:
                break
        else:
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
import itertools
N, M = map(int, input().split())
d = [[] 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)

r = 0
for path in itertools.permutations(range(1, N)):
  path = tuple([0]) + path
  for i in range(1, N):
    if(path[i] not in d[path[i-1]]):
      break
  else:
    r += 1
print(r)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
G = [ set() for _ in range(n+1) ]
for  _ in range(m):
  a, b = map(int, input().split())
  G[a].add(b)
  G[b].add(a)
seen = [False]*(n+1)

def dfs(v, c):
  if c == n:
    return 1
  seen[v] = True
  temp = 0
  for nv in G[v]:
    if not seen[nv]:
      temp += dfs(nv, c+1)
  seen[v] = False
  return temp

print(dfs(1, 1))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
g = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

ans = 0
def walk(cur, visited):
    global ans
    tmp = visited + [cur]
    if len(tmp) == N:
        ans += 1
    for nex in g[cur]:
        if nex not in tmp:
            walk(nex, tmp)
walk(1, [])
print(ans)

Submission status: Accepted

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

ret = 0
def walk(node, visited):
    global ret
    tmp = visited + [node]
    if len(tmp) == n:
        ret += 1 
    for nd in g[node]:
        if nd not in tmp:
            walk(nd, tmp)
walk(1, [])
print(ret)

Submission status: Accepted

Solution code:
nmax = 8
graph = [[False] * nmax for _ in range(nmax)]


def dfs(v, N, visited):
    all_visited = True
    for i in range(N):
        if not visited[i]:
            all_visited = False
    if all_visited:
        return 1

    ret = 0
    for i in range(N):
        if not graph[v][i]:
            continue
        if visited[i]:
            continue

        visited[i] = True
        ret += dfs(i, N, visited)
        visited[i] = False
    return ret


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

visited = [False] * nmax
visited[0] = True
print(dfs(0, N, visited))

Submission status: Accepted

Solution code:
def f(i, links, visited, nodes):
    t = 1 << i
    if t & visited != 0:
        return 0
    visited |= t
    if visited == (1 << nodes) - 1:
        return 1
    result = 0
    for j in links[i]:
        result += f(j, links, visited, nodes)
    return result


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

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

result = 0
for i in links[0]:
    result += f(i, links, 1, N)
print(result)

Submission status: Accepted

Solution code:
from itertools import permutations as per
n,m = map(int,input().split())
g = [[] 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)
c = 0
for i in per(range(2,n+1)):
  cur = 1
  f = 1
  for j in range(n-1):
    pre,cur = cur,i[j]
    if cur-1 not in g[pre-1]:
      f = 0
      break
  c += f
print(c)

Submission status: Accepted

Solution code:
def examC():
    def search_graph(graph_releation, result_list, current_idx=0, path=[0]):
        for i in range(len(graph_releation[current_idx])):
            next_idx = graph_releation[current_idx][i]
            #次の点の候補全部ひとつずつやる
            tmp_path = copy.deepcopy(path)
            #今まで通った点
            if next_idx in tmp_path:
                #通ったことがある
                continue
            tmp_path.append(next_idx)
            if len(tmp_path) == len(graph_releation):
                #今まで通った点が点全部になった
                result_list.append(tmp_path)  # 確定
                continue
            else:
                search_graph(graph_releation, result_list, next_idx, tmp_path)
                #次の点から出る辺でチェック

    N, M = LI()
    v = [[] for _ in range(N)]
    for i in range(M):
        a, b = LI()
        v[a-1].append(b-1)
        v[b-1].append(a-1)
    cur = []
    search_graph(v, cur)
    print(len(cur))
#    print(cur)

import sys
import copy
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examC()

Submission status: Accepted

Solution code:
import itertools

N,M = map(int, input().split())
E = [[0]*N for _ in range(N)]
for _ in range(M):
    y, x = map(int, input().split())
    E[y-1][x-1] = 1
    E[x-1][y-1] = 1

ans = 0
L = [int(i) for i in range(1, N)]
for P in itertools.permutations(L):
    f = 0
    for i in range(N-1):
        if i == 0:
            if E[0][P[i]] == 0:
                f = 1
                break
        elif E[P[i-1]][P[i]] == 0:
            f = 1
            break
    if f == 0:
        ans += 1
        
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
n,m=map(int,input().split())
g=[]
for i in range(m):
    a,b=map(int,input().split())
    g.append([a,b])
    g.append([b,a])
ans=0
for i in permutations(range(2,n+1),n-1):
    f=0
    if not [1,i[0]] in g:
        continue
    for j in range(n-2):
        if not [i[j],i[j+1]] in g:
            f=1
            break
    if f==0:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import copy

def perm(i, ls):
    if not ls:
        return 1
    else:
        count = 0
        for j in ls:
            if cost[i-1][j-1]:
                ls2 = copy.copy(ls)
                ls2.remove(j)
                count += perm(j, ls2)
        return count

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

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


count = perm(1, list(range(2, n+1)))

print(count)

Submission status: Accepted

Solution code:
import copy

def perm(i, ls):
    if not ls:
        global count
        count += 1
    else:
        for j in ls:
            if cost[i-1][j-1]:
                ls2 = copy.copy(ls)
                ls2.remove(j)
                perm(j, ls2)

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

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

count = 0
perm(1, list(range(2, n+1)))

print(count)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import copy

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

result_list = []

def search_graph(graph_releation,result_list,current_idx=0,path=[0]):
    for i in range(len(graph_releation[current_idx])):
        next_idx = graph_releation[current_idx][i]
        tmp_path = copy.deepcopy(path)
        if next_idx in tmp_path:
            continue
        tmp_path.append(next_idx)
        if len(tmp_path) == len(graph_releation):
            result_list.append(tmp_path) #確定
            continue
        else:
            search_graph(graph_releation,result_list,next_idx,tmp_path)

search_graph(graph_releation,result_list)
print(len(result_list))

Submission status: Accepted

Solution code:
def one_stroke_path(path, graph, i):
    if len(path) == N:
        return 1
    if not graph[i]:
        return 0
    if graph[i] in path:
        return 0
    res = 0
    for node in graph[i]:
        if not node in path:
            res += one_stroke_path(path + [node], graph, node)
    return res

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

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

ans = 0
path = [0]
i = 0

print(one_stroke_path(path, graph, i))

Submission status: Accepted

Solution code:
from copy import deepcopy as dp
N, M = map(int, input().split())
path = [list(map(int, input().split())) for i in range(M)]
count = 0

def ser(plase, path, ans):
    global count
    for i in range(len(path)):
        if path[i][0] == plase and not path[i][1] in ans:
            next_path = dp(path)
            next_path.pop(i)
            next_ans = dp(ans)
            next_ans.append(path[i][1])
            ser(path[i][1], next_path, next_ans)
        if path[i][1] == plase and not path[i][0] in ans:
            next_path = dp(path)
            next_path.pop(i)
            next_ans = dp(ans)
            next_ans.append(path[i][0])
            ser(path[i][0], next_path, next_ans)
    if N == len(ans):
        count += 1
ser(1, path, [1])
print(count)

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    matrix = [[0] * N for _ in range(N)]

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

    def dfs(v, used):
        if False not in used:
            return 1

        ans = 0
        for i in range(N):
            if not matrix[v][i]:
                continue
            if used[i]:
                continue

            used[i] = True
            ans += dfs(i, used)
            used[i] = False

        return ans

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

    print(dfs(0, used))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4100000)

def Dfs(G, v, n, visited):
    all_visited = True
  
    for i in range(n):
      if visited[i] == False:
        all_visited = False
 
    if all_visited:
        return 1
 
    ret = 0
 
    for i in range(n):
        if not G[v][i]:
            continue
        if visited[i]:
            continue
        visited[i] = True
        ret += Dfs(G, i, n, visited)
        visited[i] = False
 
    return ret

 
def main():
    input =  sys.stdin.readline
    n, m = map(int, input().split())
    e = [list(map(int, input().split())) for i in range(m)]
    g = [[False for j in range(n)] for i in range(n)]
    for i, j in e:
        g[i-1][j-1] = True
        g[j-1][i-1] = True
    visited = [False for i in range(n)]
    visited[0] = True
    
    print(Dfs(g, 0, n, visited))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import copy
def solve():
    sys.setrecursionlimit(100000)
    input = sys.stdin.readline
    N, M = map(int, input().split())
    adjM = [[0] * N for i in range(N)] 
    for i in range(M):
        a, b = map(int, input().split())
        adjM[a - 1][b - 1] = 1
        adjM[b - 1][a - 1] = 1

    arrived = [False] * N
    ans = dfs(0, adjM, arrived, N)
    print(ans)

def dfs(now, adjM, arrived, N):
    arrived[now] = True
    if arrived == [True] * N:
        return 1
    
    cnt = 0
    for i in range(N):
        if adjM[now][i] == 1 and not arrived[i]:
            cnt += dfs(i, adjM, copy.deepcopy(arrived), N)
    
    return cnt


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
path = [[] for _ in range(n)]
ab = [list(map(int,input().split())) for _ in range(m)]
for a,b in ab:
  path[a-1].append(b-1)
  path[b-1].append(a-1)

def DFS(now,v_set):
  if v_set.count(True) == n:
    return 1
  if all(v_set[i] for i in path[now]):
    return 0
  c = 0
  for v in path[now]:
    if v_set[v]==False:
      v_set[v] = True
      c += DFS(v,v_set)
      v_set[v] = False
  return c
  
v_set = [False]*n
v_set[0] = True
print(DFS(0,v_set))

Submission status: Accepted

Solution code:
from collections import deque
from copy import copy as dc
import sys

def main():
    input = sys.stdin.readline
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(m)]
    g = [[] for i in range(n+1)]
    for i in ab:
        g[i[0]].append(i[1])
        g[i[1]].append(i[0])
    que = deque()
    que.append([1,-1,0,set([1])])
    ans = 0
    while que:
        v, p, cnt, check = que.popleft()
        if cnt >= n - 1:
            if len(check) == n:
                ans += 1
            continue
        for nv in g[v]:
            if nv == p:
                continue
            a = dc(check)
            a.add(nv)
            que.append([nv, v, cnt+1, a])
    print(ans)

if __name__ == "__main__":
    main()