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 itertools import permutations

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

L = [[] for i in range(N)]

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

P = permutations([0] + [i for i in range(1,N)])

ans = 0

for perm in P :
    visited = [0 for i in range(N)]
    visited[0] = 1
    for i in range(N-1) :
        if perm[i+1] not in L[perm[i]] :
            break
         
        if visited[perm[i+1]] :
            break
        
        visited[perm[i+1]] = 1
    
    if sum(visited) == N :
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def DFS(now, visited):

    if len(visited) == n:
        ans.append(1)
        return

    for i in graph[now]:
        if not i in visited:
            DFS(i, visited + [i])


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

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

DFS(0,[0])

print(len(ans))

Submission status: Accepted

Solution code:
l = input().split()
N = int(l[0])
M = int(l[1])

C = [[] for i in range(N)]

for i in range(M):
    l = input().split()
    a = int(l[0]) - 1
    b = int(l[1]) - 1
    C[a].append(b)
    C[b].append(a)

# print(N, M, C)

def visit(cur, visited, ans, depth):
    depth += 1
    # print('depth={}, cur={}, visited={}, ans={}, C[cur]={}'.format(
    #     depth, cur, visited, ans, C[cur]))
    visited.append(cur)
    if len(visited) == N:
        # print('goal')
        return ans + 1
    for n in C[cur]:
        # print('n={}'.format(n))
        if n not in visited:
            v = [x for x in visited]
            ans = visit(n, v, ans, depth)
    return ans

ans = 0
for n in C[0]:
    visited = [0]
    ans += visit(n, visited, 0, 0)

print(ans)

Submission status: Accepted

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

path_matrix = []
for n in range(N):
    path_matrix.append([False] * N)

#まず無向グラフを表す行列を作る
for m in range(M):
    line = map(int, input().split())
    paths = [x - 1 for x in line]
    path_matrix[paths[0]][paths[1]] = True
    path_matrix[paths[1]][paths[0]] = True

#最初はvisited、つまり訪問したことのあるノードはひとつもないので、Falseにする
visited = [False] * N


def dfs(now, depth):
    if visited[now]:
        return 0
    if depth == N - 1:
        return 1
    
    visited[now] = True
    total_paths = 0
    for i in range(0, N):
        if path_matrix[now][i]:
            total_paths += dfs(i, depth + 1)
    
    visited[now] = False

    return total_paths

print(dfs(0, 0))

Submission status: Accepted

Solution code:
import copy
n,m = map(int, input().split())


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

checked = [False for _ in range(n)]


def solve(i, c):
  c[i] = True

  global ans
  if c.count(False) == 0:
    ans += 1
    return
  else:
    for j in paths[i]:
      if c[j] == False: 
        solve(j, copy.deepcopy(c))
        
      

        
solve(0, copy.deepcopy(checked))
print(ans)
    
#print(paths[0])

Submission status: Accepted

Solution code:
import itertools

N,M=map(int,input().split())
route=[list(map(int,input().split())) for _ in range(M)]
candidate=list(itertools.permutations(range(1,N+1)))

ans=0
for c in candidate:
  if c[0]==1:
    for i in range(N-1):
      l=sorted([c[i], c[i+1]])
      if l not in route:
         break
    else:
      ans+=1
print(ans)

Submission status: Accepted

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


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


def dfs(p, visited):
  if len(visited) == N:
    return 1
  else:
    ret = 0
    for q in graph[p]:
      if q not in visited:
        ret += dfs(q, visited+[q])
    return ret

print(dfs(0,[0]))

Submission status: Accepted

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


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

ans = 0

def dfs(p, visited):
  global ans
  if len(visited) == N:
    ans += 1
  else:
    for q in graph[p]:
      if q not in visited:
        dfs(q, visited+[q])

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

Submission status: Accepted

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


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    vertex = [[0] * N for i in range(N)]

    for i in range(M):
        vertex[a[i]-1][b[i]-1] += 1
        vertex[b[i]-1][a[i]-1] += 1

    import itertools
    ans = 0
    for x in itertools.permutations(range(N)):
        if(x[0] != 0):
            break
        plus = 1
        for i in range(N-1):
            plus = plus * vertex[x[i]][x[i+1]]

        ans += plus
             
    print(ans)
    return
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]" 
    b = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, M, a, b)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
grp = []
for i in range(0, N):
	lst = []
	for j in range(0, N):
		lst.append(False)
	grp.append(lst)
for i in range(0, M):
	a, b = map(int, input().split())
	grp[a-1][b-1] = True
	grp[b-1][a-1] = True
memo = [False]
goal = [False]
for i in range(1, N):
	memo.append(True)
	goal.append(False)
