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 copy import deepcopy


def solve(road, num, ans, n):
    pattern = 0
    test = deepcopy(road)
    for s in test:
        if num in s:
            s.remove(num)
    if len(ans) is n:
        return 1
    if len(test[num - 1]) == int(0):
        return 0
    else:
        for i in range(len(test[num - 1])):
            tmp = test[num - 1][i]
            if tmp is not 0:
                word = ans + str(tmp)
            pattern += solve(test, tmp, word, n)
    return pattern


N, M = [int(i) for i in input().split()]
town = []
for i in range(N):
    town.append(deepcopy([]))

for i in range(M):
    a, b = [int(i) for i in input().split()]
    if a is not 1 or b is not 1:
        town[a - 1].append(b)
        town[b - 1].append(a)
print(solve(town, 1, '1', N))

Submission status: Accepted

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

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

for i in range(M):
    a, b = list(map(int, input().split(" ")))
    graph[a].append(b)
    graph[b].append(a)
    
def DFS(node, prev, visited):
    visited.append(node)
    if len(visited) == N:
        return 1
    
    res = 0
    for edge in graph[node]:
        if edge == prev:
            continue
        elif edge in visited:
            continue
        res += DFS(edge, node, visited[:])
        
    return res

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

Submission status: Accepted

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

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

for i in range(M):
    a, b = list(map(int, input().split(" ")))
    graph[a].append(b)
    graph[b].append(a)
    
def DFS(node, prev, visited):
    visited.append(node)
    if len(visited) == N:
        return 1
    
    res = 0
    for edge in graph[node]:
        if edge == prev:
            continue
        elif edge in visited:
            continue
        res += DFS(edge, prev, visited[:])
        
    return res

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

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import permutations


def main():
    N, M = map(int, input().split())
    s = set()
    for _ in range(M):
        a, b = map(int, input().split())
        s.add((a, b))
        s.add((b, a))
    ans = 0
    for x in permutations(range(2, N + 1)):
        now = 1
        for i in range(len(x)):
            if (now, x[i]) not in s:
                break
            now = x[i]
        else:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def makelist(n, m):
  return [[False for i in range(m)] for j in range(n)]


N, M = map(int, input().split())
graph = [0]*N
ans = [0]

for i in range(N):
  graph[i] = []
  
for i in range(M):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  graph[a].append(b)
  graph[b].append(a)
  
def dfs(now, dp):
  if dp.count(True) == N:
    ans[0] += 1
  else:
    for e in graph[now]:
      if not dp[e]:
        nextdp = dp[:]
        nextdp[e] = True
        dfs(e, nextdp)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n, m = map(int, input().split())
g = [[] for i in range(n)]

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

def dfs(v):
    if len(v) == n:
        return 1
    ret = 0
    for u in set(g[v[-1]]) - set(v):
        ret += dfs(v + [u])
    return ret

print(dfs([0]))

Submission status: Accepted

Solution code:
import itertools
import sys

# sys.stdin = open('c1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_str_list():
    return input().split()


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


def read_str():
    return input()


N, M = read_int_list()
a = list()
b = list()
edges = set()
for i in range(1, M + 1):
    s = input()
    l = s.split()
    u = int(l[0])
    v = int(l[1])
    a.append(u)
    b.append(v)
    edges.add((u, v))
    edges.add((v, u))
# print(edges)

t = range(1, N + 1)
res = 0
for p in itertools.permutations(t):
    if p[0] != 1:
        break
    c = 0
    for j in range(0, N - 1):
        if (p[j], p[j + 1]) in edges:
            c += 1
    if c == N - 1:
        res += 1
print(res)

Submission status: Accepted

Solution code:
def dfs():
  stack = [[0]]
  count = 0
  while stack:
    route = stack.pop()
    if len(route) == N:
      #print 'route=',route
      count += 1
      continue
    now = route[-1]
    for next in filter(lambda x: EDGES[now][x] == 1, range(N)):
      #print 'now,next',now,next
      if next in route:
        continue
      newroute = route[:]
      newroute.append(next)
      stack.append(newroute)
  return count

