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:

N,M = [int(i) for i in input().split(" ")]
neighbor_dict={n:set() for n in range(1,N+1)}


for i in range(M):
    a,b = [int(i) for i in input().split(" ")]
    neighbor_dict[a].add(b)
    neighbor_dict[b].add(a)

ans = 0

def crawl(vertex:int,visited_set:set):
    visited_set = visited_set | {vertex}
    if len(visited_set) == N:
        global ans
        ans = ans + 1
        return

    to_visit = set(neighbor_dict[vertex]) - visited_set

    for v in to_visit:
        crawl(v,visited_set)

crawl(1,set())
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(M)]
stack = deque([[1]])
seen = deque([])
c = 0
while stack:
  x = stack.pop()
  seen.append(x)
  if len(x)==N:
    c += 1
    continue
  p = x[-1]
  A = []
  for l in L:
    if l[0]==p:
      A.append(l[1])
    if l[1]==p:
      A.append(l[0])
  A = [a for a in A if a not in x]
  for a in A:
    if x+[a] in (seen or stack):
      continue
    else:
      stack.append(x+[a])
print(c)

Submission status: Accepted

Solution code:
from collections import defaultdict
n, m = map(lambda x: int(x), input().split())

links = defaultdict(set)

for _ in range(m):
    a, b = map(lambda x: int(x), input().split())
    links[a].add(b)
    links[b].add(a)
    
path_counter = 0
    
def path_patterns_number(current_node, remaining_nodes):#, remaining_links):
    if len(remaining_nodes) == 0:
        return 1
    
    patterns = 0
    
    for next_node in (links[current_node] & remaining_nodes):
#         remaining_links_copy = remaining_links.copy()
#         remaining_links_copy[current_node].remove(next_node) <=浅いコピーなので元のからもremoveされてる
        patterns += path_patterns_number(
            next_node,
            remaining_nodes.copy() - {next_node}
#             remaining_links_copy
        )
    
    return patterns
    
print(path_patterns_number(1, set(range(2,n+1))))

Submission status: Accepted

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

I = [set() for _ in range(N)]
seq = [i for i in range(1,N)]

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

ans = 0
for p in itertools.permutations(seq):
  flag = True
  for i in range(N-2):
    #print(p,i)
    if p[i+1] not in I[p[i]]:
      flag = False 
      break
  if 0 not in I[p[-1]]:#0を終点とする
    flag = False 
  if flag:
    ans += 1
#print(I)    
print(ans)

Submission status: Accepted

Solution code:
import itertools
n, m = map(int, input().split())
G = [set() for _ in range(n)]
for _ in range(m):
    a,b = map(lambda x:int(x)-1, input().split())
    G[a].add(b)
    G[b].add(a)

P = [*itertools.permutations(range(1,n))]
ans = 0
for p in P:
    nw = 0
    for nx in p:
        if nx in G[nw]:
            nw = nx
        else:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

n,m = MI()
graph = [[] for _ in range(n+1)]
for i in range(m):
    a,b = MI()
    graph[a].append(b)
    graph[b].append(a)
visited = [False]*(n+1)
visited[0] = True
visited[1] = True
def dfs(v,visited):
    if all(visited):
        return 1
    ans = 0
    for i in graph[v]:
        if visited[i]:
            continue
        visited[i] = True
        ans += dfs(i,visited)
        visited[i] = False
    return ans
print(dfs(1,visited))

Submission status: Accepted

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

g = [[] for _ in range(N)]

for i in range(M):
    a, b = list(map(int, input().split()))

    g[a-1].append(b-1)
    g[b-1].append(a-1)

visited = [False for _ in range(N)]

def dfs(now, prev, vis):
    visited_copy = copy.copy(vis)
    visited_copy[now] = True
    all_visited = True

    for is_node_visited in visited_copy:
        if not is_node_visited:
            all_visited = False

    if all_visited:
        return 1

    counter = 0
    for adj in g[now]:
        if prev == adj:
            continue

        if visited_copy[adj]:
            continue
        counter += dfs(adj, now, visited_copy)

    return counter

ans = dfs(0, -1, visited)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

