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:
def bfs(n, node, prev, visited, graph):
    visited.append(node)
    if len(visited) == n:
        return 1

    res = 0
    for edge in graph[node]:
        if edge == prev:
            continue
        if edge in visited:
            continue
        res += bfs(n, edge, node, visited[:], graph)
    # print(visited)
    return res


def main():
    n, m = map(int, input().split())
    graph = [[] for _ in range(n+1)]
    for _ in range(m):
        i, j = map(int, input().split())
        graph[i].append(j)
        graph[j].append(i)

    ans = bfs(n, 1, 0, [], graph)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import permutations
from collections import defaultdict
n, m = map(int, input().split())
routes = permutations(range(2, n+1), n-1)
count = 0

edges = defaultdict(list)

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

for route in routes:
    goal = True
    now_node = 1
    for way_index in range(len(route)):
        if not route[way_index] in edges[now_node]:
            goal = False
        now_node = route[way_index]
    if goal:
        count += 1
print(count)

Submission status: Accepted

Solution code:
import itertools
n, m = map(int, input().split())
ab_list = [tuple(map(int, input().split())) for _ in range(m)]

path_list = sorted(iter for iter in itertools.permutations(range(2, n+1), n-1))

counter = 0

for path_i in path_list:
  path = (1, )+path_i
  
  result_list = [True for s_e in zip(path, path[1:]) if tuple(sorted(s_e)) in ab_list]
  
  if sum(result_list) == len(path)-1: counter += 1
    