N,M = map(int, raw_input().split())
EDGES = [[0 for i in range(N)] for i in range(N)]
for i in range(M):
  a,b = map(int, raw_input().split())
  EDGES[a-1][b-1] = 1
  EDGES[b-1][a-1] = 1

print dfs()

Submission status: Accepted

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

l = []

for i in range(M):
    l.append(list(map(lambda x: int(x) - 1, input().split())))

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

for i in range(M):
    lis[l[i][0]].append(l[i][1])
    lis[l[i][1]].append(l[i][0])


# 隣接行列
# list = [[0 for c in range(M)] for r in range(N)]
#
# for i in range(M):
#     tmp_n, tmp_m = map(int, input().split())
#     list[tmp_n - 1][tmp_m - 1] = 1
#
#
# def dot(index1, index2):
#     results = [[0 for c in range(M)] for r in range(N)]
#     for (i, j) in zip(index1, zip(*index2)):
#         print(i,j)
#     return results



# 再起関数
# def travel(now, nextnodes, visited):
#     ends.append(visited)
#     visited.append(now + 1)
#     for node in nextnodes:
#         if node in visited:
#             continue
#         travel(node - 1, lis[node - 1], visited[:])
#
#
# travel(0, lis[0], [])

que = [[0, lis[0], []]]
ends = []

while que:
    now, nextnodes, visited = que.pop()
    ends.append(visited)
    visited.append(now)
    for node in nextnodes:
        if node in visited:
            continue
        que.append([node, lis[node], visited[:]])

print(len(list(filter(lambda ii: len(ii) is N, ends))))

Submission status: Accepted

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

abmap = {}
for a, b in ab:
    atarget = abmap.get(a)
    if atarget == None:
        abmap[a] = []
    abmap[a].append(b)

    btarget = abmap.get(b)
    if btarget == None:
        abmap[b] = []
    abmap[b].append(a)

que = [[1, abmap[1], []]]
ends = []
while que:
    now, nextnodes, visited = que.pop()
    ends.append(visited)
    visited.append(now)
    for node in nextnodes:
        if node in visited:
            continue
        mvisited = visited[:]
        que.append([node, abmap[node], mvisited])

print(len(list(filter(lambda x: len(x) == n, ends))))

Submission status: Accepted

Solution code:
import itertools
import numpy as np
N, M = map(int, raw_input().split())
G = [map(int, raw_input().split()) for i in range(M)]
ans = 0
for x in itertools.permutations(range(1,N+1)):
    if x[0] != 1:
        continue
    ok = True
    for i in range(N-1):
        a, b = x[i:i+2]
        if (not [a, b] in G) and (not [b, a] in G):
            ok = False
            break
    if ok:
        ans += 1
print ans

Submission status: Accepted

Solution code:
# Suplemental: ABC54 C
N, M = map(int, input().split())
E = [[] for i in range(N+1)]
for i in range(M):
    a,b = map(int, input().split())
    E[a].append(b)
    E[b].append(a)
    
#for i in range(1,N+1):
#    print(E[i])

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

num_of_paths = 0
def dfs(v):
    global num_of_paths
    
    if visited.count(True) == N:
        num_of_paths += 1
        return
    else:
        for next_v in E[v]:
            if not visited[next_v]:
                visited[next_v] = True
                dfs(next_v)
                visited[next_v] = False
        return
    
visited[1] = True
dfs(1)

print(num_of_paths)

Submission status: Accepted

Solution code:
def move(a, A, c):

  c.remove(a)
  if(c==[]):
    return 1
  if(not a in A):
    return 0
  sum = 0
  for i in A[a]:
    if(i in c):
      sum += move(i, A, list(c))

  return sum


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