n, m = map(int, input().split())
edge = [[False] * n for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    edge[a-1][b-1] = True
    edge[b-1][a-1] = True

res = 0
for t in permutations(list(range(1, n))):
    l = list(t)
    l.insert(0, 0)
    flag = True

    for i in range(n-1):
        if not edge[l[i]][l[i+1]]:
            flag = False

    if flag:
        res += 1

print(res)

Submission status: Accepted

Solution code:
import itertools
N, M, *AB = [int(_) for _ in open(0).read().split()]
G = [set() for _ in range(N)]
for a, b in zip(AB[::2], AB[1::2]):
    a -= 1
    b -= 1
    G[a].add(b)
    G[b].add(a)
ans = 0
for root in itertools.permutations(range(1, N), N - 1):
    root = [0] + list(root)
    if all(a in G[b] for a, b in zip(root, root[1:])):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:

#入力

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

graph = [ ]
for _ in range(N+1):
    graph.append([])

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

visited = []
for _ in range(N+1):
    visited.append(False)


def dfs(dep,cur):
    global N,visited,graph

    if dep == N:
        return 1

    ans = 0

    for dist in graph[cur]:
        if visited[dist] == False:
            visited[dist] = True
            ans += dfs(dep + 1,dist)
            visited[dist] = False
    return ans

visited[1] = True
print(dfs(1,1))

Submission status: Accepted

Solution code:
import itertools

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

path = [[False] * n for i in range(n)]
#ｎ行ｎ列のpathリストを生成(中身はすべてFalseにする)
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    path[a][b] = True
    path[b][a] = True
    #頂点aを行、頂点bを列とするようpathリストを更新
    #無向グラフなのでpath[b][a]=Trueも入れる
    
ans = 0
#出力の初期値

# 頂点を並び替える順列を生成してループ
for i in itertools.permutations(range(n), n):
    # 頂点1が始点
    if i[0] == 0:
        # 生成した順列の中をさらにループ
        #生成した順列からすべての頂点を探索する
        for j in range(n):
            # n - 1 まで続いたら全ての頂点を探索したとなるので
            #条件を満たすpathが存在する
            if j == n - 1:
                ans += 1
                break
            # i[j] から i[j + 1] に行くパスがなければ終了
            #ここでpath[a][b] = True or Falseの値を参照している
            #参照した場所の値がTrueでない場合終了
            if not path[i[j]][i[j + 1]]:
                break

print(ans)

Submission status: Accepted

Solution code:
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):
    #もし全てTrueなら1を返す
    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))

Submission status: Accepted

Solution code:
"""
順列全探索
"""
import itertools
n, m = map(int, input().split())
path = []
for _ in range(m) :
    a, b = map(int, input().split())
    path.append([a, b])

ans = 0
order_list = list(itertools.permutations(range(2,n+1)))
for order in order_list :
    now = 1
    for i in order :
        if [now,i] in path :
            now = i
        elif [i,now] in path :
            now = i
        else :
            break
    else :
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N, M = read_ints()
    G = defaultdict(list)
    for _ in range(M):
        a, b = read_ints()
        G[a].append(b)
        G[b].append(a)

    def dfs(node, visited):
        if len(visited) == N:
            return 1
        answer = 0
        for child in G[node]:
            if child not in visited:
                visited.add(child)
                answer += dfs(child, visited)
                visited.discard(child)
        return answer
    
    return dfs(1, set([1]))


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N, M = map(int, input().split(' '))

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

is_used = [False for _ in range(N)]
is_used[0] = True
buf = [(0, is_used)]
ans = 0

while buf:
    src, is_used = buf.pop()
    if all(is_used):
        ans += 1

    else:
        for dst in graph[src]:
            if not is_used[dst]:
                is_used2 = list(is_used)
                is_used2[dst] = True
                buf.append((dst, is_used2))

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
Path = [list(map(int, input().split())) for _ in range(M)]
import itertools

lis = [x for x in range(2, N+1)] 
ans = 0

permutations_lis = itertools.permutations(lis)

for one_case in permutations_lis:
  List = [1]
  List.extend(one_case)
  for i in range(N-1):
    if not ([List[i], List[i+1]] in Path or [List[i+1], List[i]] in Path):
      break
  else:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m=map(int,input().split())