print(counter)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
G = [[] for i 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(node, prev, visited):
    visited.append(node)
    if len(visited) == N:
        return 1
 
    res = 0
    for edge in G[node]:
        if edge == prev:
            continue
        if edge in visited:
            continue
        res += dfs(edge, prev, visited[:])
 
    return res


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

Submission status: Accepted

Solution code:
import array
import itertools
from collections import defaultdict, deque


def log(s):
    # print("| " + str(s), file=sys.stderr)
    pass


def output(x):
    print(x, flush=True)


def input_ints():
    return map(int, input().split())


def solve():
    num_nodes, num_edges = tuple(input_ints())

    edges = [tuple(input_ints()) for _ in range(num_edges)]

    navigability = defaultdict(lambda: [])

    for e in edges:
        navigability[e[0]].append(e[1])
        navigability[e[1]].append(e[0])

    def solve1(path, result):
        if len(path) == num_nodes:
            result.append(path)
            return

        for m in navigability[path[-1]]:
            if m not in path:
                solve1(path + [m], result)

        return result

    return solve1([1], [])


def main():
    print(len(solve()))


main()

Submission status: Accepted

Solution code:
import array
import itertools
from collections import defaultdict, deque


def log(s):
    # print("| " + str(s), file=sys.stderr)
    pass


def output(x):
    print(x, flush=True)


def input_ints():
    return map(int, input().split())


def solve():
    num_nodes, num_edges = tuple(input_ints())

    edges = [tuple(input_ints()) for _ in range(num_edges)]

    navigatility = defaultdict(lambda: [])

    for e in edges:
        navigatility[e[0]].append(e[1])
        navigatility[e[1]].append(e[0])

    queue = deque()
    queue.append([1])
    result = []

    while queue:
        path = queue.popleft()

        if len(path) == num_nodes:
            result.append(path)
        else:
            n = path[-1]

            for m in navigatility[n]:
                if m not in path:
                    queue.append(path + [m])

    return result


def main():
    print(len(solve()))


main()

Submission status: Accepted

Solution code:
import itertools

n, m = map(int, input().split(" "))
path_city = [[] for _ in range(n)]
for _ in range(m):
  a, b = map(int, input().split(" "))
  path_city[a - 1].append(b - 1)
  path_city[b - 1].append(a - 1)
list_city = [i for i in range(1, n)]
list_order_city = itertools.permutations(list_city)

result = 0
for one_order in list_order_city:
  pre_city = 0
  flag_con = True
  for one_city in one_order:
    if pre_city not in path_city[one_city]:
      flag_con = False
      break
    pre_city = one_city
  if flag_con:
    result += 1
print(result)

Submission status: Accepted

Solution code:
from collections import deque

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

def dfs(p, done):
    curr = p[-1]
    nodes = n[curr]
    paths = list(set(nodes) - set(p))
    for path in paths:
        p.append(path)
        dfs(p, done)
    if not paths:
        done.append(list(p))
    del p[-1]
        
def main():
    for _ in range(M):
        a, b = map(lambda s: int(s) - 1, input().split())
        n[a].append(b)
        n[b].append(a)
    done = []
    p = deque([0])
    dfs(p, done)
    ans = sum(1 for li in done if len(li) == N)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

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

# 辺が存在する箇所にフラグ1を置く
edge = [[0 for _ in range(N)] for _ in range(N)]
for idx in range(M):
    edge[ab[idx][0]-1][ab[idx][1]-1] = 1
    edge[ab[idx][1]-1][ab[idx][0]-1] = 1


# 頂点1から始まる全通りのパスについて実現可能かを調べる
path = list(range(2,N+1))
path = list(itertools.permutations(path))
ans = 0

for out_idx in range(len(path)):
    path[out_idx] = (1,) + path[out_idx]
    miss_flg = 0
    for in_idx in range(1, len(path[out_idx])-1):
        if edge[path[out_idx][in_idx-1]-1][path[out_idx][in_idx]-1] == 0 or edge[path[out_idx][in_idx]-1][path[out_idx][in_idx+1]-1] == 0:
            miss_flg = 1
            break
    if miss_flg == 0:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N,M= map(int,input().split())
list=[[False for i in range(N)] for j in range(N)]
for i in range (M):
    a,b=map(int,input().split())
    list[a-1][b-1]=True
    list[b-1][a-1]=True
count = 0
flag = [False for i in range(N)]
flag[0]=True

def depth_search (now,flag):
    global count
    tmp_flag = []
    tmp_flag += flag
    tmp_flag[now] = True
    if(False in tmp_flag):
        for i in range(1,N):
            if(list[now][i] and not tmp_flag[i]):
                depth_search(i,tmp_flag)
    else:
        count += 1

for i in range(1,N):
    if(list[0][i]):
        depth_search(i,flag)
print(count)

Submission status: Accepted

Solution code:
from itertools import permutations

N, M = map(int, input().split())
AB = set([tuple(sorted(map(int, input().split()))) for _ in range(M)])

answer = 0
for pattern in permutations(range(2, N+1), N-1):
    pattern = [1] + list(pattern)
    for i in zip(pattern[:-1], pattern[1:]):
        if tuple(sorted(i)) not in AB:
            break
    else:
        answer += 1
print(answer)

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())
    to[a-1].append(b-1)
    to[b-1].append(a-1)
    

def dfs(v, n, visited):
    #print(visited)
    all_visited = True
    for i in visited:
        if not i:
            all_visited = False
            break
    if all_visited:
        return(1)
    
    ret = 0
    for i in range(1, n):
        #print(ret)
        if to[i].count(v) == 0:
            continue
        if visited[i]:
            continue
        visited[i] = True
        ret += dfs(i, n, visited)
        visited[i] = False
    return(ret)

visited = [False for _ in range(n)]
visited[0] = True
print(dfs(0, n ,visited))

Submission status: Accepted

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

count = 0
seq = list(range(1,n))
permutation = itertools.permutations(seq)
for l in permutation:
    t = 0
    flag = 0
    for i in l:
        c = to[i].count(t)
        if c == 0:
            flag = 1
            break
        t = i
    if flag == 0:
        count += 1
    flag = 0

print(count)

Submission status: Accepted

Solution code:
from itertools import permutations

n, m = map(int, input().split())
ab = []
for i in range(m):
    ai, bi = map(int, input().split())
    ab.append([ai, bi])
ab = sorted(ab)

per_origin = []
for i in range(2, n+1):
    per_origin.append(i)

res = 0
for per in permutations(per_origin, len(per_origin)):
    root = [1] + list(per)
    flag = 0
    for i in range(n-1):
        if [root[i], root[i+1]] not in ab and [root[i+1], root[i]] not in ab:
            flag = 1
            break
    if not flag:
        res += 1