A = {}
c = []

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

  if(not a in c):
    c.append(a)
  if(not b in c):
    c.append(b)

  if(a in A):
    A[a].append(b)
  else:
    A[a] = [b]
  if(b in A):
    A[b].append(a)
  else:
    A[b] = [a]

print(move(1, A, c))

Submission status: Accepted

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

import sys
import os

N, M = map(int, input().split())
# Node
# M: Edge num

# 隣接リスト
E = [[] for i in range(N)]
#print(E)

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

# BFSだとvisitedリストも増えすぎる
# DFSがよい

visited = [False] * N

one_stroke_num = 0
def dfs(v):
    #print('dfs', v)
    global one_stroke_num

    if visited.count(True) == N:
        one_stroke_num += 1
        return
    else:
        # vから行けるところあるか
        for next_i in E[v]:
            if not visited[next_i]:
                # そこに行く
                visited[next_i] = True
                dfs(next_i)
                visited[next_i] = False
        # もう行くところない
        return

visited[0] = True
dfs(0)

print(one_stroke_num)

Submission status: Accepted

Solution code:
from collections import defaultdict
import queue

if __name__ == "__main__":
    inp = [int(i) for i in input().split()]
    N = inp[0]
    M = inp[1]
    adjs = defaultdict(lambda: [])
    for i in range(M):
        a, b = [int(i) for i in input().split()]
        adjs[a].append(b)
        adjs[b].append(a)
    
    q = queue.Queue()
    q.put([1])
    n = 0
    while True:
        if q.empty(): break
        p = q.get()
        if len(p) == N:
            n += 1
        else:
            for i in adjs[p[-1]]:
                if i not in p:
                    pp = p.copy()
                    pp.append(i)
                    q.put(pp)
    print(n)

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)

ans = 0
passed = [0]
n = 0
s = [[n,passed]]
while s:
	n, passed = s.pop()
	if len(passed) == N:
		ans += 1
	else:
		for i in g[n]:
			if i not in passed:
				s.append([i, passed + [i]])
print(ans)

Submission status: Accepted

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

def dfs(v,n,visited):
    if not False in 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,n,visited)
        visited[i] = False
    return ret

visited = [False]*N
visited[0] = True
print(dfs(0,N,visited))

Submission status: Accepted

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

bar = [[] for _ in range(n)]

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

result = 0

def search(root=[0]):
    global result
    if len(root) >= n:
        result += 1
        return
    nxt = set(bar[root[-1]])
    nxt = nxt - set(root)
    for nxt_ in nxt:
        search(root+[nxt_])

search()
print(result)

Submission status: Accepted

Solution code:
def add_adj(adj, k, v):
    if k not in adj:
        adj[k] = set()
    adj[k].add(v)


def all_visited(N):
    x = 0
    for i in range(N):
        x += 1 << i
    return x


def dfs(adj, cur, visited, N):
    if visited == all_visited(N):
        return 1
    cnt = 0
    for nex in adj[cur]:
        if (visited >> (nex - 1)) & 1 == 1:
            continue
        cnt += dfs(adj, nex, (visited | (1 << (nex - 1))), N)
    return cnt


def main():
    N, M = map(int, input().split())
    adj = {}
    for i in range(M):
        a, b = map(int, input().split())
        add_adj(adj, a, b)
        add_adj(adj, b, a)
    print(dfs(adj, 1, 1, N))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
num = list(map(int,raw_input().split()))
point = num[0]
line = num[1]
total = 0
d = {}
for i in range (point):
    d[i+1] = []
for i in range(line):
    pair = list(map(int,raw_input().split()))
    d[pair[0]].append(pair[1])
    d[pair[1]].append(pair[0])
old_list = []
new_list = [[1]]
for i in range (point-1):
    old_list = new_list[:]
    new_list =[]
    for j in old_list:
        for k in d[j[-1]]:
            if k in j:
                pass
            else:
                j.append(k)
                new_list.append(j[:])
                j.pop()
print len (new_list)

