Problem:


Score : 300 points

Problem Statement

You are given an undirected unweighted graph with N vertices and M edges that contains neither self-loops nor double edges.

Here, a self-loop is an edge where a_i = b_i (1≤i≤M), and double edges are two edges where (a_i,b_i)=(a_j,b_j) or (a_i,b_i)=(b_j,a_j) (1≤i<j≤M).

How many different paths start from vertex 1 and visit all the vertices exactly once?

Here, the endpoints of a path are considered visited.  

For example, let us assume that the following undirected graph shown in Figure 1 is given.

Figure 1: an example of an undirected graph

The following path shown in Figure 2 satisfies the condition.

Figure 2: an example of a path that satisfies the condition

However, the following path shown in Figure 3 does not satisfy the condition, because it does not visit all the vertices.

Figure 3: an example of a path that does not satisfy the condition

Neither the following path shown in Figure 4, because it does not start from vertex 1.

Figure 4: another example of a path that does not satisfy the condition

Constraints

2≦N≦8 

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

1≦a_i<b_i≦N 

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

Input

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

N M  
a_1 b_1  
a_2 b_2
:  
a_M b_M  

Output

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

Sample Input 1

3 3
1 2
1 3
2 3

Sample Output 1

2

The given graph is shown in the following figure:

The following two paths satisfy the condition:

Sample Input 2

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

Sample Output 2

1

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



Sample input:
3 3
1 2
1 3
2 3


Sample output:
2

Submission status: Accepted

Solution code:
import itertools
N,M = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(M)]
es = [[] for i in range(N)]
for a,b in src:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

ans = 0
for ptn in itertools.permutations(range(1,N)):
    a = 0
    for b in ptn:
        if a not in es[b]:
            break
        a = b
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

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

X = [i for i in range(1, N)]

ans = 0
for s in itertools.permutations(X, N - 1):
	judge = "Yes"
	x = 0
	for i in s:
		if L[i].count(x) == 1:
			pass
			x = i
		else:
			judge = "No"
			break
	if judge == "Yes":
		ans += 1

print(ans)

Submission status: Accepted

Solution code:
n = 0
g = []
res = 0


def dfs(i, path):
    global n, g, res
    path.append(i)
    if len(path) == n:
        res += 1
        path.pop()
        return

    for j in g[i]:
        if not j in path:
            dfs(j, path)
    path.pop()


def main():
    global n, g, res
    n, m = map(int, input().split())
    g = [set() for _ in range(n)]
    for _ in range(m):
        a, b = map(lambda s: int(s) - 1, input().split())
        g[a].add(b)
        g[b].add(a)

    path = []
    dfs(0, path)
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

edges=[[] for i in range(n)]

for i in range(m):
  s,t = map(int,input().split())
  edges[s-1].append(t-1)
  edges[t-1].append(s-1)

cnt =0

V=[0]*n

def dfs(V,s):
  global cnt
  V=V[:]
  V[s]=1
  if sum(V)==n:
    cnt+=1
  else:
    for v in edges[s]:
      if V[v]==0:
        dfs(V,v)
  # print(V)
dfs(V,0)
print(cnt)

Submission status: Accepted

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

check = [False for i in range(n)]

ans = 0
def dfs(v):
    global ans

    if check.count(True) == n:
        ans += 1
        return
    else:
        for next in matrix[v]:
            if not check[next]:
                check[next] = True
                dfs(next)
                check[next] = False
        return

check[0] = True
dfs(0)

print(ans)

Submission status: Accepted

Solution code:
def c_one_stroke_path(N, M, E):
    from itertools import permutations
    edge = [[] for j in range(N + 1)]
    for a, b in E:
        edge[a].append(b)
        edge[b].append(a)

    ans = 0
    # 頂点1を始点としてこの順番に頂点を回れるか試す
    routes = permutations(range(2, N + 1), N - 1)
    for route in routes:
        r = [1] + list(route)
        for i in range(len(r) - 1):
            if not r[i + 1] in edge[r[i]]:
                break  # 次の行き先に行くことができなかった
        else:
            ans += 1  # すべての頂点を訪れることができた
    return ans

N,M = [int(i) for i in input().split()]
E = [[int(i) for i in input().split()] for j in range(M)]
print(c_one_stroke_path(N, M, E))

Submission status: Accepted

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

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

for a, b in ab:
    G[a][b] = 1
    G[b][a] = 1

count = 0