queue = [[0, memo]]
cnt = 0
while queue != []:
	now = queue.pop(0)
	if now[1] == goal: cnt += 1
	else:
		for i in range(0, N):
			if grp[now[0]][i] and now[1][i]:
				newmemo = []
				for j in range(0, N):
					if i == j: newmemo.append(False)
					else: newmemo.append(now[1][j])
				queue.append([i, newmemo])
print(cnt)

Submission status: Accepted

Solution code:
def dp(d,i):
    if sum(d)==n-1:return 1
    x=0
    for j in l[i]:
        if d[j-2]==1:continue
        di=d[:]
        di[j-2]=1
        x+=dp(di,j)
    return x
        
n,m=map(int,input().split())
l=[[] for _ in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    if b!=1:l[a].append(b)
    if a!=1:l[b].append(a)
print(dp([0]*(n-1),1))

Submission status: Accepted

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

def solve():
    N, M = list(map(int, input().split()))
    A, B = [], []
    edge = {}  # edge[v] := 頂点vの隣接リスト

    """方針
    Nは高々8なので全探索してみる
    """
    for i in range(M):
        a, b = list(map(int, input().split()))
        # 始点は0とする
        if not a-1 in edge:
            edge[a-1] = []
        edge[a-1].append(b-1)
        if not b-1 in edge:
            edge[b-1] = []
        edge[b-1].append(a-1)

    rest_list = [i for i in range(N)]  # まだ到達してない残りの頂点のリスト
    rest_list.remove(0)  # 0が始点なので除外しておく
    now_v = 0  # 現在の頂点

    def dfs(now_v, rest_list):
        if len(rest_list) == 0:
            # 残りの頂点が存在しない（すべての頂点に到達成功した）
            return 1
        ans = 0  # パスの数
        for u in rest_list:
            if not u in edge[now_v]: continue  # 現在の頂点now_vから、次の頂点uに辺が存在しないならスキップ
            tmp_rest_list = copy.deepcopy(rest_list)
            tmp_rest_list.remove(u)
            ans += dfs(u, tmp_rest_list)
        return ans

    ans = dfs(0, rest_list)
    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from collections import defaultdict
import itertools

n, m = map(int, input().split())
connected_dict = defaultdict(lambda: [])

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

count = 0
for permutation in list(itertools.permutations(range(2, n + 1))):
    flag = True
    pre_num = 1
    for num in permutation:
        if num not in connected_dict[pre_num]:
            flag = False
            break
        pre_num = num
    if flag:
        count += 1
print(count)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import collections
import itertools


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    graph = collections.defaultdict(list)
    for aa,bb in zip(a,b):
        graph[aa].append(bb)
        graph[bb].append(aa)

    res = 0
    for seq in itertools.permutations(range(1,N+1)):
        if seq[0] != 1:
            continue
        bOK = True
        for i in range(len(seq)-1):
            if seq[i+1] not in graph[seq[i]]:
                bOK = False
                break
        if bOK:
            res += 1

    print(res)





# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]" 
    b = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, M, a, b)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

graph = [[None] * N for _ in range(N)]
for x, y in edges:
    graph[x - 1][y - 1] = True
    graph[y - 1][x - 1] = True
    
def dfs(v):    
    if all(visited):
        return 1
    
    ret = 0
    for i in range(N):
        if not graph[v][i]:
            continue
        if visited[i]:
            continue
            
        visited[i] = True
        ret += dfs(i)
        visited[i] = False
        
    return ret

visited = [True] + [False] * (N - 1)
print(dfs(0))

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

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

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

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

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

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

ans = 0
DFS(0,used)

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
p = [[] for i in range(n)]

for i in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    p[a].append(b)
    p[b].append(a)
ans = 0

# print(p)
def s(d, l):
    global ans
    # print(d,l)
    if d == n:
        ans += 1
        return
    for i in p[l[-1]]:
        if i in l:
            continue
        s(d+1, l+[i])
    return


s(1, [0])
print(ans)

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

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

# print(tree)
def dfs(node,p,passed):
    # print(node,passed)
    if len(passed) == N:
        return 1
    cnt = 0
    for new_node in tree[node]:
        if new_node == p:
            continue
        if not new_node in passed:
            passed2 = copy.deepcopy(passed)
            passed2 += [new_node]
            cnt += dfs(new_node,node,passed2)
    return cnt

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

Submission status: Accepted

Solution code:
import itertools

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

count = 0
for p in itertools.permutations(range(1, N+1)):
    if p[0] != 1:
        continue

    flag = True
    for i in range(N - 1):
        if not {p[i], p[i+1]} in Lines:
            flag = False
            break

    if flag:
        count += 1