Submission status: Accepted

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

###到達しているか否かのサイン
sign = []
for i in range(n):
    sign.append("o")

###グラフ
graph = []
for i in range(n):
    graph.append([])

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

###深さ優先探索
###dfsはxからスタートしてoの箇所を全て回収する場合の数
def dfs(x, i=0):
    sign[x] = "x"
    
    ###すべてのノードが到達済みなら終了
    if sign == ["x" for k in range(n)]:
        return i + 1
    
    ###隣接するすべての点に対して、未到達ならdfsを適用
    for j in graph[x]:
        if sign[j] == "o":
            
            ###一旦xにする（後で戻す）
            sign[j] = "x"
            
            ###重要重要重要重要重要重要重要重要重要重要重要重要重要重要重要重要重要重要
            ###右辺のiにはこれまでの場合の数が蓄積されている
            ###そのiの上にjスタートの場合の数が加算される
            ###それを新たなiとする
            ###つまり、足し算の操作は右辺で完結している
            ###iはここでしか動かないことに注意
            ###重要重要重要重要重要重要重要重要重要重要重要重要重要重要重要重要重要重要
            
            i = dfs(j, i)
            
            ###戻した
            sign[j] = "o"
    return i

print(dfs(0))

Submission status: Accepted

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

sign = []
for i in range(n):
    sign.append("o")
    
graph = []
for i in range(n):
    graph.append([])
    
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    for j in range(n):
        if a == j:
            graph[j].append(b)
        if b == j:
            graph[j].append(a)

def dfs(x, i=0):
    sign[x] = "x"
    if sign == ["x" for k in range(n)]:
        return i + 1
    for j in graph[x]:
        if sign[j] == "o":
            sign[j] = "x"
            i = dfs(j, i)
            sign[j] = "o"
    return i 

print(dfs(0))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import numpy as np
from itertools import permutations
from functools import reduce
# sys.setrecursionlimit(10000)


def main():
    # 入力処理
    N, M = map(int, input().split())
    edges = [set(map(int, input().split())) for i in range(M)]
    print(edges, file=sys.stderr)

    # アルゴリズム本体
    ps = permutations(range(2,N+1), N-1)

    C = 0
    for p in ps:
        q = [1] + list(p)
        xs = [set((q[i],q[i+1])) in edges for i in range(N-1)]
        if all(xs):
            print(q, file=sys.stderr)
            C += 1

    # 出力
    print(C)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
vector = []
for i in range(m):
    a,b = map(int,input().split())
    vector.append([a,b])
    vector.append([b,a])
global kotae
kotae = 0
route =  [1]

def idou(route,vector):
    global kotae
    if len(route) == n:
        kotae += 1
        return 0
    for vec in vector:
        if vec[0] == route[-1] and vec[1] not in route:
            route.append(vec[1])
            idou(route,vector)
            route.remove(vec[1])
    return 0
    

idou(route,vector)
 
          
print(kotae)

Submission status: Accepted

Solution code:
def main():
    N,M = map(int, raw_input().split())
    conf = [[0 for i in range(N)]for j in range(N)] 
    visit = [0]*N
    c = 0
    for i in range(M):
        s,g = map(int , raw_input().split())
        conf[s-1][g-1] = 1
        conf[g-1][s-1] = 1
    visit[0] = 1
    return dfs(conf, visit, 0, c)

def dfs(conf, visit, s, c):
    if 0 not in visit:
        visit[s] = 0
        c += 1
        return c
    for i in xrange(len(visit)):
        if conf[s][i] == 1 and visit[i] == 0:
            visit[i] = 1
            c = dfs(conf, visit , i, c)
            visit[i] = 0
    return c
print main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split(" "))
a = [0 for i in range(M)]
b = [0 for i in range(M)]
for i in range(M):
    a[i], b[i] = map(int, input().split(" "))

adj_matrix = [[0 for i in range(N)] for j in range(N)]
visited_flag = [0 for i in range(N)]
visited_flag[0] = 1

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