def dfs(G, a, x):
    a[x] = 1
    if all(a):
        return 1
    else:
        count = 0
        for j in range(N):
            if G[x][j] == 1 and a[j] == 0:
                count += dfs(G, a.copy(), j)
        return count


print(dfs(G, [0] * N, 0))

Submission status: Accepted

Solution code:
v=[]
n,m=map(int,input().split())
ans=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    ans[a-1].append((b-1))
    ans[b-1].append((a-1))
def dfs(now,visited=[]):
    if len(visited)==n:
        v.append([visited])
        return
    for j in ans[now]:
        if j not in visited:
            dfs(j,visited+[j])
dfs(0,[0])
print(len(v))

Submission status: Accepted

Solution code:
#!/usr/bin/python3

from itertools import permutations

def main():
    ans = 0
    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] += [b]
        G[b] += [a]

    a = list(permutations(range(1, n)))

    for i in a:
        ok = True
        for j in range(len(i)):
            tmp = False
            if j == 0:
                for e in G[0]:
                    if e == i[j]:
                        tmp = True
            else:
                for e in G[i[j-1]]:
                    if e == i[j]:
                        tmp = True
            if not tmp:
                ok = False
        if ok:
            ans += 1

    print(ans)

main()

Submission status: Accepted

Solution code:
#!/usr/bin/python3

import sys

sys.setrecursionlimit(10000)
ans = 0

def dfs(cur, visited, G):
    visited[cur] = True

    if all(visited):
        global ans
        ans += 1

    for c in G[cur]:
        if not visited[c]:
            dfs(c, visited, G)
            visited[c] = False
    return


def main():
    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] += [b]
        G[b] += [a]

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

    dfs(0, v, G)
    print(ans)

main()

Submission status: Accepted

Solution code:
from collections import deque