path=[]
for i in range(m):
    a,b=map(int,input().split())
    path.append([a,b])
    path.append([b,a])
ans=0
factorial=list(itertools.permutations(list(range(1,n+1))))

for i in range(len(factorial)):
    if factorial[i][0]!=1:
        continue
    flag=True
    for j in range(1,n):
        if [factorial[i][j-1],factorial[i][j]] not in path:
            flag=False
    ans+=flag
print(ans)

Submission status: Accepted

Solution code:
mat = [[] for i in range(10)]
vis  = [False for i in range(10)]
def dfs(a, n):
	all_vis= True
	for i in range(0, n):
		if vis[i]==False:
			all_vis=False
	if all_vis==True:
		return 1
	ans =0
	for i in mat[a]:
		if vis[i]==True:
			continue
		vis[i]=True
		ans = ans+dfs(i,n)
		vis[i]=False
	return ans
n , m = map(int , input().split())
for i in range(m):
	a, b= map(int ,input().split())
	a =a-1
	b=b-1
	mat[a].append(b)
	mat[b].append(a)
vis[0]=True
print(dfs(0, n))

Submission status: Accepted

Solution code:
import itertools

n, m = map(int, input().split())
lsts = []
for _ in range(m):
  lsts.append(list(map(int, input().split())))
m = list(range(2, n + 1))
all = []
for v in itertools.permutations(m):
  l = [1] + list(v)
  all.append(l)
#print(all)

count = 0
for each in all:
  for i in range(n - 1):
    flag = False
    pos_1 = each[i]
    pos_2 = each[i + 1]
    for lst in lsts:
      if (pos_1 == lst[0] and pos_2 == lst[1]) or (pos_1 == lst[1] and pos_2 == lst[0]):
        flag = True
        break
    if not flag:
      break
  if flag:
    count += 1
print(count)

Submission status: Accepted

Solution code:
N, M = list(map(int,input().split()))
G = [[] for _ 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)

def dfs(depth, node):
    global visited
    global ans
    visited[node] = 1
    if depth == N - 1:
        if sum(visited) == N:  ans += 1
        return
    for i in G[node]:
        if visited[i] == 0:
            dfs(depth + 1, i)
            visited[i] = 0
            
ans = 0
visited = [0 for _ in range(N)]
dfs(0, 0)
print(ans)

Submission status: Accepted

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

adj = [[] for _ in range(n)]
for a, b in ab:
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)

dp = [[0] * n for _ in range(1 << n)]
dp[1][0] = 1

for i in range(1 << n):
    for u in range(n):
        for v in adj[u]:
            if i >> v & 1 == 0:
                nxt = i + (1 << v)
                dp[nxt][v] += dp[i][u]

print(sum(dp[-1]))

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 + 1) for _ in range(n + 1)]
for a, b in ab:
    g[a][b] = 1
    g[b][a] = 1

ans = 0
for nxt in permutations(range(2, n + 1), n - 1):
    bl = 1
    u = 1
    for v in nxt:
        if not g[u][v]:
            bl = 0
            break
        u = v

    ans += bl

print(ans)

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
n,m=f()
g=[[] for _ in range(n)]
for _ in range(m):
  a,b=f()
  g[a-1]+=[b-1]
  g[b-1]+=[a-1]
from itertools import *
p=[*permutations(range(1,n))]
a=0
for t in p:
  v=0
  for c in t:
    if c in g[v]: v=c
    else: break
  else: a+=1
print(a)

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
n,m=f()
g=[[0]*n for _ in range(n)]
for _ in range(m):
  a,b=f()
  g[a-1][b-1]=1
  g[b-1][a-1]=1
from itertools import *
p=[*permutations(range(1,n))]
a=0
for t in p:
  v=0
  for c in t:
    if g[v][c]: v=c
    else: break
  else: a+=1
print(a)

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
n,m=f()
g=[set() for _ in range(n)]
for _ in range(m):
  a,b=f()
  g[a-1].add(b-1)
  g[b-1].add(a-1)