print(res)

Submission status: Accepted

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

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

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

print(ans)

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split(" ")))
path = [tuple(map(int,input().split(" "))) for _ in range(M)]
path += [(item[1], item[0]) for item in path]
visited = [False for _ in range(N)]
visited[0] = True

def dfs(v_, visited):
    if not (False in visited):
        return 1
    ret = 0
    v = v_ + 1 
    for i_ in range(N):
        i = i_ + 1
        if not ((i, v) in path):
            continue
        if visited[i_]:
            continue
        visited[i_] = True
        ret += dfs(i_, visited)
        visited[i_] = False
        
    return ret
print(dfs(0, visited))

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:
import itertools
N,M = map(int,input().split())
edges = {tuple(map(int,input().split())) for i in range(M)}
ans = 0
for i in itertools.permutations(range(2,N+1),N-1):
    l = [1]+list(i)
    ans += all(tuple(sorted(edge)) in edges for edge in zip(l,l[1:]))
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
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)

    
ans=0

for i in permutations(range(1,n+1)):
    if i[0]!=1:
        continue
    for j in range(n-1):
        if i[j+1] not in graph[i[j]]:
            break
    else:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import itertools
import math
def main():
    N,M = map(int,input().split())
    root = [[] for _ in range(N)]
    ans = math.factorial(N-1)
    for i in range(M):
        a,b = map(int,input().split())
        root[a-1].append(b-1)
        root[b-1].append(a-1)

    for i in itertools.permutations([j for j in range(1,N)]):
        if i[0] not in root[0]:
            ans -= 1
        else:
            for j in range(N-2):
                if i[j+1] not in root[i[j]]:
                    ans -= 1
                    break

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def resolve():
    import sys
    sys.setrecursionlimit(10**6)
    
    N,M = map(int,input().split())
    ab =[map(int,input().split()) for _ in range(M)]
    branch = [[] for _ in range(N)]
    for a,b in ab:
        branch[a-1].append(b-1)
        branch[b-1].append(a-1)
    
    bit = 0
    count = 0
    def walk(p):
        nonlocal bit,N
        bit |= (1 << p)
        if bit == 2 ** N - 1:
            nonlocal count
            count += 1
        for n in branch[p]:
            if not(bit & (1 << n)):
                walk(n)
        bit &= ~(1 << p)

    walk(0)
    print(count)
resolve()

Submission status: Accepted

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


def dfs(v, seen, res):
    seen[v] = True
    if all(seen):
        res += 1

    for i in edge[v]:
        if not seen[i]:
            tmp = [tf for tf in seen]
            res = dfs(i, tmp, res)

    return res


visited = [False]*n
ans = dfs(0, visited, 0)
print(ans)

Submission status: Accepted

Solution code:
# ABC054 C One-stroke Path
N,M = map(int, input().split())

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

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

cnt = 0

def DFS(x):

    global cnt
    global reached

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

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

        else:
            DFS(i)

    reached[x] = False

DFS(0)
print(cnt)

Submission status: Accepted

Solution code:
import itertools

n,m=map(int,input().split())
uselist=[]
for _ in range(m):
    ad=list(map(int,input().split()))
    uselist.append(ad)
cnt=0
for i in itertools.permutations(range(1,n+1)):
    if i[0]==1:
        flag=True
        for j in range(n-1):
            if [i[j],i[j+1]]  not in uselist and [i[j+1], i[j]] not in uselist:
                flag =False
                break
            else:
                continue
        if flag==True:
            cnt+=1
        else:
            continue
        
print(cnt)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
#ts=time.time()
#sys.setrecursionlimit(10**6)
input=sys.stdin.readline
show_flg=False
#show_flg=True

n,m=MI()
g=[[] for _ in range(n)]
t=1<<n
mask=t-1
for i in range(m):
    a,b=LI_()
    g[a].append(b)
    g[b].append(a)

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