def main():
    N, M = map(int, input().split())
    adj = [[False] * N for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        adj[a][b] = True
        adj[b][a] = True
    retval = 0
    q = deque([(0, set([0]))])
    while len(q):
        cur, visited = q.popleft()
        if len(visited) == N:
            retval += 1
            continue
        for nxt in range(N):
            if nxt in visited:
                continue
            if adj[cur][nxt]:
                next_visited = set(visited)
                next_visited.add(nxt)
                q.append((nxt, next_visited))
    print(retval)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools

N, M = (int(i) for i in input().split())
sides = []
for i in range(M):
    a, b = (int(i) for i in input().split())
    sides.append((a-1,b-1))
kouhos = list(itertools.permutations(range(N)))
count = 0

for kouho in kouhos:
    Judge = True
    if kouho[0] != 0:
        break
    else:
        for i in range(N-1):
            if (kouho[i] , kouho[i+1]) in sides:
                pass
            elif (kouho[i+1] , kouho[i]) in sides:
                pass
            else:
                Judge = False
                break
    
    if Judge:
        count += 1

print(count)

Submission status: Accepted

Solution code:
from itertools import permutations

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

points = [i for i in range(1, N+1)]
answer = 0

for point in permutations(points):
  if not point[0] == 1:
    continue
  for i in range(N-1):
    if sorted([point[i], point[i+1]]) not in paths:
      break
  else:
    answer += 1

print(answer)

Submission status: Accepted

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

visited = [False for _ in range(n)]
def dfs(v):
    if all(visited):
        return 1
    res = 0
    for e in edge[v]:
        if not visited[e]:
            visited[e] = True
            res += dfs(e)
            visited[e] = False
    return res

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

Submission status: Accepted

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

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

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

def DFS(now_V, now_Log, ans):
    #print(now_V, now_Log, ans, sum(now_Log))
    
    if sum(now_Log)==N:
        ans = ans+1
        #print('cc')
        return ans
    
    for i in V[now_V]:
        if now_Log[i]<1:
            now_Log[i]=1
            ans = DFS(i, now_Log, ans)
            now_Log[i]=0
    
    return ans
          

count = 0  

Log[0] = 1

print(DFS(0, Log, count))

Submission status: Accepted

Solution code:
num_route = 0
num_node = 0

def func(unvisited_paths, visited_node, current_node):
    global num_route
    if len(visited_node) == num_node:
            num_route += 1
            return
    for next_path in [path for path in unvisited_paths if (path[0] == current_node) and (path[1] not in visited_node)]:
        next_visited_node = visited_node + [next_path[1]]
        next_unvisited_paths = unvisited_paths[:]
        next_unvisited_paths.pop(next_unvisited_paths.index([current_node, next_path[1]]))
        next_unvisited_paths.pop(next_unvisited_paths.index([next_path[1], current_node]))
        next_current_node = next_path[1]
        
        func(next_unvisited_paths, next_visited_node, next_current_node)
    
    return

def main():
    global num_node
    num_node, num_path = map(int, input().split())
    unvisited_paths = [list(map(int, input().split())) for i in range(num_path)]
    for path in unvisited_paths[:]:
        unvisited_paths.append([path[1], path[0]])
    current_node, visited_node = 1, [1]
    func(unvisited_paths, visited_node, current_node)
    print(num_route)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def func(paths, passed_node, current_node, num_node):
    global num_route
    if len(passed_node) == num_node:
            num_route += 1
            return
    for next_path in [path for path in paths if (path[0] == current_node) and (path[1] not in passed_node)]:
        new_passed_node = passed_node + [next_path[1]]
        new_paths = paths[:]
        new_paths.pop(new_paths.index([current_node, next_path[1]]))
        new_paths.pop(new_paths.index([next_path[1], current_node]))
        new_current_node = next_path[1]
        
        func(new_paths, new_passed_node, new_current_node, num_node)
    
    return num_route
    
            


num_node, num_path = map(int, input().split())
paths = [list(map(int, input().split())) for i in range(num_path)]
for path in paths[:]:
    paths.append([path[1], path[0]])
current_node = 1
passed_node = [1]
num_route = 0

try:
    func(paths, passed_node, current_node, num_node)
finally:
    print(num_route)

Submission status: Accepted

Solution code:
import itertools

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


points = [i for i in range(1, N+1)]
ans = 0

for i, v in enumerate(list(itertools.permutations(points))):
    if not v[0] == 1:
        continue
    for j in range(N-1):
        if sorted([v[j], v[j+1]]) not in Paths:
            break
    else:  # このelseの使い方覚える
        ans += 1


print(ans)

Submission status: Accepted

Solution code:
import copy


def search(start, adj, stack):
    nextNum = 0
    start[1][start[0]] = 1
    for i in range(len(adj[start[0]])):
        # print("start:{} next:{} vidited:{}".format(start, i, visited))
        if adj[start[0]][i] == 1 and start[1][i] == -1:
            stack.append([i, copy.deepcopy(start[1])])
            # print("append")
            nextNum += 1
            # print("visit to {}".format(next))
            # visited[i] = 1
    if nextNum > 0:
        return nextNum
    elif sum(start[1]) == len(adj):
        return 0
    else:
        return -1


n, m = [int(i) for i in input().split()]
adj = [[0 for j in range(n)] for i in range(n)]  # 隣接行列
for j in range(m):
    a, b = [int(i) - 1 for i in input().split()]
    adj[a][b] = 1
    adj[b][a] = 1

visited = [-1 for i in range(n)]
visited[0] = 1
stack = [[0, visited]]
poped = []
count = 0
while 1:
    size = len(stack)
    # print("\nstack:{}".format(stack))
    if size == 0:
        # print("visited:{}".format(visited))
        break
    next = stack.pop()
    # print("stack:{}".format(stack))
    # if len(stack) != 0:
    # poped.append(next)
    # print("poped:{}".format(poped))
    nextNum = search(next, adj, stack)
    if nextNum == 0:
        count += 1
        # print("ok")
    # elif nextNum == -1:
        # print("missed")
print(count)

Submission status: Accepted

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

def search(S, history, counter):
    new_history = [i for i in history]
    new_history.append(S)
    if len(new_history) == N:
        counter += 1
        return counter
        
    for i in range(len(A)):
        if A[i] == S and not B[i] in history:
            counter = search(B[i], new_history, counter)

    for i in range(len(B)):
        if B[i] == S and not A[i] in history:
            counter = search(A[i], new_history, counter)

    return counter

print(search(1, [], 0))

Submission status: Accepted

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

s = [set() for _ in range(n)]
for ab_i in ab:
	a_i, b_i = map(lambda x: x-1, ab_i)
	s[a_i].add(b_i)
	s[b_i].add(a_i)

# print(s)

def dfs(num, visited=set()):
	visited = visited | {num}
	can_moves = s[num] - visited
	# print(num, can_moves, visited)
	if not can_moves:
		return (len(visited) == n)
	return sum(dfs(can_move, visited) for can_move in can_moves)

print(dfs(0))

Submission status: Accepted

Solution code:
import itertools
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
L=list(itertools.permutations(range(2,n+1)))
c=0
for j in range(len(L)):
  if [1,L[j][0]] in l:
    x=0
    for k in range(n-2):
      if [L[j][k],L[j][k+1]] in l or [L[j][k+1],L[j][k]] in l:x+=1
    if x==n-2:c+=1
print(c)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-


"""
https://beta.atcoder.jp/contests/abc054/tasks/abc54_c
"""

import sys
import math
import copy
from inspect import currentframe

def debug_print(*args):
    names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args), file=sys.stderr)

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