from itertools import *
p=[*permutations(range(1,n))]
c=0
for t in p:
  v=0
  for i in t:
    if i in g[v]: v=i
    else: break
  else: c+=1
print(c)

Submission status: Accepted

Solution code:
from collections import deque
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)
ans = 0
que = deque([[0]])
while len(que) != 0:
    p = que.popleft()
    if len(p) == N:
        ans += 1
    else:
        for i in range(len(g[p[-1]])):
            if not g[p[-1]][i] in p:
                que.append(p + [g[p[-1]][i]])
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import permutations

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, *AB = map(int, read().split())
    G = [[] for _ in range(N)]
    for a, b in zip(*[iter(AB)] * 2):
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)

    def dfs(v, seen):
        if len(seen) == N:
            return 1

        ans = 0
        for nv in G[v]:
            if nv not in seen:
                seen.add(nv)
                ans += dfs(nv, seen)
                seen.remove(nv)

        return ans

    print(dfs(0, {0}))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import permutations

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, *AB = map(int, read().split())
    G = [[False] * N for _ in range(N)]
    for a, b in zip(*[iter(AB)] * 2):
        G[a - 1][b - 1] = G[b - 1][a - 1] = True

    ans = 0
    for perm in permutations(range(1, N)):
        if not G[0][perm[0]]:
            continue
        ok = True
        for i in range(N - 2):
            if not G[perm[i]][perm[i + 1]]:
                ok = False
                break
        if ok:
            ans += 1

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import permutations

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

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)

ans = 0
for perm in permutations(range(1, n), n-1):
    s = 0
    flag = True
    for p in perm:
        if p not in g[s]:
            flag = False
            break
        s = p
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import *
f=lambda:map(int,input().split())
N,M=f()
a=[[*f()] for i in range(M)]
a=[*a,*[[y,x] for x,y in a]]
p=[(1,*i)for i in [*permutations(range(2,N+1))]]
print([sum(1 for y in range(N-1)if [x[y],x[y+1]] in a)for x in p].count(N-1))

Submission status: Accepted

Solution code:
from itertools import permutations
import copy

def resolve():
    N, M = list(map(int, input().split()))
    G = [[0] * N for _ in range(N)]
    for i in range(M):
        a, b = list(map(int, input().split()))
        G[a-1][b-1] = 1
        G[b-1][a-1] = 1

    ls = list(permutations(range(1, N)))
    ans = 0
    for l in ls:
        h = copy.deepcopy(G)
        cnt = 1
        p = 0 
        for k in l:
            if h[p][k] == 0:
                break
            else:
                cnt += 1
                p = k
        if cnt == N:
            ans += 1
    print(ans)
    return

resolve()

Submission status: Accepted

Solution code:
def saiki(arr_lst,count,path,N):
	if len(path) == N:
		count[0] += 1
	else:
		here = path[-1]
		arrival = arr_lst[here]
		for next in arrival:
			if not next in path:
				newpath = path[:]
				newpath.append(next)
				saiki(arr_lst,count,newpath,N)


if __name__ == '__main__':
	N, M = map(int, input().split())
	arr_lst = [[]]

	for i in range(1,N+1):
		arr_lst.append([])

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

	count = [0]

	saiki(arr_lst,count,[1],N)

	print(count[0])

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

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

dp = [[-1] * n for i in range(1<<n)]
#訪れた集合がs、今いる点がvの時０に戻る最短経路
def rec(s,v,dp):
    if dp[s][v] >= 0:
        return dp[s][v]
        
    if s == (1<<n)-1:
        dp[s][v] = 1
        return 1
    
    res = 0
    for u in range(n):
        if (s>>u&1) == 0 and d[v][u] == 1:
            res += rec(s|(1<<u),u,dp)
    dp[s][v] = res
    return res

print(rec(1,0,dp))

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


from collections import defaultdict
n,m = map(int, input().split())
ns = defaultdict(set)
for _ in range(m):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add(v)
    ns[v].add(u)
dp = [[0]*(1<<n) for _ in range(n)]
dp[0][1] = 1
for b in range(1, 1<<n):
    for u in range(n):
        for i in range(n):
            if not (b>>i&1) and i in ns[u]:
                dp[i][b+(1<<i)] += dp[u][b]