def find_next(idx, matrix, flag, nb_ans):
    if sum(flag) == N:
        return nb_ans+1
    for j in range(N):
        if matrix[idx][j] == 1 and flag[j] == 0:
            flag[j] = 1
            nb_ans = find_next(j, matrix, flag, nb_ans)
            flag[j] = 0

    return nb_ans

nb_ans = find_next(0, adj_matrix, visited_flag, 0)
print(nb_ans)

Submission status: Accepted

Solution code:
t = list(str(input()).split(" "))
n = int(t[0])
m = int(t[1])

x = [list() for i in range(n)]
lst = list()

for i in range(m):
    t = list(str(input()).split(" "))
    a = int(t[0])
    b = int(t[1])
    x[a-1].append(b-1)
    x[b-1].append(a-1)

def depth(p):

    if(len(lst) == n-1):
        global c
        c = c+1

    else:
        for i in x[p]:
            if(i not in lst):
                lst.append(p)
                depth(i)
                lst.remove(p)

c = 0
depth(0)
print(c)

Submission status: Accepted

Solution code:
import itertools

def path(n):
    l = len(n)
    i = 0
    while i < l - 1:
        a = n[i]
        b = n[i + 1]

        if a < b:
            c = (a, b)
        else:
            c = (b, a)

        for m in C:
            if m == c:
                break
        else:
            return False
        i += 1
    return True

N, M = map(int, input().split())
C = []
i = 0
while i < M:
    C += [tuple(map(int, input().split()))]
    i += 1

i = 0
l = range(1, N + 1)
for n in itertools.permutations(l, N):
    if n[0] != 1:
        break
    if path(n) == True:
        i += 1
print(str(i))

Submission status: Accepted

Solution code:
#ABC054C
from itertools import permutations

n,m=map(int,raw_input().split())
r=set()
s=set()
for i in xrange(m):
 u,v=map(int,raw_input().split())
 u-=1
 v-=1
 r.add(u)
 r.add(v)
 s.add((u,v))
 s.add((v,u))

res=0
l=list(permutations(r))
for t in l:
 if t[0]!=0:
  continue
 if all((t[i],t[i+1]) in s for i in xrange(n-1)):
  res+=1
   
print res

Submission status: Accepted

Solution code:
n, m = map(int, raw_input().split())
edges = [list(map(int, raw_input().split())) for _ in xrange(m)]

adjacent = [[] for _ in xrange(n)]
for a, b in edges:
    adjacent[a-1].append(b)
    adjacent[b-1].append(a)

check = [False]*n
check[0] = True
count = 0

def DFS(cn):
    global count
    if all(check):
        count += 1
        return 0
    for nn in adjacent[cn-1]:
        if check[nn-1] == True:
            continue
        else:
            check[nn-1] = True
            DFS(nn)
            check[nn-1] = False
    return 0

if __name__ == '__main__':
    DFS(1)
    print count

Submission status: Accepted

Solution code:
from itertools import permutations as perm

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

path = [[False] * n for _ in range(n)]
for i in range(n):
    path[i][i] = True

for _ in range(m):
    ai, bi = map(int, input().split())
    a, b = ai - 1, bi - 1
    path[a][b] = True
    path[b][a] = True

ans = 0
for ps in perm(range(1, n)):
    fst = ps[0]
    if not path[0][fst]:
        continue
    check = [path[i][j] for (i, j) in zip(ps, ps[1:])]
    if all(check):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

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

inlist = []
for i in range(m):
	inlist.append(list(map(int, input().split())))

graph = [[0 for i in range(n)] for j in range(n)]

for i in inlist:
	graph[i[0]-1][i[1]-1] = 1
	graph[i[1]-1][i[0]-1] = 1

visited = []
visited.append(0)
count = 0
def dfs(cur):
	if len(visited) == n:
		global count
		count += 1
		return
	for i in range(n):
		if graph[cur][i] == 1 and i not in visited:
			visited.append(i)
			dfs(i)
			visited.pop()
	return