for _ in range(M):
    a, b  = map(int, input().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)
    
# 普通にdfsで行けるイメージなのでそれをする
# パスの数を返す
def dfs(node, visited_list):
    paths = 0
    visited = copy.copy(visited_list)
    if node not in visited:
        visited.append(node)
    debug_print(node)
    debug_print(visited_list)
    if len(visited) == N:
        return 1
    for to in graph[node]:
        if to not in visited:
            paths += dfs(to, visited)
    return paths
        
print(dfs(0, [0]))

Submission status: Accepted

Solution code:
import copy


class Line:
    def __init__(self, a, b):
        self.a = a
        self.b = b


def generate_patterns(remains, current_pattern, patterns):
    if len(remains) == 0:
        patterns.append(current_pattern)
        return
    for remain in remains:
        _current_pattern = copy.copy(current_pattern)
        _current_pattern.append(remain)
        _remains = copy.copy(remains)
        _remains.remove(remain)
        generate_patterns(_remains, _current_pattern, patterns)
    return patterns


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

m = {}
for i in range(1, N+1):
    m[i] = {}
    for j in range(1, N+1):
        m[i][j] = False

for line in lines:
    m[line.a][line.b] = True
    m[line.b][line.a] = True

remains = []
for i in range(2, N+1):
    remains.append(i)
patterns = generate_patterns(remains, [1], [])

cnt = 0
for pattern in patterns:
    countable = True
    for i in range(len(pattern)-1):
        current = pattern[i]
        next = pattern[i+1]
        if not(m[current][next]):
            countable = False
            break
    if countable:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, raw_input().split())
nodes = {i:[] for i in range(1, N+1)}
for _ in range(M):
  a, b = map(int, raw_input().split())
  nodes[a] += [b]
  nodes[b] += [a]
stack = deque([[1, []]])
ans = 0
while stack:
  n, history = stack.pop()
  if len(history) == N - 1:
    ans += 1
    continue
  node = nodes[n]
  for next_node in node:
    if not next_node in history:
      stack.append([next_node, history+[n]])
print ans

Submission status: Accepted

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

l = [set() for _ in range(n)]
for a_i, b_i in ab:
	l[a_i-1].add(b_i-1)
	l[b_i-1].add(a_i-1)

# print(l)

def dfs(num, visited=set()):
	visited = visited | {num}
	can_moves = l[num] - visited
	# print(num, visited, can_moves)
	if not can_moves:
		# print(visited, n)
		return (len(visited) == n)

	sum_num = 0
	for can_move in can_moves:
		sum_num += dfs(can_move, visited)
	return sum_num

print(dfs(0))

Submission status: Accepted

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

seq = tuple([x for x in range(2,n+1)])
route = list(itertools.permutations(seq))

ans = 0
for t in route:
    now = 1
    flag = True
    t = list(t)
    for i in t:
        (p,q) = (now,i) if now < i else (i,now)
        if [p,q] not in e:
            flag = False
            break
        now = i
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
Edge=[[int(i) for i in input().split()] for i in range(M)]
Vertex=[]
X=[]
n=1
a=0
while n<=N:
  while a<=M-1:
    if n in Edge[a]:
      X=X+Edge[a]
    a+=1
  X=[item for item in X if item!=n]
  Vertex.append(X)
  n+=1
  a=0
  X=[]
Choices=[[1]]
m=0
for i in Choices:
    if len(i)>=N:
      break
    for j in Vertex[i[len(i)-1]-1]:
      Choices.append(i+[j])
Choices=[item for item in Choices if len(item)==N]
a=1
while a<=N:
  Choices=[item for item in Choices if item.count(a)==1]
  a+=1
print(len(Choices))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
e = [set([]) for _ in range(n+1)] # e[0] never used
for _ in range(m):
    a, b = map(int, input().split())
    e[a].add(b)
    e[b].add(a)