ans = sum(dp[u][(1<<n)-1] for u in range(n))
print(ans)

Submission status: Accepted

Solution code:

## import
from collections import deque # キュー、スタックに利用
import itertools
import math # 数学的計算に利用
# import numpy as np # 行列計算などに利用 # Pypy3ではimport不可
import sys

## 初期設定
# input = sys.stdin.readline # 標準入力の高速化に利用
sys.setrecursionlimit(10**7) # 再帰関数の呼び出し上限を増やす
inf = float('inf')

is_debug = False

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

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

## 隣接リスト表現でグラフを表現する
# 空の2次元リストの初期化 行数n * 列数0
M = [[] for _ in range(n)]
for a,b in AB:
    M[a-1].append(b-1)
    M[b-1].append(a-1)

if is_debug:
    for row in M:
        print(row)
    print('-----------')

def main():
    '''メイン処理'''

    ok_count = 0
    # 全パターンの順列（要素が同じでも、順番が異なれば異なるとみなすもの）を生成し、
    # 一つずつ、始点から終点までたどり着けるかチェック
    for permutation in itertools.permutations(range(1,n)):
        move_list = list(permutation)
        if is_debug:
            print(move_list)

        # この順列で終点までたどり着けるかチェック
        move_count = 0
        now_n = 0 # 始点は必ず0
        for next_n in move_list:
            if next_n in M[now_n]:
                now_n = next_n
                move_count += 1
            else:
                break
        if move_count == len(move_list):
            ok_count += 1
    
    print(ok_count)
            

if __name__ == "__main__":
    # ファイル実行時に、main()関数を実行
    main()

Submission status: Accepted

Solution code:
from itertools import permutations

N,M = list(map(int,input().split()))
P=[]
for m in range(M):
    P.append(list(map(int,input().split())))

ad={}
for _ in range(1,N+1):
    ad[_]=set()
    
for p in P:
    ad[p[0]].add(p[1])
    ad[p[1]].add(p[0])

ans=0
for p in permutations(range(2,N+1),N-1):
    ans_flag=True
    start=1
    for p_ in p:
        end=p_
#         print(start,end ,end in ad[start])
        if end not in ad[start]:
#             print('break')
            ans_flag=False
            break
        start=p_
        
    if ans_flag==True:
        ans+=1
        
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from collections import deque
from copy import deepcopy

def perm(h,r):
    n=len(r)
    stack=[]
    if n==0:
        return [h]
    for i in range(n):
        nh=h+[r[i]]
        nr=r[:i]+r[i+1:]
        stack+=perm(nh,nr)
    return stack
        
def main():
    n,m=map(int,input().split())
    e=[tuple(map(int,input().split())) for _ in range(m)]
    gm=[[0]*n for _ in range(n)]
    for edge in e:
        gm[edge[0]-1][edge[1]-1]=1
        gm[edge[1]-1][edge[0]-1]=1
    l=perm([],list(range(2,n+1)))
    c=0
    for s in l:
        s=[1]+s
        f=1
        for i in range(n-1):
            if gm[s[i]-1][s[i+1]-1]==0:
                f=0
                break
        if f:
            c+=1
    print(c)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

N,M = map(int, input().split())
g = [[0 for i in range(N)] for j in range(N)]

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

  
jr = list(itertools.permutations(range(2,N+1),N-1))
js = []

for i in jr:
  j = list(i)
  j.insert(0,1)
  js.append(j)

ans = 0
  
for i in range(len(js)):
  hantei = True
  for j in range(N-1):
    a = js[i][j]
    #print(a)
    b = js[i][j+1]
    #print(b)
    if g[a-1][b-1] == 0:
      hantei = False
  if hantei:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import *
N,M = map(int,input().split())
S = [list(map(int,input().split())) for m in range(M)]
a = 0

for p in permutations(range(1,N+1)):
  f = True
  if p[0]==1:
    for n in range(N-1):
      if sorted([p[n],p[n+1]]) not in S:
        f = False
    if f:
      a+=1