for s in range(t):
    for h in range(n):
        if s&(1<<h)==0:
            #show('pas1')
            continue
        for f in g[h]:
            if s&(1<<f)==0:
                #show('pas2')
                continue
            
            dp[s][h]+=dp[s-(1<<h)][f]
            show('!dp','s,h,f',bin(s+t)[3:],h,f,'|',dp[s][h],dp[s-(1<<h)][f])

ans=0
for i in range(1,n):
    ans+=dp[t-1][i]

print(ans)
show(g)
show(dp)

Submission status: Accepted

Solution code:
import numpy as np

n, m = map(int, input().split())
g = [[] for i in range(n + 1)]
visited = np.zeros(n, dtype=np.bool)
ans = 0


def dfs(now):
    global ans
    if (visited == True).all():
        ans += 1
    for i in range(len(g[now])):
        next_n = g[now][i]
        if visited[next_n - 1] == False:
            visited[next_n - 1] = True
            dfs(next_n)
            visited[next_n - 1] = False


for i in range(m):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)
# print(g)
visited[0] = True
dfs(1)
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
r = [set() for _ in range(N+1)]
for _ in range(M):
    n1, n2 = map(int, input().split())
    r[n1].add(n2)
    r[n2].add(n1)

from itertools import permutations as p
c = 0
kumis = p(range(2, N+1))
for kumi in kumis:
    prev = 1
    for k in kumi:
        if k not in r[prev]:
            break
        prev = k
    else:
        c += 1
print(c)

Submission status: Accepted

Solution code:
import itertools

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)
nodes = [i for i in range(N)]
count = 0
for node_order in itertools.permutations(nodes, N):
    if node_order[0] != 0:
        break
    for i in range(N-1):
        if not node_order[i+1] in graph[node_order[i]]:
            break
    else:
        count += 1
print(count)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(M)]
import sys
sys.setrecursionlimit(100000000)

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

def dfs(x,s,flags):
    vlist = adj[x]
    flags = list(flags)
    flags[x] = False
    flags = tuple(flags)
    if sum(flags) == 0:
        return 1
    s = 0
    for v in vlist:    
        if flags[v]:
            s += dfs(v,s,flags)
    return s        

Flag = [True] * N
Flag[0] = False
ans = dfs(0,0,tuple(Flag))
print(ans)

Submission status: Accepted

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

for i in range(m):
    a,b=map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)
    
ans=0
for i in itertools.permutations(range(1,n+1)):
    if i[0]!=1:
        continue
    for j in range(n-1):
        if i[j+1] not in edge[i[j]]:
            break
    else:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
def dfs(p, ans):
    c[p] = False
    terminal = True
    for x in e[p]:
        if c[x]:
            terminal = False
            ans = dfs(x, ans)
    
    if terminal:
        if not any(c):
            ans += 1
    c[p] = True
    
    return ans

(n,m), *s = [list(map(int, s.split())) for s in open(0)]

e = [[] for _ in range(n)]
for i,j in s:
    e[i-1].append(j-1)
    e[j-1].append(i-1)

c = [True]*n

ans = dfs(0, 0)

print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
E = [set() for _ in range(N)]
for i in range(M):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  E[a].add(b)
  E[b].add(a)
#print(E)

def dfs(v,c):
  if c == N:
    return 1
  res = 0
  for u in E[v]:
    if not visited[u]:
      visited[u] = True
      res += dfs(u,c+1)
      visited[u] = False
  return res

visited = [True] + [False for _ in range(N-1)]
print(dfs(0,1))

Submission status: Accepted

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

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

# E[i] := 頂点 i と結ばれている頂点の集合
E = [set() for _ in range(N+1)]
for _ in range(M):
    a,b = map(int, input().split())
    E[a].add(b)
    E[b].add(a)

ans = 0

# まだ訪れていない頂点を訪れていき、全て訪問できたら +1.
# 現在地 n, 次の候補の集合 nexts, 訪問済みの集合 visited
def dfs(n, nexts, visited):
    v = visited + [n]
    if len(v) == N:
        global ans
        ans += 1
    else:
        for i in nexts:
            dfs(i, set([j for j in E[i] if j not in v]), v)

