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

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


def dfs(n, path):
    count = 0
    path.append(n)
    if len(path) == N:
        count += 1
        return count
    for i in d[n]:
        if i not in path:
            count += dfs(i, path)
            path.pop()

    return count


print(dfs(1, []))

Submission status: Accepted

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

checked = [0] * 8
path = [[] for _ in range(8)]

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

ans = 0

def dfs(place):
  checked[place] = 1
  if sum(checked) == N:
    return 1
  ret = 0
  for i in path[place]:
    if checked[i] == 1:
      continue
    ret += dfs(i)
    checked[i] = 0
  return ret

print(dfs(0))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
leng = [set() for i in range(N+1)]
res = 0
for _ in range(M):
  a,b = map(int, input().split())
  leng[a].add(b)
  leng[b].add(a)
def check(arr):
  for i in range(N-1):
    if arr[i+1] not in leng[arr[i]]:
      return False
  return True

import itertools
for i in itertools.permutations([x for x in range(2,N+1)]):
  if check([1]+list(i)):
    res += 1
print(res)

Submission status: Accepted

Solution code:
import collections
import copy

def dfs(i,basho,memo):
    global ans
    #print(i,basho,memo)
    if memo[basho]==1:
        return
    memo[basho]=1
    if i == n:
        if sum(memo)==n:
            ans += 1
        return
    tmp = collections.Counter(graph[basho])
    #print(tmp)
    for next_basho in tmp.keys():
        copy_memo = copy.copy(memo)
        dfs(i+1,next_basho,copy_memo)

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

memo = [0 for i in range(n+1)]
ans = 0
dfs(1,1,memo)
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
sys.setrecursionlimit(10**6)

N,M=map(int,input().split())
tmp=[x for x in range(1,N)]
Cases=itertools.permutations(tmp)
G=[[] for _ in range(N)]
seen=[0]*N

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

def solve(v,case,cnt,N):
    if cnt==N-1: return True
    for nv in G[v]:
        if nv==case[cnt]:
            return solve(nv,case,cnt+1,N)
    return False

ans=0
for case in Cases:
    if solve(0,case,0,N): ans+=1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
adj = [set() for i in range(N+1)]
for i in range(M):
	u, v = map(int,input().split())
	adj[u].add(v)
	adj[v].add(u)

def good(p):
	for i in range(N-1):
		if p[i+1] not in adj[p[i]]:
			return False
	return True

ans = 0

from itertools import permutations
for p in permutations(range(2,N+1)):
	if good([1]+list(p)):
		ans += 1

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# 13:50 -> 

class Node():
    def __init__(self, idx):
        self.idx = idx
        self.next_node = []
    
    def add_node(self, node):
        self.next_node.append(node)

N, M = map(int, input().split())
nodes = {i:Node(i) for i in range(1,N+1)}

for m in range(M):
    a,b = map(int, input().split())
    nodes[a].add_node(nodes[b])
    nodes[b].add_node(nodes[a])

def permutation_search(idxs, now_idx):
    if len(idxs) == 0:
        return 1

    num = 0
    for i in range(len(idxs)):
        next_idx = idxs[i]
        next_idxs = idxs[:i]+idxs[i+1:]
        if next_idx in [node.idx for node in nodes[now_idx].next_node]:
            num += permutation_search(next_idxs, next_idx)
    
    return num

total = permutation_search([i for i in range(2,N+1)], 1)

print(total)

Submission status: Accepted

Solution code:
import itertools
from collections import deque

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

p = [i for i in range(1,N)]
q = list(itertools.permutations(p))

s = deque()
for i in range(len(q)):
    x = 0
    flag = 0
    for y in q[i]:
        if table[x][y] == 0:
            flag = 1
            break
        x = y
    if flag == 0:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