print(count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
C - One-stroke Path
https://atcoder.jp/contests/abc054/tasks/abc054_c

"""
import sys


from itertools import permutations

def solve(N, M, path):
    ans = 0
    for p in permutations(range(2, N+1)):
        p = [1] + list(p)
        for f, t in zip(p, p[1:]):
            if not [f, t] in path and not [t, f] in path:
                break
        else:
            ans += 1
    return ans


def main(args):
    N, M = map(int, input().split())
    path = [[int(i) for i in input().split()] for _ in range(M)]
    ans = solve(N, M, path)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
import itertools
n,m=map(int,input().split())
A=[]
for i in range(m):
  a,b=map(int,input().split())
  A.append([a,b])
N=[int(i+2) for i in range(n-1)]
def f(list,n):
  path=0
  if [1,list[0]] in A:
    path+=1
  for i in range(1,n-1):
    if [list[i],list[i-1]] in A or [list[i-1],list[i]] in A:
      path+=1
  if path==n-1:
    return 1
  else:
    return 0  
ans=0
for p in itertools.permutations(N,n-1):
  ans+=f(list(p),n)
print(ans)

Submission status: Accepted

Solution code:
import copy
n, m = map(int,input().split())
graph = []
num = 1
for i in range(m):
    graph.append(list(map(int, input().split())))
pathes = [[[1],graph]]
count = 0
while pathes:
    path_lines = pathes.pop()
    path, lines = path_lines
    if len(path) == n:
        count += 1
    else:
        for line in lines:
            if path[-1] in line:
                new_path = copy.copy(path)
                new_lines = copy.copy(lines)
                new_lines.remove(line)
                new_line = copy.copy(line)
                new_line.remove(new_path[-1])
                
                if new_line[0] in new_path:
                    continue
                new_path.append(new_line[0])
                pathes.append([new_path, new_lines])
print(count)

Submission status: Accepted

Solution code:
N,M = [int(i) for i in input().split()]
p = {}

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

cnt = 0

def func(q,l,n):
    if n == N:
        global cnt
        cnt += 1
    for i in p[q]:
        if i not in l:
            func(i, l+[i], n+1)

func(1, [1], 1)
print(cnt)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
p = {} #各点と繋がってる点を記録
for _ in range(M):
    a, b = map(int, input().split())
    if a in p:
        p[a].append(b)
    else:
        p[a] = [b]
    if b in p:
        p[b].append(a)
    else:
        p[b] = [a]
cnt = 0 #答え
def func(q, l, n): #q今いる点 lこれまで訪れた点のリスト nこれまで訪れた頂点の種類
    if n == N:
        global cnt
        cnt += 1
    for i in p[q]:
        if i not in l: #今まで訪れてなければ訪れる
            func(i, l+[i], n+1)
func(1, [1], 1)
print(cnt)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
p = {}
for _ in range(M):
    a, b = map(int, input().split())
    if a in p:
        p[a].append(b)
    else:
        p[a] = [b]
    if b in p:
        p[b].append(a)
    else:
        p[b] = [a]
cnt = 0
def func(q, l, n):
    if n == N:
        global cnt
        cnt += 1
    for i in p[q]:
        if i not in l:
            func(i, l+[i], n+1)
func(1, [1], 1)
print(cnt)

Submission status: Accepted

Solution code:
from itertools import permutations
from heapq import *
from collections import defaultdict
from math import log
from itertools import accumulate
from collections import deque
#maxv=[0]
import sys
sys.setrecursionlimit(100100)

import math
from math import ceil
from copy import deepcopy


N,M=map(int,input().split())
T=[[] for i in range(N)]
for i in range(M):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    T[u].append(v)
    T[v].append(u)
list=list(range(1,N))
ans=0
for l in permutations(list):
    t=True
    for i in range(N-1):
        if i==0:
            if not l[0] in T[0]:
                t=False
                break
        else:
            if not l[i] in T[l[i-1]]:
                t=False
                break
    if t:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import itertools
N,M=map(int,input().split())
ab=list(list(map(int,input().split())) for _ in range(M))
l=list(l for l in range(1,N+1))
numlist=list(itertools.permutations(l))
ans=0
for I in numlist:
    if I[0]==1 and all(sorted([I[j],I[j+1]]) in ab for j in range(N-1)):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split(" "))
G = [[] for x in range(N)]
E = [0]*N
for i in range(M):
    a,b = map(int,input().split(" "))
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

def search(x):
    a = 0
    E[x] = 1
    if 0 not in E:
        a += 1
    for g in G[x]:
        if E[g] == 0:
            a += search(g)
    E[x] = 0
    return a

print(search(0))

Submission status: Accepted

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

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

def dfs(x, been):
    ans = 0
    if len(been) == N:
        return 1
    else:
        for i in data[x]:
            if been.count(str(i)) == 0:
                been += str(i)
                ans += dfs(i, been)
                been = been[:-1]

    return ans

been = '1'
print(dfs(1, been))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from itertools import permutations

n,m=map(int,input().split())
path=set()
for _ in range(m):
    u,v=map(int,input().split())
    path|={(u-1,v-1),(v-1,u-1)}
s = 0
for i in permutations(range(n)):
    if i[0] ==0:

        s+=(all((h,j) in path for h,j in zip(i[1:],i)))


print(s)

Submission status: Accepted

Solution code:
#########
#thiking Face
from itertools import permutations

n,m=map(int,input().split())
path=set()
for _ in range(m):
    u,v=map(int,input().split())
    path|={(u-1,v-1),(v-1,u-1)}

print(sum(all((u,v) in path for u,v in zip(p,p[1:]))
          for p in permutations(range(n)) if p[0]==0))

Submission status: Accepted

Solution code:
def dfs(graph, start):
    ans = 0
    stack = [[start, 2**start]]
    visited = {}
    while stack:
        d = stack.pop()
        if d[1] == 2 ** N - 1:
            ans += 1
            continue
        for node in graph[d[0]]:
            if not (d[1] & 2 ** node):
                stack.append([node, d[1] | 2 ** node])
    return ans


N, M = map(int, input().split())
g = {i: [] 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)
print(dfs(g, 0))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
X = [[0] * N for _ in range(N)]
for i in range(M):
  X[ab[i][0]-1][ab[i][1]-1] = 1
  X[ab[i][1]-1][ab[i][0]-1] = 1

def dfs(u):
  c = 0
  if len(u) == N:
    return 1
  for i in range(len(X[u[-1]])):
    if X[u[-1]][i] == 1 and i not in u:
      c += dfs(u + [i])
  return c

print(dfs([0]))

Submission status: Accepted

Solution code:
import numpy as np
N, M = map(int, input().split())
 
Adj_matrix = np.zeros((N, N))
for _ in range(M):
    a, b = map(int, input().split())
    Adj_matrix[a - 1, b - 1] += 1
    Adj_matrix[b - 1, a - 1] += 1
    
def initialize():
    explored_list = np.zeros((N, 1))
    return explored_list
  
def is_move(vertex, explored_list, Adj_martrix):
    for i in range(len(explored_list)):
        if explored_list[i] == 0 and Adj_martrix[vertex - 1, i] == 1:
            return True
    return False
  
import copy
 
g_count = 0
 
def graph_exp(vertex, explored_list, Adj_matrix):
    global g_count
    
    explored_list[vertex - 1] += 1
    
    # Recursive End
    if not is_move(vertex, explored_list, Adj_matrix):
        g_count += all(explored_list)
        return 0
    
    # Recursive Call
    for i in range(len(explored_list)):
        if explored_list[i] == 0 and Adj_matrix[vertex - 1, i] == 1:
            graph_exp(i + 1, copy.copy(explored_list), Adj_matrix)
    
explored_list = initialize()
 
graph_exp(1, explored_list, Adj_matrix)
 
print(g_count)

Submission status: Accepted

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

def dfs(s,check):
  if len(check)==n:
    if len(set(check))==n:
      return 1
    else:
      return 0
  ans=0
  for i in edge[s]:
    ans+=dfs(i,check+[i])
  return ans

n,m=map(int,input().split())
edge=[[] for _ in range(n+1)]
for i in range(m):
  s,t=map(int,input().split())
  edge[s].append(t)
  edge[t].append(s)
print(dfs(1,[1]))

Submission status: Accepted

Solution code:
import itertools
N,M = map(int,input().split())
ab = [list(map(int,input().split())) for _ in [0]*M]
connect = [[] for _ in [0]*N]
for a,b in ab:
    connect[a-1].append(b-1)
    connect[b-1].append(a-1)
ans = 0
for a in itertools.permutations(range(1,N)):
    a = (0,) + a
    for i in range(N-1):
        if not a[i+1] in connect[a[i]]:
            break
    else:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
ans = 0
def dfs(v, visiteNode, graph):
  visiteNode[v] = 1
  if all(visiteNode):
    global ans
    ans += 1
    return
  for node in graph[v]:
    if visiteNode[node]:
      continue
    else:
      dfs(node, visiteNode[:], graph)

N,M = map(int, input().split())
v = 0
visiteNode = [0] * N

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)
  
dfs(v, visiteNode, graph)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
n, m = map(int,input().split())
dist =[[0 for i in range(n)] for j in range(n)]

for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    dist[a][b] = 1
    dist[b][a] = 1
ans = 0
for p in permutations([i for i in range(1,n)]):
    t = True
    for i in range(n-2):
        if i == 0:
            if dist[0][p[0]] == 0:
                t = False
                break
        if dist[p[i]][p[i+1]] == 0:
            t = False
            break
    if t:
        ans += 1
        #print(p)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools


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

graph = [[] for _ in range(N)]
for p in path:
    graph[p[0]-1].append(p[1]-1)
    graph[p[1]-1].append(p[0]-1)
# print(graph)

arr = [i for i in range(1,N)]
perms = [v for v in  itertools.permutations(arr, len(arr))]
# print(perms)

solved = 0
for perm in perms:
    now = 0
    res = True

    for v in perm:
        if v in graph[now]:
            now = v
        else:
            res = False
            break
    if res:
        solved += 1

print(solved)

Submission status: Accepted

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

visited = [False] * (N + 1)

def dfs(src, count):
    if count == N:
        return 1

    visited[src] = True
    result = 0
    for dst in E[src]:
        if not visited[dst]:
            result += dfs(dst, count + 1)
    visited[src] = False

    return result

print(dfs(1, 1))

Submission status: Accepted

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

visited = [False] * (N + 1)
visited[1] = True

def dfs(src, count):
    if count == N:
        return 1
    result = 0
    for dst in E[src]:
        if not visited[dst]:
            visited[dst] = True
            result += dfs(dst, count + 1)
            visited[dst] = False

    return result

print(dfs(1, 1))

Submission status: Accepted

Solution code:
ans = 0

def dfs(v, visited, d):
    visited[v] = 1
    if all(visited):
        global ans
        ans += 1
        return
    for node in d[v]:
        if visited[node]:
            continue
        else:
            dfs(node, visited[:], d)

n, m = map(int, input().split())
d = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a = a - 1
    b = b - 1
    d[a].append(b)
    d[b].append(a)
v = 0
visited = [0] * n
dfs(v, visited, d)
print(ans)

Submission status: Accepted

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

c = 0
rel = {}

for n in range(1, N + 1):
	rel[n] = []

for a, b in AB:
	rel[a] += [b]
	rel[b] += [a]

def trase(r):
	global c
	#print(r)
	if N == len(r):
		c += 1
		return
	for n in rel[r[-1]]:
		if n in r:
			continue
		trase(r + [n])

for n in rel[1]:
	trase([1] + [n])

print(c)

Submission status: Accepted

Solution code:
import itertools

n, m = [int(x) for x in input().split()]
edges = set(tuple(int(x) for x in input().split()) for _ in range(m))
print(sum(1 if all(p in edges or tuple(reversed(p)) in edges for p in [(1, path[0])] + list(zip(path, path[1:]))) else 0 for path in itertools.permutations(range(2, n + 1))))

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
branch_list = []
for i in range(M):
    branch_list.append(list(map(int,input().split())))

visited = [1]

def dfs(now):
    global cnt
    if len(visited) == N:
        cnt += 1
        return cnt
    for br in branch_list:
        if now in br:
            next_node = br[1-br.index(now)]
            if not next_node in visited:
                visited.append(next_node)
                dfs(next_node)
                visited.remove(next_node)
    return cnt
cnt = 0
dfs(1)
print(cnt)

Submission status: Accepted

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

ab_list = []
for _ in range(M):
    ab_list.append(list(map(int, input().split())))

cnt = 0
def func(position, hist):
    global cnt
    hist = hist[:]
    if len(hist) == N:
        cnt += 1
    for ab in ab_list:
        if position in ab:
            next_position = [x for x in ab if x != position][0]
            if next_position not in hist:
                func(next_position, hist+[position])

func(1,[0])
print(cnt)

Submission status: Accepted

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

# グラフ組み立て
g = [["#" for _ in range(N)] for _ in range(N)]
for p in ab:
    g[p[0]-1][p[1]-1] = "-"
    g[p[1]-1][p[0]-1] = "-"

import itertools

# 頂点集合
n = [i for i in range(N)]

# 全ての組み合わせを調べる
ans = 0
for p in itertools.permutations(n, len(n)):
    flag = 1
    if p[0] != 0: # 頂点が合わない場合
        continue
    for i in range(N-1):
        if g[p[i]][p[i+1]] != "-":
            flag = 0
            break
    if flag:
        ans += 1
print(ans)