ans = 0
visited = [False]*(n+1) # visited[0] never used
visited[0] = True
def dfs(v):
    # current pos is v
    global visited
    global ans
    if all(v==True for v in visited):
        ans += 1
        return
    
    for next_pos in e[v]:
        if visited[next_pos] != True:
            visited[next_pos] = True
            dfs(next_pos)
            visited[next_pos] = False

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

Submission status: Accepted

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


def gcd(n, m):
    if n % m == 0:
        return m
    else:
        return gcd(m, n % m)


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


def lcm(n, m):
    return (n * m) // gcd(n, m)


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v


# Width First Search (+ Distance)
def wfs_d(D, N, K):
    """
    D: 隣接行列(距離付き)
    N: ノード数
    K: 始点ノード
    """

    dfk = [-1] * (N + 1)
    dfk[K] = 0

    cps = [(K, 0)]
    r = [False] * (N + 1)
    r[K] = True
    while len(cps) != 0:
        n_cps = []
        for cp, cd in cps:
            for i, dfcp in enumerate(D[cp]):
                if dfcp != -1 and not r[i]:
                    dfk[i] = cd + dfcp
                    n_cps.append((i, cd + dfcp))
                    r[i] = True

        cps = n_cps[:]

    return dfk


# Depth First Search (+Distance)
def dfs_d(v, pre, dist):
    """
    v:  現在のノード
    pre: １つ前のノード
    dist: 現在の距離

    以下は別途用意する
    D: 隣接リスト(行列ではない)
    D_dfs_d: dfs_d関数で用いる，始点ノードから見た距離リスト
    """

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return


def sigma(N):
    ans = 0
    for i in range(1, N + 1):
        ans += i
    return ans


def comb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def bisearch(L, target):
    low = 0
    high = len(L) - 1
    
    while low <= high:
        mid = (low + high) // 2
        guess = L[mid]
        if guess == target:
            return True
        elif guess < target:
            low = mid + 1
        elif guess > target:
            high = mid - 1
    if guess != target:
        return False

# --------------------------------------------

dp = None

ans = 0
N, M = 0, 0
A = None

def dfs(current_node, past_nodes, depth):
    global ans

    if depth == N:
        ans += 1
        return
    
    for next_node_i in range(1, N+1):
        if A[current_node][next_node_i] and next_node_i not in past_nodes:
            past_nodes.append(next_node_i)
            dfs(next_node_i, past_nodes, depth+1)
            past_nodes.remove(next_node_i)
    

def main():
    global N
    global M
    global A

    N, M = li_input()
    A = [[0] * (N+1) for _ in range(N+1)]

    for i in range(M):
        a, b = li_input()
        A[a][b] = 1
        A[b][a] = 1

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


main()

Submission status: Accepted

Solution code:
import itertools
N,M=map(int,input().split())
grid = []
for i in range(N):
    array = []
    while len(array) < N:
      array.append(0)
    grid.append(array)
for i in range(M):
    s,t=map(int,input().split())
    grid[s-1][t-1] = 1
    grid[t-1][s-1] = 1
i = 1
lis = []
while i <= N:
  lis.append(i)
  i += 1
ans = 0
for nums in itertools.permutations(lis):
    if nums[0]!=1:
      pass
    else:
      k = 0
      flag = 0
      while k < N-1:
        if grid[nums[k]-1][nums[k+1]-1] == 1:
          pass
        else:
          flag = 1
        k += 1
      if flag == 0:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
G = {}
for i in range(0,M):
    a, b = list(map(int, input().split()))
    if a in G:
        G[a] += [b]
    else:
        G[a] = [b]
    if b in G:
        G[b] += [a]
    else:
        G[b] = [a]

from itertools import permutations
import copy
paths = list(map(lambda x: [1] + list(x),list(permutations(range(2,1+N),N-1))))
cnt = 0

for path in paths:
    _G = copy.deepcopy(G)
    flg = 1
    for i in range(1,N):
        if path[i] in _G[path[i-1]]:
            _G[path[i-1]].remove(path[i])
            _G[path[i]].remove(path[i-1])
        else:
            flg = 0
            break
    cnt += flg

print(cnt)

Submission status: Accepted

Solution code:
# dfsで解く
def dfs_mat(v):
    global adjacency_mat, ans, visited
    # 全部訪れたか判定
    if sum(visited) == N:
        ans += 1
        return
    for i in range(N):
        if adjacency_mat[v][i]:
            # 訪れたことがあるなら何もしない
            if visited[i] == True:
                continue
            # 訪れたことがないなら
            else:
            # 訪れたことにする
                visited[i] = True
                dfs_mat(i)    
            # 頂点aを未訪問にする
                visited[i] = False