root=[[] for _ in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    root[a].append(b)
    root[b].append(a)
s=[0]*(n+1)
s[0]=1
s[1]=1
ans=0
def f(a,x):
    global ans
    for i in root[a]:
        if x[i]==0:
            x[i]=1
            f(i,x)
            x[i]=0
    if x.count(1)==n+1:
        ans+=1
f(1,s)
print(ans)

Submission status: Accepted

Solution code:
def dfs(v, used):
  if not False 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

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

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

print(dfs(0, used))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
road=[[] for _ in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    road[a].append(b)
    road[b].append(a)
dp=[[0]*(n+1) for _ in range(2**n)]
dp[1][1]=1
for i in range(1,2**n):
    for j in range(1,n+1):
        for k in road[j]:
            if not (i>>(k-1))&1:
                dp[i+2**(k-1)][k]+=dp[i][j]
print(sum(dp[2**n-1]))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
#隣接リスト
graph=[[0]*n for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  graph[a-1][b-1]=1
  graph[b-1][a-1]=1


def dfs(v,visited):
  #print("v",v,"visited",visited)
  if not False in visited:
    #print("visited",visited,"end")
    return 1
  count=0
  for i in range(n):
    if not graph[v][i]:continue
    if visited[i]:continue
    
    visited[i]=True
    count+=dfs(i,visited)
    visited[i]=False
  return count

# 到達したかどうかlist（Falseは未到達、Trueは到達済み）
visited=[False] *(n)
visited[0]=True
print(dfs(0,visited))
#print("visited",visited)
#print("graph",graph)

Submission status: Accepted

Solution code:
import numpy as np
import itertools
import queue

def accept_input():
    N,M = map(int,input().split())
    G = {}
    for _ in range(M):
        a,b = map(int,input().split())
        if a not in G:
            G[a] = [b]
        else:
            G[a].append(b)
        if b not in G:
            G[b] = [a]
        else:
            G[b].append(a)
    return N,M,G


def widthsearch(q):
    global curvisited
    movelist = [(0,1),(0,-1),(1,0),(-1,0)] 
    lastplace = ((0,0),0)
    cur = 0
    while curvisited < H*W:
        q1 = queue.Queue()
        cur += 1
        while not q.empty():
            pack = q.get()
            y = pack[0][0]
            x = pack[0][1]
            num = pack[1]
            for move in movelist:
                if y+move[0] == -1 or y + move[0] == H or x+move[1] == -1 or x + move[1] == W:
                    continue
                elif visitedlist[y+move[0]][x+move[1]] == 1:
                    continue
                elif S[y+move[0]][x+move[1]] == "#":
                    continue
                else:
                    visitedlist[y+move[0]][x+move[1]] = 1
                    curvisited += 1
                    q1.put(((y+move[0],x+move[1]),num+1))
            if curvisited == H*W:
                break
        q = q1
    return cur

N,M,G = accept_input()
l = []
for i in range(2,N+1):
    l.append(i)
al = 0
for comb in itertools.permutations(l, N-1):
    if comb[0] not in G[1]:
        continue
    for i in range(0,N-2):
        if comb[i+1] not in G[comb[i]]:
            break
    else:
        al += 1
print(al)

Submission status: Accepted

Solution code:
def dfs(start,path):
    res = 0
    path.append(start)
    if len(path) == N:
        res += 1
        return res
    for i in graph[start]:
        if i not in path:
            res += dfs(i,path)
            path.pop()
    return res

N, M = map(int, input().split())
graph = [[] for _ 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)
print(dfs(0,[]))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
root=[[] for _ in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    root[a].append(b)
    root[b].append(a)
s=[0]*(n+1)
s[0]=1
s[1]=1
ans=0
def f(a,x):
    global ans
    for i in root[a]:
        if x[i]==0:
            z=[x[j] for j in range(n+1)]
            z[i]=1
            f(i,z)
    if x.count(1)==n+1:
        ans+=1
f(1,s)
print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

N,M = map(int,readline().split())
G = [[] for i in range(N)]

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

stack = []
stack.append([0, set()])
ans = 0
while stack:
  v, visited = stack.pop()
  visited.add(v)
  if len(visited) == N:
    ans += 1
    continue
  for child in G[v]:
    if child in visited:
      continue
    visited_c = visited.copy()
    stack.append([child, visited_c])
  
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

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

graph = [[False]*(N+1) for i in range(N+1)]

for i ,j in Alist:
  graph[i][j] = True
  graph[j][i] = True

route = permutations(range(1,N+1))

count = 0
for i in route:
  flag = True
  if i[0] !=1:
    continue
  for j in range(N-1):
    if graph[i[j]][i[j+1]] == False:
      flag = False
      break
  
  if flag == True:
    count += 1

print(count)

Submission status: Accepted

Solution code:
from itertools import permutations

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

graph = [[False]*(N+1) for _ in range(N+1)]

for i,j in l:
    graph[i][j] = True
    graph[j][i] = True

pattern = permutations(range(1,N+1))

cnt = 0
for i in pattern:
    flag = True
    if i[0] != 1:
        continue
    for j in range(N-1):
        if graph[i[j]][i[j+1]] == False:
            flag = False
            break
    
    if flag:
        cnt += 1

print(cnt)

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
import itertools
n,m = map(int,input().split())
tf = [[False for _ in range(n)] for _ in range(n)]
for _ in range(m):
  ai,bi = map(int,input().split())
  ai -= 1
  bi -= 1
  tf[ai][bi] = True
  tf[bi][ai] = True
l = [i for i in range(1,n)]
c = 0
for v in itertools.permutations(l,n-1):
    if tf[0][v[0]] == True:
      flag = True
      for i in range(n-2):
        if tf[v[i]][v[i+1]] == False:
          flag = False
          break
      if flag:
        c += 1
print(c)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

"""
全ての場所を一度だけ通り巡回する通りの数
bit(1 << N)を小さい順から探索する
①bit & (1 << 0)
最初に0を踏んでないということだから飛ばす
②現在の場所sを探すためN個探索する
③次の場所tを探すためN個探索する
④渡すdpする
"""

N, M = getNM()
G = [[0] * N for i in range(N)]
for i in range(M):
    a, b = getNM()
    G[a - 1][b - 1] = 1 # a ~ bのエッジが存在する
    G[b - 1][a - 1] = 1

# 状態bitから次の状態へ渡すdpするというのはよくやる
# [0](001) → [0, 1](011) → [0, 1, 2](111)
#          → [0, 2](101) → [0, 1, 2](111)
def counter(sta):
    # dp[bit][i]これまでに踏んだ場所がbitであり、現在の場所がiである
    dp = [[0] * N for i in range(1 << N)]
    dp[1 << sta][sta] = 1

    for bit in range(1, 1 << N):
        if not bit & (1 << sta):
            continue
        # s:現在の場所
        for s in range(N):
            # sを踏んだことになっていなければ飛ばす
            if not bit & (1 << s):
                continue
            # t:次の場所
            for t in range(N):
                # tを過去踏んでいない and s → tへのエッジがある
                if (bit & (1 << t)) == 0 and G[s][t]:
                    dp[bit|(1 << t)][t] += dp[bit][s]

    return sum(dp[(1 << N) - 1])

print(counter(0))

Submission status: Accepted

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

path = [[0]*(N+1) for _ in range(N+1)]

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

visited = [0]*(N+1)

def dfs(now,depth):
    if visited[now]:
        return 0
    if depth == N:
        return 1 # 最後まで探索したらはじめて+1
    
    visited[now] = 1
    
    total_paths = 0
    
    for i in range(1,N+1):
        if path[now][i]:
            total_paths += dfs(i, depth + 1)
            
    visited[now] = 0
    
    return total_paths

print(dfs(1,1))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import itertools

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

graph= [[False]*N for i in range(N)]

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

lst = [i-1 for i in range(N)]
cnt = 0

for v in itertools.permutations(lst, N):
    if v[0] != 0:
        continue
    for i in range(N-1):
        if graph[v[i]][v[i+1]] == False:
            break
        if i == N-2:
            cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import itertools

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

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

nlis=[i for i in range(n)]
perm=list(itertools.permutations(nlis))

for one_case in perm:
    if one_case[0]==0:
        cou=0
        for i in range(n-1):
            if one_case[i+1] in emp[one_case[i]]:
                cou+=1
            
            if cou==n-1:
                count+=1
print(count)

Submission status: Accepted

Solution code:
from itertools import permutations

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

for i in range(M):
  ab = list(map(int,input().split()))
  AB[i] = ab

count = 0
nums = [i for i in range(1,N+1)]
pers =permutations(nums,N)
for i in pers:
  if i[0] == 1:
    flag1 = 0
    for j in range(N-1):
      flag2 = False
      for k in range(M):
        if (i[j] == AB[k][0] and i[j+1] == AB[k][1]) or (i[j] == AB[k][1] and i[j+1] == AB[k][0]):
          flag2 = True
          #print(i,i[j],i[j+1],AB[k])
      if flag2:
        flag1 += 1
    if flag1 == N-1:
      #print(i)
      count += 1
print(count)

Submission status: Accepted

Solution code:
import math
import itertools

# 与えられた数値の桁数と桁値の総和を計算する.
def calc_digit_sum(num):
    digits = sums = 0
    while num > 0:
        digits += 1
        sums += num % 10
        num //= 10
    return digits, sums


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


answer = 0
routes = [c for c in itertools.permutations(range(0, n), n) if c[0] == 0]
for route in routes:
    seen = set()

    is_one_stroke = True
    for index in range(len(route) - 1):
        node = route[index]

        seen.add(node)
        next_node = route[index+1]
        if not graph[node] or next_node not in graph[node] or next_node in seen:
            is_one_stroke = False
            break

    if is_one_stroke:
        answer += 1

print(answer)

Submission status: Accepted

Solution code:
import itertools
N, M = map(int, input().split())
p=[[0]*N for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    p[a-1][b-1]=1
    p[b-1][a-1]=1
cnt=0
a=[i for i in range(N)]

for i in itertools.permutations(a):
    flag=0
    if i[0]==0:
        for j in range(1,N):
            if p[i[j]][i[j-1]]!=1:
                flag=1
        if flag==0:
            cnt+=1
    
print(cnt)

Submission status: Accepted

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


#iから進める場所をリストにして保管
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):
    #lst(通過点)の数がN(頂点数)と等しくなったら探索終了（成功）
  if len(list) == N:
    return 1
  else:
    a = list[-1]
    #lstの最後尾（現在地）が次に進める場所をnextとしてリスト化
    #nextに以前通った場所が入っていないか確認
    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)

Submission status: Accepted

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


#iから進める場所をリストにして保管
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):
    #lst(通過点)の数がN(頂点数)と等しくなったら探索終了（成功）
  if len(list) == N:
    return 1
  else:
    a = list[-1]
    #lstの最後尾（現在地）が次に進める場所をnextとしてリスト化
    #nextに以前通った場所が入っていないか確認
    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)

Submission status: Accepted

Solution code:
N,M = [int(a) for a in input().split()]


#iから進める場所をリストにして保管
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):
    #lst(通過点)の数がN(頂点数)と等しくなったら探索終了（成功）
  if len(list) == N:
    return 1
  else:
    a = list[-1]
    #lstの最後尾（現在地）が次に進める場所をnextとしてリスト化
    #nextに以前通った場所が入っていないか確認
    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)