dfs(0)

print(count)

Submission status: Accepted

Solution code:
def dfs(x, count):
    ret = 0
    if used[x]:
        return ret
    used[x] = 1
    for y in path[x]:
        ret += dfs(y, count + 1)
    used[x] = 0
    if count == N:
        return ret + 1
    else:
        return ret

if __name__ == '__main__':
    N, M = map(int, input().split())
    path = {i + 1: set() for i in range(N)}
    for _ in range(M):
        a, b = map(int, input().split())
        path[a].add(b)
        path[b].add(a)
    used = [0] * (N + 2)
    print(dfs(1, 1))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from queue import Queue

q = Queue()
N, M = [int(n) for n in input().split()]
graph = {n:[] for n in range(1, N+1)}

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

end = 0
for n in range(2, N+1):
    if len(graph[n]) == 1:
        end = n

ok = []
q.put([1, []])

while not q.empty():
    point, past = q.get()
    for d in graph[point]:
        if not d in past:
            if len(past + [point, d]) == N:
                ok.append(past + [point, d])
            else:
                q.put([d, past+[point]])

print(len(ok))

Submission status: Accepted

Solution code:
import itertools

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

graph = [[] for i in range(n)]
for j in range(m):
    x, y = map(int, input().split())
    road[x - 1][y - 1] += 1
    road[y - 1][x - 1] += 1
    graph[x - 1].append(y - 1)
    graph[y - 1].append(x - 1)
# print(road)
# print(graph)

count = 0

for can in itertools.permutations(range(n)):
    if can[0] != 0:
        break
    # print(can)
    plus = 1
    for k in range(n - 1):
        # print(road[can[k]][can[k + 1]])
        plus *= road[can[k]][can[k + 1]]
    count += plus


def dfs(node, prev, visited):
    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 += dfs(edge, prev, visited[:])

    return res


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

if count == dfs:
    print(dfs)

Submission status: Accepted

Solution code:
_N,_M=input().split()
N = int(_N)
M = int(_M)
l = []
for i in range(0,M):
    _p, _q = input().split()
    l.append((int(_p),int(_q)))
_A,_B=zip(*l)

A=_A+_B
B=_B+_A


def gen_get_to(_fr):
    global A
    global B
    global nodes
    global step
    for itr in range(0,len(A)):
        if A[itr]==_fr:
            if not B[itr] in nodes[0:step]:
                yield B[itr]

def move(): #returns whether "move" succeeded or not
    global nodes
    global possible_memo
    global step
    global counter
    global N
    global end_flag
    try:
        _=next(possible_memo[step])
        nodes[step+1]=_
        step+=1
        #print("success move to {}".format(nodes[step]))
        #print("map: {}".format(nodes[0:step+1]))
        #print("I am at {}th node".format(step+1))
        if step==N-1:
            counter+=1
            #print('REACHED GOAL!!!')
        possible_memo[step]=gen_get_to(nodes[step])
    except StopIteration:
        step-=1
        #print("failed to move")
        if not step==-1:
            pass#print("map: {}".format(nodes[0:step+1]))
            #print("I am at {}th node".format(step+1))
        if step==-1:
            #print("I fell from the first node")
            end_flag=True

nodes=[0]*N
possible_memo=[0]*N
counter=0
step=0
nodes[step]=1
possible_memo[step]=gen_get_to(nodes[0])
end_flag=False

while not end_flag:
    move()


print(counter)

Submission status: Accepted

Solution code:
N, M = map(int, raw_input().split())
E = {}
for _ in range(M):
	a, b = map(int, raw_input().split())
	if not a in E: E[a] = set()
	if not b in E: E[b] = set()
	E[a].add(b)
	E[b].add(a)