if __name__ == "__main__":
    # input
    N, M = map(int, input().split())
    # 隣接行列を作る
    adjacency_mat = [[None]* N for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        adjacency_mat[a-1][b-1] = 1
        adjacency_mat[b-1][a-1] = 1
    # 訪れたかどうか
    visited = [False] * N
    visited[0] = True # 0を訪れたことにする
    ans = 0 # 答え
    dfs_mat(0)
    print(ans)

Submission status: Accepted

Solution code:
# dfsで解く
def dfs(v):
    global adjacency_list, ans, visited
    # 全部訪れたか判定
    if sum(visited) == N:
        ans += 1
        return
    for a in adjacency_list[v]:
        # 訪れたことがあるなら何もしない
        if visited[a] == True:
            continue
        # 訪れたことがないなら
        else:
        # 訪れたことにする
            visited[a] = True
            dfs(a)    
        # 頂点aを未訪問にする
            visited[a] = False

if __name__ == "__main__":
    # input
    N, M = map(int, input().split())
    # 隣接listを作る
    adjacency_list = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        adjacency_list[a-1].append(b-1)
        adjacency_list[b-1].append(a-1)
    # 訪れたかどうか
    visited = [False] * N
    visited[0] = True # 0を訪れたことにする
    ans = 0 # 答え
    dfs(0)
    print(ans)

Submission status: Accepted

Solution code:
# encoding: utf-8
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(M)]

route = [[] for i in range(N)]
for ai, bi in ab:
    route[ai - 1].append(bi - 1)
    route[bi - 1].append(ai - 1)

# print("#", route)
    
def walk(pos, footprint):
    # goal
    if footprint == 2 ** N - 1: return 1
    # search route
    # print("##", pos, bin(footprint))
    ans = 0
    for to in route[pos]:
        if footprint & 2 ** to > 0: continue
        else: ans += walk(to, footprint + 2 ** to)
    return ans

print(walk(0, 1))

Submission status: Accepted

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

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

def search(x, L):
    LL = list(L)
    global result
    LL.append(x)
    if len(LL) == N:
        result += 1
        return
    for i in range(len(array[x-1])):
        if not array[x-1][i] in L:
            search(array[x-1][i], LL)
        
def main():
    L = []
    search(1, L)
    print(result)

main()

Submission status: Accepted

Solution code:
def find_route(now, node, route):
    count = 0
    if min(node) == 1:
        return 1
    dist = route[now]
    for i in dist:
        if node[i] == 0:
            tmpnode = node.copy()
            tmpnode[i] = 1
            count += find_route(i, tmpnode, route)
    return count

(n, m) = list(map(int, input().split()))
route = {}
for i in range(m):
    (a, b) = list(map(int, input().split()))
    a -= 1
    b -= 1
    if a in route:
        route[a].append(b)
    else:
        route[a] = [b]
    if b in route:
        route[b].append(a)
    else:
        route[b] = [a]
count = find_route(0, [1] + [0 for _ in range(n - 1)], route)

print(count)

Submission status: Accepted

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



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

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

print(dfs(0,N,visited))

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(V, v):
  _V = [v for v in V]
  _V[v] = 1
  cnt = 0
  if sum(_V) == N:
    return 1
  else:
    for adj in G[v]:
      if _V[adj] == 0:
        cnt += dfs(_V, adj)
    return cnt
print(dfs([0] * N, 0))

Submission status: Accepted

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

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

map_org = [[0 for _ in range(N)] for _ in range(N)]

for a, b in ab:
    map_org[a-1][b-1] = 1
    map_org[b-1][a-1] = 1

def dfs(v):
    visited[v] = 1
    if sum(visited) == N:
        return 1

    ret = 0    
    for i in range(N):
        if map_org[v][i] == 1:
            if visited[i] == 0:
                ret += dfs(i)
                visited[i] = 0
    return ret


visited = [0 for _ in range(N)]
print(dfs(0))

Submission status: Accepted

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

count = 0

for p in itertools.permutations(range(N)):
    #print(p)
    if p[0] != 0:
        break
    check = 1
    for s in range(N-1):
        check = check  * matrix[p[s]][p[s+1]]
    count += check

print(count)