Submission status: Accepted

Solution code:
N,M = [int(a) for a in input().split()]


#iから進める場所をリストにして保管
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 search(lst):
    #lst(通過点)の数がN(頂点数)と等しくなったら探索終了（成功）
  if len(lst) == N:
    return 1
  else:
    a = lst[-1]
    #lstの最後尾（現在地）が次に進める場所をnextとしてリスト化
    #nextに以前通った場所が入っていないか確認
    next = [n for n in edges[a] if n not in lst]
    #次に進める場所がなくなったら探索終了（失敗）
    if len(next) == 0:
      return 0

    tot = 0
    #再帰でさらに探索
    for n in next:
      tot += search(lst + [n])

    return tot


ans = search([1])

print(ans)

Submission status: Accepted

Solution code:
N,M = [int(a) for a in 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 search(lst):
  if len(lst) == N:
    return 1
  else:
    a = lst[-1]
    next = [n for n in edges[a] if n not in lst]
    if len(next) == 0:
      return 0

    tot = 0
    for n in next:
      tot += search(lst + [n])
    
    return tot


ans = search([1])

print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m=map(int,input().split())
tbl=[[0]*n for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    tbl[a-1][b-1]=1
    tbl[b-1][a-1]=1
ans=0
l=[i+1 for i in range(n-1)]
for p in itertools.permutations(l,n-1):
    flag=True
    p=[0]+list(p)
    for i in range(n-1):
        if tbl[p[i]][p[i+1]]==0:
            flag=False
            break
    if flag:
      ans+=1
print(ans)

Submission status: Accepted

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

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


def dfs(v, seen):
    if seen == [1] * N:
        return 1
    
    res = 0
    for nv in to[v]:
        if not seen[nv]:
            seen[nv] = 1
            res += dfs(nv, seen)
            seen[nv] = 0
    return res


def main():
    seen = [0] * N
    seen[0] = 1
    print(dfs(0, seen))    


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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


res = 0
def dfs(v, seen):
    global res
    if seen == [1] * N:
        res += 1
        return
    for nv in to[v]:
        if not seen[nv]:
            seen[nv] = 1
            dfs(nv, seen)
            seen[nv] = 0


def main():
    seen = [0] * N
    seen[0] = 1
    dfs(0, seen)
    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import copy
from collections import deque

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

e = [[] for i in range(n)]
for i in range(m):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    e[a].append(b)
    e[b].append(a)
visited = [False]*n
visited[0] = True
d = deque([[0, visited]])

cnt = 0
while d:
    f, visited = d.pop()
    for t in e[f]:
        v = copy.deepcopy(visited)
        if not v[t]:
            v[t] = True
            if False in v:
                d.append([t, v])
            else:
                cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
from itertools import permutations

n,m = map(int,input().split())
v = [set() for _ in range(n)]
for i in range(m):
    ai,bi = map(int,input().split())
    v[ai-1].add(bi-1)
    v[bi-1].add(ai-1)

ans = 0
for ci in permutations(range(n)):
    if not ci[0]:
        for i in range(n-1):
            if not (ci[i+1] in v[ci[i]]):
                break
        else:
            ans += 1
print(ans)

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())
  a-=1
  b-=1
  G[a].append(b)
  G[b].append(a)
ans=0
for P in permutations(range(n),n):
  f=1
  if P[0]!=0:
    continue
  for i in range(n-1):
    if  P[i+1] in G[P[i]]:
      f*=1
    else:
      f*=0
  if f==1:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

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

ans = 0
for r in permutations(range(N)):
    if r[0] != 0: break
    factor = 1
    for i in range(len(r)-1):
        factor *= root[r[i]][r[i+1]]
    ans += factor
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
n,m=map(int,input().split())
lis=[i for i in range(1,n+1)]
nm=[[] for _ in range(n+1)]
for _ in range(m):
    a,b=map(int,input().split())
    nm[a].append(b)
    nm[b].append(a)
count=0
for i in permutations(lis):
    if i[0]==1:
        temp=nm[1]
        for j in range(n-1):
            if not i[j+1] in set(temp):
                break
            temp=nm[i[j+1]]
        else:
            count+=1
print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import permutations
N,M=map(int,input().split())
mat = [[0]*(1+N) for _ in range(1+N)]
for _ in range(M):
    a,b = map(int,input().split())
    mat[a][b] = 1
    mat[b][a] = 1
ans = 0
for tpl in permutations(range(2, 1+N), N-1):
    is_ok = 1
    tpl = [1] + list(tpl)
    for i in range(N-1):
        if mat[tpl[i]][tpl[i+1]] == 0:
            is_ok = 0
            break
    
    if is_ok:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)