print(a)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
intx = lambda x:int(x)-1
#mp = [list(map(intx,input().split())) for _ in range(M)]
adj = [[0]*N for _ in range(N)]
for i in range(M):
    a,b = map(intx,input().split())
    adj[a][b] = 1
    adj[b][a] = 1
#print(adj)

visited = [False]*N
def dfs(loc,depth):
    if visited[loc]:
        return 0
    if depth == N-1:
        return 1
        
    visited[loc] = True
    path = 0
    for i in range(N):
        if adj[loc][i]:
            path+=dfs(i,depth+1)
    
    visited[loc] = False
    
    return path
    
print(dfs(0,0))

Submission status: Accepted

Solution code:
def dfs(v,visited):
  if all(visited):
    return 1
  res=0
  for nv in G[v]:
    if visited[nv]:
      continue
    visited[nv]=1
    res+=dfs(nv,visited)
    visited[nv]=0
  return res
 
n,m=map(int, input().split())
G=[[] for _ in range(n)]
visited=[0]*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)

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
L = [tuple(map(int, input().split())) for _ in range(M)]
import itertools
l = [i for i in range(2, N+1)]
Ps = itertools.permutations(l, N-1)
c = 0
for P in Ps:
  T = 1
  for p in P:
    if (T, p) in L or (p, T) in L:
      T = p
    else:
      break
  else:
    c += 1
print(c)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

# 関数定義
def dfs(now_p, visited, comb_p, p_num):
    # N頂点と同じ数のルートを通ったら有効なパスとして1を返す
    if len(visited) == p_num:
        return 1

    ans = 0

    # now_pの検索
    for tmp_p in comb_p:
        if tmp_p[0] == now_p and tmp_p[1] not in visited:
            # visitedのtmp
            tmp_visited = visited[:]
            tmp_visited.append(tmp_p[1])
            #print(*tmp_visited)
            # 次の頂点
            next_p = tmp_p[1]
            #print('next_p: ', next_p)
            # comb_pのtmp
            tmp_comb = comb_p[:]
            tmp_comb.remove(tmp_p)
            # 往復対象の削除
            tmp_p_r = [tmp_p[1], tmp_p[0]]
            tmp_comb.remove(tmp_p_r)
            #print(*tmp_comb)
            # dfsの再起呼び出し
            ans += dfs(next_p, tmp_visited, tmp_comb, p_num)

    return ans

## 入力読み取り
N, M = map(int, input().split())
a_b = []
tmp = []
tmp_r = []

# 辺読み取り
for i in range(M):
    tmp = list(map(int, input().split()))
    tmp_r = [tmp[1], tmp[0]]
    a_b.append(tmp)
    a_b.append(tmp_r)

visited = [1]

# 再起関数の実施
pass_num = dfs(1, visited, a_b, N)
print(pass_num)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
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)

used = [False] * n
ans = 0
def dfs(i, depth=1):
    ret = 0
    if depth==n:
        return 1
    else:
        for e in g[i]:
            if used[e]:
                continue
            used[e] = True
            ret+=dfs(e, depth+1)
            used[e] = False
    return ret

used[0] = True
print(dfs(0, 1))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
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)

used = [False] * n
ans = 0
def dfs(itr, n, cnt=0):
    ans = 0
    if len(itr)==n:
        return 1
    else:
        ans = cnt
        for e in g[itr[-1]]:
            if used[e]:
                continue
            used[e] = True
            ans+=dfs(itr+[e], n)
            used[e] = False
    return ans

used[0] = True
print(dfs([0], n, 0))

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

from itertools import permutations
ans=0
p=list(permutations([x for x in range(1,n)]))
for pp in p:
  ok=True
  t=[0]+list(pp)
  for i in range(1,n):
    if G[t[i-1]][t[i]]==0:
      ok=False
  if ok:ans+=1
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
n,m=map(int,input().split())
lst=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    lst[a-1].append(b-1)
    lst[b-1].append(a-1)
kumi=list(permutations(range(1,n)))
ans=0
for i in kumi:
    switch=1
    prev=0
    for j in range(n-1):
        if not i[j] in lst[prev]:
            switch=0
            break
        prev=i[j]
    if switch==1:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
# -*- 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))