def main():
    dfs(1, E[1], [])
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
cs = [[0] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    cs[a][b] = 1
    cs[b][a] = 1
visited = [False] * (n + 1)
visited[0] = visited[1] = True


def dfs(k):
    count = 0
    es = [i for i in range(n + 1) if cs[k][i] == 1 and not visited[i]]
    if len(es) == 0:
        return 1 if all(visited) else 0
    for i in es:
        visited[i] = True
        count += dfs(i)
        visited[i] = False
    return count


print(dfs(1))

Submission status: Accepted

Solution code:
import itertools as it

n, m = list(map(int,input().split()))
nodes = [[] for _ in range(n)] 
for i in range(m):
    ai, bi = list(map(int, input().split()))
    nodes[ai-1].append(bi-1)
    nodes[bi-1].append(ai-1)
cnt = 0
for perm in it.permutations(range(1,n),n-1):
    i = 0
    ok = True
    for j in perm:
        if j not in nodes[i]:
            ok = False
            break
        i = j
    if ok:
        cnt += 1
            
print(cnt)

Submission status: Accepted

Solution code:
# ABC054c
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
l = [set() for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    l[a].add(b)
    l[b].add(a)

visited = [False]*(n+1)


def dfs(i, cnt):
    #print(i, cnt)
    if (cnt == n):
        return 1
    ans = 0
    for j in l[i]:
        if (visited[j]):
            continue
        visited[j] = True
        ans += dfs(j, cnt + 1)
        visited[j] = False
    return ans


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

Submission status: Accepted

Solution code:
from itertools import permutations

N, M = map(int, input().split())
adj = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    adj[a][b] = 1
    adj[b][a] = 1

ans = 0
for seq in permutations(range(1, N + 1)):
    if seq[0] != 1:
        continue
    new = 1
    for i in range(1, N):
        if adj[seq[i - 1]][seq[i]] == 0:
            new = 0
    ans += new
print(ans)

Submission status: Accepted

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

# それぞれの要素のつながりを1で表現
A = [ [0 for _ in range(N)] for _ in range(N) ]

visited = [False]*N

for i in range(M):
    a, b = map(int, input().split())
    # インデックスのため -1する
    a -= 1
    b -= 1
    A[a][b] = 1
    A[b][a] = 1

def dfs(node, count):
    # 全てのノードが訪れられていたら ans+=1
    if all(visited):
        return count+1
    
    # 全てのノード間の繋がりでfor文
    for i in range(N):
        # nodeの繋がりがあるか判定。
        if A[node][i] == 0:
            continue
        # 見ているノードが訪れられているか判定。
        if visited[i]:
            continue
        
        # 見ているノード間の繋がりがあり、そのノードが訪れられていないとき。
        visited[i] = True
        count = dfs(i, count)
        # 探索前の状態に戻す
        visited[i] = False

    return count

# 開始地点
visited[0] = True

# 開始地点とcountを引数に
count = dfs(0, 0)

print(count)

Submission status: Accepted

Solution code:
from itertools import permutations 
n, m = map(int, input().split())

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

cnt = 0
for per in permutations(range(n)):
    Pth = True
    for i in range(n-1):
        if M[per[i]][per[i+1]] != 1 or per[0]!=0:
            Pth = False
            break
    if Pth:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
def slove():
    import sys
    import collections
    import copy
    input = sys.stdin.readline
    n, m = list(map(int, input().rstrip('\n').split()))
    ab = collections.defaultdict(list)
    for i in range(m):
        a, b = list(map(int, input().rstrip('\n').split()))
        ab[a] += [b]
        ab[b] += [a]
    td = collections.defaultdict(list)
    td[1]
    q = [[1, td]]
    ans = []
    while True:
        if len(q) != 0:
            p, d = q.pop()
            if len(d) != n:
                for v in ab[p]:
                    if v not in d:
                        td = copy.deepcopy(d)
                        td[v]
                        q.append([v, td])
            else:
                ans.append([d])
        else:
            print(len(ans))
            exit()


if __name__ == '__main__':
    slove()

Submission status: Accepted

Solution code:
from collections import deque

def run():
  N, M = map(int, input().split())
  vertex_dict = {}
  for m in range(M):
    a, b = map(int, input().split())
    vertex_dict.setdefault(a, []).append(b)
    vertex_dict.setdefault(b, []).append(a)
  all_m_list = range(M)
  q = deque([])
  q.append((1, [1]))
  total = 0
  while True:
    #print(q)
    if len(q) == 0: break
    now_vertex, visited_list = q.popleft()
    if len(visited_list) == N:
      total += 1
      continue
    next_list = vertex_dict[now_vertex]
    for next_vertex in next_list:
      for visited_vertex in visited_list:
        if next_vertex == visited_vertex: break
      else:
        q.append((next_vertex, visited_list+[next_vertex]))
  print(total)
        
  
if __name__ == '__main__':
  run()

Submission status: Accepted

Solution code:
from itertools import permutations as per
ty,he=map(int,input().split())
l=[set(map(int,input().split())) for i in range(he)]
ans=0
for g in per(range(2,ty+1)):
  co=[1]+list(g)
  for sd in zip(co,co[1:]):
    if set(sd) not in l:break
  else:ans+=1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
from collections import deque as dq
N, M = map(int, input().split())
e = dd(list)
for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)
dp = [[0] * (N + 1) for _ in range(2 ** N)]
dp[1][1] = 1
Q = dq([])
Q.append((1, 1))
visited = set()
visited.add((1, 1))
while len(Q):
  i, j = Q.popleft()
  for p in e[j]:
    temp = i ^ (1 << (p - 1))
    if temp > i:
      #print(i, p, temp)
      dp[temp][p] += dp[i][j]
      if not (temp, p) in visited:
        Q.append((temp, p))
        visited.add((temp, p))
print(sum(dp[2 ** N - 1]))

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

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

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

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

#print(A)

def dfs(node, count):
    if all(visited):
        return count+1

    for i in range(N):
        if A[node][i] == 0:
            continue
        if visited[i]:
            continue

        visited[i] = True
        count = dfs(i, count)
        visited[i] = False

    return count


visited[0] = True
count = dfs(0, 0)
print(count)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
G = [[0]*(N+1) for i in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    G[a][b] = 1
    G[b][a] = 1
    
import itertools
zero = [i for i in range(2,N+1)]
ans = 0
for i in itertools.permutations(zero,N-1):
    flag = 1
    if G[1][i[0]]!=1:
        flag = 0
    for j in range(len(i)-1):
        if G[i[j]][i[j+1]] != 1:
            flag = 0
    if flag == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
n, m = map(int, input().split())
edges = {tuple(map(int, input().split())) for _ in range(m)}

ans = 0
for i in permutations(range(2, n+1), n-1):
    load = [1]+list(i)
    ans += sum(1 for edge in zip(load, load[1:])
               if tuple(sorted(edge)) in edges) == n-1
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]

ans = 0
for i in permutations(range(2, n+1), n-1):
    load = [1]+list(i)
    ans += sum(1 for edge in zip(load, load[1:])
               if tuple(sorted(edge)) in edges) == n-1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
import itertools

def main():
    n, m = map(int, input().strip().split())
    lis = [[] for _ in range(n)]
    visited = [-1] * n
    for _ in range(m):
        a, b = list(map(lambda x: x-1, map(int, input().strip().split())))
        lis[a].append(b)
        lis[b].append(a)
    
    ans = 0
    for path in itertools.permutations(range(n), n):
        if path[0] != 0:
            continue
        c = True
        for i in range(n-1):
            pi1 = path[i+1]
            pi = path[i]
            # print(path)
            if pi1 not in lis[pi]:
                c = False
                break
        if c:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

path, ans = [[0]], 0
while len(path) > 0:
    p = path.pop()
    for g in G[p[-1]]:
        if not g in p:
            if len(p) == N - 1:
                ans += 1
            else:
                path.append(p + [g])

print(ans)

Submission status: Accepted

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

path, ans = [[0]], 0
while len(path) > 0:
    p = path.pop()
    if len(p) == N:
        ans += 1
    else:
        for g in G[p[-1]]:
            if not g in p:
                path.append(p + [g])

print(ans)