N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for i in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    graph[a].append(b)
    graph[b].append(a)
def dfs(cur, visited):
    if visited == (1 << N) - 1:
        return 1
    res = 0
    for to in graph[cur]:
        if not visited & (1 << to):
            res += dfs(to, visited | (1 << to))
    return res
print(dfs(0, 1))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)

N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for i in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    graph[a].append(b)
    graph[b].append(a)
def dfs(cur, visited):
    if visited == (1 << N) - 1:
        return 1
    res = 0
    for to in graph[cur]:
        if not (visited >> to) & 1:
            res += dfs(to, visited | (1 << to))
    return res
print(dfs(0, 1))

Submission status: Accepted

Solution code:
import itertools

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

#繋がっている頂点リスト
a_list = []
for j in range(m) :
    a = list(map(int, input().split()))
    a_list.append(a)
a_list.sort()

#道順リスト(最初が1に限る)
b_list = [k for k in itertools.permutations([l for l in range(1, n + 1)]) if k[0] == 1]

#道順リストの中で頂点リストが含まれているもの
cnt = 0
for x in b_list :
    tf_list = []
    for y in range(n - 1) :
        tf_list.append([x[y], x[y + 1]] in a_list or [x[y + 1], x[y]] in a_list)
    
    if all(tf_list) == True :
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
from typing import List, Tuple


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