def numPaths(visited_nodes, start_node):
	if len(visited_nodes) == N-1:
		return 1
	sum = 0
	for adj_node in E[start_node]:
		if not adj_node in visited_nodes:
			visited_nodes.add(start_node)
			sum += numPaths(visited_nodes, adj_node)
			visited_nodes.remove(start_node)
	return sum

print numPaths(set(), 1)

Submission status: Accepted

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

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


q = [(0,0)]
all_visited = (1 << n) - 1
ans = 0

while len(q) > 0:
    u,visited = q.pop(0)
    visited = visited ^ (1 << u)
    
    if visited == all_visited:
       ans += 1 
    
    for v in adj[u]:
        if visited & (1 << v):
            continue
        q.append((v,visited))

print ans

Submission status: Accepted

Solution code:
nmax = 8
graph = [[False for i in range(nmax)] for j in range(nmax)]

def dfs(v, N, visited):
    all_visited = True

    for i in range(N):
        if visited[i] == False:
            all_visited = False

    if all_visited:
        return 1

    ret = 0

    for i in range(N):
        if graph[v][i] == False:
            # 経路がない
            continue
        if visited[i] == True:
            # 使用済み
            continue

        visited[i] = True
        ret += dfs(i, N, visited)
        visited[i] = False

    return ret

if __name__ == '__main__':
    n, m = map(int, input().split())

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

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

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

Submission status: Accepted

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

fp=set()
def rec(cur):
    ret = 0
    fp.add(cur)
    if len(fp) == n:
        fp.remove(cur)
        return 1
    for nex in e[cur]:
        if nex not in fp:
            ret += rec(nex)
    fp.remove(cur)
    return ret
print(rec(0))

Submission status: Accepted

Solution code:
def findpath(graph, root, rest):
    if len(rest) == 0:
        return 1
    res = 0
    for n in graph[root]:
        if n in rest:
            rest.remove(n)
            res += findpath(graph, n, rest)
            rest.add(n)
    return res

n, m = map(int, input().split())
graph = {}
for _ in range(m):
    a, b = map(int, input().split())
    if a not in graph:
        graph[a] = set()
    graph[a].add(b)
    if b not in graph:
        graph[b] = set()
    graph[b].add(a)

print(findpath(graph, 1, set(range(2, n + 1))))

Submission status: Accepted

Solution code:
# recursively find all one-stroke paths
def findPaths(start, used):
	# if all vertices used, return 1 path found
	if len(used) == n:
		return 1

	# traverse all connections to unused vertices
	tot = 0
	for v in conn[start]:
		if v not in used:
			used.append(v)
			tot += findPaths(v, used)
			used.pop()

	# return total number of one-stroke paths found
	return tot

# get number of vertices N and edges M
n, m = map(int, raw_input().split())

# build a dict where key is start vertex and value is list of connected vertices
conn = {}
for i in range(m):
	a, b = map(int, raw_input().split())
	if a in conn:
		conn[a].append(b)
	else:
		conn[a] = [b]
	if b in conn:
		conn[b].append(a)
	else:
		conn[b] = [a]

# recursively start at vertex 1 with corresponding visited queue and find all one-stroke paths
print (findPaths(1, [1]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def do_dp(N, Adj):
    univ = 2**(N-1) - 1
    dp = [[0]*(N-1) for i in range(univ + 1)]

    for u in range(N - 1):
        if Adj[0][u+1]:
            dp[1<<u][u] = 1

    for S in range(univ + 1):
        for v in range(N - 1):
            S2 = S & (univ ^ (1 << v))
            for u in range(N):
                if ((1 << u) & S2) and Adj[u+1][v+1]:
                    dp[S][v] += dp[S2][u]

    # debug(dp, locals())
    ans = sum(dp[univ][u] for u in range(N - 1))

    return ans

def solve():
    N, M = map(int, input().split())
    Adj = [[0]*N for i in range(N)]

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

    ans = do_dp(N, Adj)

    print(ans)

if __name__ == '__main__':
    solve()