def osp(n: int, g: List[Tuple[int, int]]) -> int:
    v = [False] * n
    g = set(g)

    return dfs(0, v, n, g)


def dfs(i, v, n, g):
    v[i] = True
    if all(v):
        v[i] = False
        return 1

    cnt = 0
    for j in range(n):
        if v[j]:
            continue
        if not ((i + 1, j + 1) in g or (j + 1, i + 1) in g):
            continue
        cnt += dfs(j, v, n, g)

    v[i] = False
    return cnt


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from typing import List, Tuple


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


def osp(n: int, g: List[Tuple[int, int]]) -> int:
    v = [False] * n

    return dfs(0, v, n, g)


def dfs(i, v, n, g):
    v[i] = True
    if all(v):
        v[i] = False
        return 1

    cnt = 0
    for j in range(n):
        if v[j]:
            continue
        if not ((i + 1, j + 1) in g or (j + 1, i + 1) in g):
            continue
        cnt += dfs(j, v, n, g)

    v[i] = False
    return cnt


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from typing import List, Tuple


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


def osp(n: int, g: List[Tuple[int, int]]) -> int:
    graph = [[False] * n for _ in range(n)]
    for a, b in g:
        graph[a - 1][b - 1] = True
        graph[b - 1][a - 1] = True
    v = [False] * n

    return dfs(0, v, n, graph)


def dfs(i, v, n, graph):
    v[i] = True
    if all(v):
        v[i] = False
        return 1

    cnt = 0
    for j in range(n):
        if v[j]:
            continue
        if not graph[i][j]:
            continue
        cnt += dfs(j, v, n, graph)

    v[i] = False
    return cnt


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Graph = [[] for _ in range(N)]
for a,b in Edge:
    Graph[a-1].append(b-1)
    Graph[b-1].append(a-1)

seen = set()
def dfs(v):
    seen.add(v)
    if len(seen) == N:
        seen.remove(v)
        return 1
    Res = [dfs(nv) for nv in Graph[v] if not nv in seen]
    seen.remove(v)
    return sum(Res)

print(dfs(0))

Submission status: Accepted

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

Graph = [[] for _ in range(N)]
for a,b in Edge:
    Graph[a-1].append(b-1)
    Graph[b-1].append(a-1)

seen = set()
def dfs(v):
    global Graph, seen
    seen.add(v)
    if len(seen) == N:
        seen.remove(v)
        return 1
    Res = [dfs(nv) for nv in Graph[v] if not nv in seen]
    seen.remove(v)
    return sum(Res)

print(dfs(0))