Problem:


Score : 300 points

Problem Statement

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

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

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

Here, the endpoints of a path are considered visited.  

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

Figure 1: an example of an undirected graph

The following path shown in Figure 2 satisfies the condition.

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

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

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

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

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

Constraints

2≦N≦8 

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

1≦a_i<b_i≦N 

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

Input

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

N M  
a_1 b_1  
a_2 b_2
:  
a_M b_M  

Output

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

Sample Input 1

3 3
1 2
1 3
2 3

Sample Output 1

2

The given graph is shown in the following figure:

The following two paths satisfy the condition:

Sample Input 2

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

Sample Output 2

1

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



Sample input:
3 3
1 2
1 3
2 3


Sample output:
2

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10000)
N,M=list(map(int,input().split()))
links=defaultdict(list)
for i in range(M):
    a,b=list(map(int, input().split()))
    links[a].append(b)
    links[b].append(a)
ct=0
visited=[False]*N
def DFS(idx):
    global visited
    if all(visited):
        global ct
        ct+=1
        return
    for i in links[idx]:
        if visited[i-1]:
            continue
        visited[i-1]=True
        DFS(i)
        visited[i-1]=False
visited[0]=True
DFS(1)
print(ct)

Submission status: Accepted

Solution code:
from itertools import permutations

def main():
	n, m = list(map(int, input().split()))
	adj_list = [[] for _ in range(n)]
	for i in range(m):
		u, v = list(map(int, input().split()))
		adj_list[u-1].append(v-1)
		adj_list[v-1].append(u-1)
	pts = list(permutations(list(range(1, n))))
	
	#print(pts)
	ans = 0
	for pt in pts:
		cur = 0
		for nxt in pt:
			if nxt in adj_list[cur]:
				cur = nxt
			else:
				break
		else:
			ans += 1
	print(ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

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

ans = 0
global visit
visit = [1 for i in range(0,n)]

def dfs(s):
    if sum(visit) == 0:
        global ans
        ans += 1
        return
    for i in g[s]:
        # print(ans,visit)
        if visit[i] == 1:
            visit[i] = 0
            dfs(i)
            visit[i] = 1
    return

visit[0] = 0
dfs(0)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N, M = list(map(int, input().split()))
mtr = np.zeros((N, N), dtype=np.bool)
for _ in range(M):
    a, b = list(map(int, input().split()))
    mtr[a-1][b-1] = 1
    mtr[b-1][a-1] = 1
def v(i=0):
    return [_i for _i, _j in enumerate(mtr[i]) if _j]
def search_path(node, done):
    _d = done.copy()
    _d[node] = True
    if False not in _d:
        return [True]
    flag = [False]
    _v = [_i for _i in v(node) if not _d[_i]]
    if _v == []:
        return [False]
    return(np.concatenate([search_path(_i, _d) for _i in _v]))
print(list(search_path(0, np.zeros(N, dtype=np.bool))).count(True))

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split(' '))
neib = {}
for i in range(M):
    a, b = map(int, input().split(' '))
    if not a in neib.keys():
        neib[a] = [b]
    else:
        neib[a].append(b)
    if not b in neib.keys():
        neib[b] = [a]
    else:
        neib[b].append(a)

q = deque([])
q.append([1])
res = 0
while len(q) > 0:
    p = q.pop()
    if set(p) == set([i for i in range(1, N+1)]):
        res += 1
    cand = neib[p[-1]]
    for n in cand:
        if not n in p:
            q.append(p + [n])

print(res)

Submission status: Accepted

Solution code:
n,m=map(int, input().split())
q=[]
for i in range(m):
    a,b=map(int, input().split())
    q+=[[a,b],[b,a]]
p=[[1]]
count=0
while p:
    p1=p.pop()
    if len(p1)==n:count+=1
    else:
        for i,j in q:
            if i == p1[-1] and j not in p1:
                p.append(p1+[j])
    #print(p1,p)
print(count)

Submission status: Accepted

Solution code:

n,m=map(int, input().split())
q=[]
for i in range(m):
    a,b=map(int, input().split())
    q.append([a,b])
    q.append([b,a])
p=[[1]]
count=0
route=set()
while len(p)!=0:
    p1=p.pop()
    for i,j in q:
        #print(i,j)
        if i == p1[-1]:
            if j not in p1:
                p.append(p1+[j])
    if len(p1)==n: count+=1
    route |= {tuple(p1)}
    #print(p,p1)
print(count)

Submission status: Accepted

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

ans = 0

def dfs(v):
  global ans

  if all(visited):
    ans += 1
    return
  
  for i in range(n):
    if e[v][i] == False:
      continue
    if visited[i] == True:
      continue

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

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

Submission status: Accepted

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

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

b = [[0 for i in range(n)] for j in range(n)]
for i in a:
    b[i[0]][i[1]] = 1
    b[i[1]][i[0]] = 1


c = [i+1 for i in range(n-1)]
ans = 0
for i in itertools.permutations(c,n-1):
    j = [0]
    j += i
    count = 0
    for i in range(n-1):
        if b[j[i]][j[i+1]] == 1:
            count += 1
            if count == n-1:
                ans += 1
                count = 0
        else:
            break
print(ans)

Submission status: Accepted

Solution code:
import itertools

N, M = map(int, input().split())
nodes = [set(map(lambda x: int(x)-1, input().split())) for i in range(M)]
ans = 0
for path in itertools.permutations(range(N)):
    flag = True
    for i in range(N-1):
        if not ({path[i], path[i+1]} in nodes and path[0] == 0):
            flag = False
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy
import re
import math
from collections import deque, defaultdict
import itertools

def main():
	"""
	テストコード実行
	:return:
	"""
	"""
	連結を隣接行列で管理 + DFS
	"""
	n, m = map(int, input().split())
	table = [[0] * n for _ in range(n)] #隣接行列
	for _ in range(m):
		a, b = map(int, input().split())
		table[a - 1][b - 1] = 1
		table[b - 1][a - 1] = 1
	cnt = 0
	for pattern in itertools.permutations(range(n)): #全ての点が繋がっている状態は順列の積で記述
		if pattern[0] != 0: #スタートがゼロ(頂点1)でなかった場合
			break
		factor = 1
		for i in range(n - 1):
			factor *= table[pattern[i]][pattern[i + 1]] #0なら頂点1から繋がっておらず、1なら頂点1から全ての点へ繋がっている
		cnt += factor #頂点1から繋がっていれば加算

	print(cnt)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
from itertools import permutations

n, m = map(int, input().split())
edges = set()
for _ in range(m):
    a, b = map(int, input().split())
    edges.add((a, b))
    edges.add((b, a))

print(sum(all(move in edges for move in zip((1,)+p, p)) for p in permutations(range(2, n+1))))

Submission status: Accepted

Solution code:
from collections import defaultdict

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

D = defaultdict(list)

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

S = [[[1],1]] #Stack 初期はwalked=[1]のnow=1
ans = 0
def dfs(ans,S):
    while(len(S)>0):
        SS = S.pop()
        walked,now = SS[0],SS[1]
        #print(SS)
        for d in D[now]:
            if d not in walked:
                ans = dfs(ans,[[walked+[d],d]])
        if len(walked)==N: return ans+1
    return ans

print(dfs(ans,S))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
from collections import defaultdict

counter = 0

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

visited = []
def h(a):
    global counter
    visited.append(a)
    if len(visited) == N:
        counter += 1
        return
    for i in g[a]:
        if not i in visited:
            h(i)
            visited.remove(i)
h(1)
print(counter)

Submission status: Accepted

Solution code:
from itertools import permutations

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

matrix = [[0] * N for _ in range(N)]
for _ in range(M):
    u, v = map(int, input().split())
    matrix[u - 1][v - 1] = 1
    matrix[v - 1][u - 1] = 1

cnt = 0
for p in pe:
    for i in range(N - 1):
        if i == 0 and p[i] != 0:
            break
        if matrix[p[i]][p[i + 1]] == 1:
            continue
        else:
            break
    else:
        cnt += 1
print(cnt)

Submission status: Accepted

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

def f(L,k):
    for a in L:
        if a==k:
            return True
    return False

S=[i for i in range(1,N)]
ans =0
for s in permutations(S,N-1):
    flag =True
    if not f(table[0],s[0]):
        continue
    for i in range(N-2):
        if not f(table[s[i]],s[i+1]):
            flag =False
    if flag:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys

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

array = [[int(x) for x in input().split()] for x in range(m)]

if m == 0:
    print(0)
    sys.exit()

adj_array = [[] for x in range(n + 1)]
res_array = [True] + [False for x in range(n)]
for item in array:
    adj_array[item[0]].append(item[1])
    adj_array[item[1]].append(item[0])


def dfs(n, res_array, res):
    res_array[n] = True
    if False not in res_array:
        return res+1
    else:
        for next in adj_array[n]:
            if not res_array[next]:
                res = dfs(next, list(res_array), res)
    return res


res = 0
res_array[1] = True
print(dfs(1, res_array, res))

Submission status: Accepted

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

    ans = 0
    import itertools
    perm = list(itertools.permutations([j for j in range(1,n+1)]))
    for l in perm:
        if l[0] != 1:
            continue
        flag = 0
        for i in range(1, len(l)):
            if l[i] in g[l[i-1]]:
                pass
            else:
                flag = 1
                break
        if flag:
            continue
        ans+=1
    return ans

print(m())

Submission status: Accepted

Solution code:
def dfs(now,depth):
    if vis[now]:
        return 0
    if depth==n:
        return 1
    vis[now]=1
    ans=0
    for i in range(n):
        if graph[now][i]:
            ans+=dfs(i,depth+1)
    vis[now]=0
    return ans
n,m=map(int,input().split())
edge=[[int(i)for i in input().split()]for i in range(m)]
graph=[[0 for i in range(n)] for i in range(n)]
vis=[0]*n
for i in range(m):
    graph[edge[i][0]-1][edge[i][1]-1]=1
    graph[edge[i][1]-1][edge[i][0]-1]=1
print(dfs(0,1))

Submission status: Accepted

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

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

def search(now, gone):
    if len(gone) == N - 1:
        return 1

    s = 0
    for i in edge[now]:
        if i not in gone:
            hoge = gone.copy()
            hoge.add(now)
            s += search(i, hoge)
    return s

print(search(1, set()))

Submission status: Accepted

Solution code:
import itertools

l = input().split(' ')

N = int(l[0])
M = int(l[1])

S = [[0 for i in range(N)]for j in range(N)]

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

seq = list(range(2,N+1))
lst = list(itertools.permutations(seq))

#print(lst)
def solve(lst):
    bef = 1
    for k in lst:
        if S[bef-1][k-1] == 1:
            bef = k
        else:
            return False

    return True


ans = 0
for list in lst:
    if solve(list):
        ans += 1

print(ans)

Submission status: Accepted

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

# AtCoder Beginner Contest
# Problem C


# See:
# https://atcoder.jp/img/abc054/editorial.pdf
def dfs(v):
    all_visited = True

    if False in visited:
        all_visited = False

    if all_visited:
        return 1

    count = 0

    for i in range(n):
        if graph[v][i] == 0:
            continue

        if visited[i]:
            continue

        visited[i] = True
        count += dfs(i)
        visited[i] = False
    return count


if __name__ == '__main__':
    n, m = list(map(int, input().split()))
    graph = [[0 for __ in range(n)] for _ in range(n)]

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

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

    print(dfs(0))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
l = []
combo = []
for i in range(max(n, m)+1):
  l.append([])
  
def dfs(path, now):
  if len(set(path)) == n and not path in combo:
    combo.append(path)
    return

  for i in l[now]:
    if not i in path:
      temp = path[:]
      temp.append(i)
      dfs(temp, i)

  return

if m == 0:
  print(0)
else:

  for i in range(m):
    f, t = map(int, input().split())
    if not t in l[f]:
      l[f].append(t)
    
    if not f in l[t]:
      l[t].append(f)

  dfs([1], 1)
  print(len(combo))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
edges = [[] for _ in range(N + 1)]
res = 0
passed_nodes = set()

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

def recur(i, tot, pns):
    global res
    pns = pns.copy()

    if tot == N:
        res += 1
        return

    flag = False
    pns.add(i)

    for e in edges[i]:
        if e not in pns:
            recur(e, tot + 1, pns)
            flag = True

    if not flag:
        return

recur(1, 1, passed_nodes.copy())

print(res)

Submission status: Accepted

Solution code:
N, M  = map(int,input().strip().split())
edges = [[x for x in  map(int,input().strip().split())] for i in range(M)]
import numpy as np
a = np.zeros([N+1,N+1],dtype = np.int32) # adjacency matrix
for e in edges:
    a[e[0],e[1]] = 1
a = a.T+a
def iter(visited_nodes):
    if len(visited_nodes) == N:
        return 1
    else:
        now = visited_nodes[-1] 
        return sum(iter(visited_nodes+[node]) for node, aij in enumerate(a[now]) if aij == 1 and not (node in visited_nodes))
print(iter([1]))

Submission status: Accepted

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

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

def dfs(node,visited):
    global ans
    if visited.count(0) == 0:
        ans += 1 
        return 0
    else:
        visited[node] = 1
        for node_,edge_ in enumerate(H[node]):
            if edge_ == 1 and visited[node_] != 1:
                visited[node_] = 1
                visited[node] = 1
                dfs(node_,visited)
                
                #忘れない！！！
                visited[node_] = 0
dfs(0,l)
print(ans)

Submission status: Accepted

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

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

def dfs(node,visited):
    global ans
    if visited.count(0) == 0:
        ans += 1 
        return 0
    else:
        visited[node] = 1
        for node_,edge_ in enumerate(H[node]):
            if edge_ == 1 and visited[node_] != 1:
                visited[node_] = 1
                visited[node] = 1
                dfs(node_,visited)
                visited[node_] = 0
dfs(0,l)
print(ans)

Submission status: Accepted

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

n,m = map(int,input().split())
H = [[0 for _ in range(n)] for _ in range(n) ]

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

def dfs(node,visited):
    global ans
    if visited.count(0) == 0:
        ans += 1 
        return 0
    else:
        visited[node] = 1
        for node_,edge_ in enumerate(H[node]):
            if edge_ == 1 and visited[node_] != 1:
                visited[node_] = 1
                visited[node] = 1
                dfs(node_,visited)
                visited[node_] = 0

dfs(0,l)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- Coding: utf-8 -*-
n,m = map(int,input().split())

H = [[0 for _ in range(n)] for _ in range(n) ]

edge_list = []

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

def dfs(node,x):
    global ans
    if x.count(0) == 0:
        ans += 1 
        return 0


    else:
        visited = x
        visited[node] = 1
        for node_,edge_ in enumerate(H[node]):
            if edge_ == 1 and visited[node_] != 1:
                visited[node_] = 1
                visited[node] = 1
                dfs(node_,visited)
                visited[node_] = 0
                #頂点iをここで未訪問にすることが一番重要！！！！！



dfs(0,l)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

def f(n, m, uu, vv):
    a = [[0] * n for _ in range(n)]
    for u, v in zip(uu, vv):
       
        a[u][v] = 1
        a[v][u] = 1
 
    res = 0
    for p in permutations(range(n)):
        if p[0] != 0:
            break
     
        ok = True
        for i in range(n-1):
            if a[p[i]][p[i+1]] == 0:
                ok = False
                break
        if ok:
            res += 1
    return res


n,m = map(int,input().split())
a = []
b = []

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

print(f(n, m, a, b))

Submission status: Accepted

Solution code:
def dfs(now,depth):
    if vis[now]:
        return 0
    if depth==n:
        return 1
    vis[now]=1
    ans=0
    for i in range(n):
        if graph[now][i]:
            ans+=dfs(i,depth+1)
    vis[now]=0
    return ans
n,m=map(int,input().split())
edge=[[int(i) for i in input().split()]for i in range(m)]
graph=[[0 for i in range(n)]for i in range(n)]
for i in range(m):
    graph[edge[i][0]-1][edge[i][1]-1]=1
    graph[edge[i][1]-1][edge[i][0]-1]=1
vis=[0]*n
print(dfs(0,1))

Submission status: Accepted

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

a = [[0] * n for i in range(n)]

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

def dfs(v, n, visited):
    all_visited = 1
    for i in range(n):
        if visited[i] == 0:
            all_visited = 0

    if all_visited == 1:
        return 1

    ret = 0
    for i in range(n):
        if a[v][i] == 0:
            continue
        if visited[i] == 1:
            continue

        visited[i] = 1
        ret += dfs(i, n, visited)
        visited[i] = 0

    return ret

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

Submission status: Accepted

Solution code:
def dfs(now,depth):
    ans=0
    if vis[now]:
        return 0
    if depth==n:
        return 1
    vis[now]=1
    for i in range(n):
        if graph[now][i]:
            ans+=dfs(i,depth+1)
    vis[now]=0
    return ans
n,m=map(int,input().split())
edge=[[int(i) for i in input().split()]for i in range(m)]
graph=[[0 for i in range(n)]for i in range(n)]
for i in range(m):
    graph[edge[i][0]-1][edge[i][1]-1]=1
    graph[edge[i][1]-1][edge[i][0]-1]=1
vis=[0]*n
print(dfs(0,1))

Submission status: Accepted

Solution code:
def dfs(now,depth):
    if visited[now]:
        return 0
    if depth==n:
        return 1
    visited[now]=1
    ans=0
    for i in range(n):
        if connect[now][i]==1:
            ans+=dfs(i,depth+1)
    visited[now]=0
    return ans
n,m=map(int,input().split())
visited=[0]*n
edge=[[int(i)for i in input().split()]for i in range(m)]#入力値を受け取っている
connect=[[0 for i in range(n)]for i in range(n)]#隣接行列
for i in range(m):
    connect[edge[i][0]-1][edge[i][1]-1]=1
    connect[edge[i][1]-1][edge[i][0]-1]=1
print(dfs(0,1))

Submission status: Accepted

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

graph  = [[] for _ in range(N+1)]
for _ in range(M):
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)

visited = [0]*(N)
ans = 0

def DFS(pos):
    global visited
    global ans
    if sum(visited) == N:
        ans += 1
        return

    for i in graph[pos]:
        if visited[i-1]:
            continue
        visited[i-1] = 1
        DFS(i)
        visited[i-1] = 0
    return

visited[0] = 1
DFS(1)
print(ans)

Submission status: Accepted

Solution code:
import itertools

N, M = map(int, input().split())
patterns = list(itertools.permutations(range(2, N+1)))
path = [[0]*(N+1) for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    path[a][b] = 1
    path[b][a] = 1

ans = 0
for pattern in patterns:
    p = 1
    ok = True
    for x in pattern:
        if path[p][x] == 0:
            ok = False
            break
        p = x
    if ok:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
E_DICT = {}


def search_pass(v_idx, v_set, cnt):
    v_set2 = v_set.copy()
    v_set2.remove(v_idx)

    if len(v_set2) == 0:
        return cnt + 1

    e_tup = E_DICT[v_idx]

    for i in range(len(e_tup)):
        if e_tup[i] in v_set2:
            cnt = search_pass(e_tup[i], v_set2, cnt)

    return cnt


def main():
    n, m = map(int, input().split())
    v = {i+1 for i in range(n)}

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

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

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

    if m == 0:
        comb = 0
    else:
        comb = search_pass(1, v, 0)

    print(comb)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
edges = [input().split() for i in range(M)]
searched_edge = [0 for i in range(M)]
searched = [0 for i in range(N)]
stack = ['1']

count = 0
searched[0] = 1
def search(stack, searched, edges, searched_edge):
	global count
	
	while (stack):
		now = stack.pop()
		searched[int(now)-1] = 1
		
		if 0 not in searched:
			count += 1
			return
		
		for edge in edges:
			if now in edge:
				next = edge[1] if edge[0] == now else edge[0]
				searched_edge[edges.index(edge)] = 1
				if searched[int(next)-1] == 0:
					stack += [next]
					searched[int(next)-1] = 1
					search(stack, searched, edges, searched_edge)
					searched_edge[edges.index(edge)] = 0
					searched[int(next)-1] = 0

	return

search(stack, searched, edges, searched_edge)
print(count)

Submission status: Accepted

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

    ans = 0
    # 頂点1を除いて、この順番に頂点を回れるか試す
    route = itertools.permutations(range(2, N + 1), N - 1)
    for r in route:
        if not r[0] in edge[1]:
            # 頂点1からrが示す次の行き先に行くことができない
            continue
        count = 0
        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 = map(int, input().split())
P = [list(map(int, input().split())) for k in range(M)]
G = [[0 for k in range(N)] for k in range(N)]
for p in P:
    G[p[0]-1][p[1]-1] = G[p[1]-1][p[0]-1] = 1

def dfs(ima,itta):
    if len(itta)==N:
        return 1
    ans = 0
    for k in range(N):
        if ima[k]==1 and k not in itta:
            itta.append(k)
            ans += dfs(G[k],itta)
            itta.remove(k)
    return ans

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

Submission status: Accepted

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

visited = [1]
rest = [i for i in range(2, n + 1)]
ans = 0

def dfs(num):
    if rest == []:
        # print(visited)
        global ans
        ans += 1
    for i in range(m):
        if num in paths[i]:
            other = paths[i][1 - paths[i].index(num)]
            if other in rest:
                # print(other)
                visited.append(other)
                rest.remove(other)
                # print(visited, rest)
                dfs(other)
                visited.remove(other)
                rest.append(other)

dfs(1)
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
edges = [input().split() for x in range(M)]
path = []
for i in range(M):
  if '1' == edges[i][0]:
    path.append('1' + edges[i][1])

while 0 < len(path):
  if len(path[0]) == N:
    break 
  work = path.pop(0)
  for j in range(M):
    if (work[-1] == edges[j][0]) and edges[j][1] not in work:
      path.append(work + edges[j][1])
    elif (work[-1] == edges[j][1]) and edges[j][0] not in work:
      path.append(work + edges[j][0])

print(len(path))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
def dfs(now,depth):#現在見ている点、今まで列挙した頂点数
    if used[now]:
        return 0
    if depth==n:
        return 1
    used[now]=1#使用済みグラフを立てる
    ans=0#出力値を数える変数
    for i in range(n):#全部の遷移先を調べる
        if connect[now][i]:#nowから繋がっている頂点であれば遷移を試す。
            ans+=dfs(i,depth+1)
    used[now]=0#使用済みグラフを折る
    return ans
edge=[[int(i)for i in input().split()]for i in range(m)]#入力値受け取り、グラフの初期設定
connect=[[0 for i in range(n)]for i in range(n)]#接続状況を管理する配列
for i in range(m):
    connect[edge[i][0]-1][edge[i][1]-1]=1
    connect[edge[i][1]-1][edge[i][0]-1]=1
used=[0]*n#既にその頂点を訪問したか管理する配列
print(dfs(0,1))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
def dfs(now,depth):
    if used[now]:
        return 0
    if depth==n:
        return 1
    used[now]=1
    ans=0
    for i in range(n):
        if connect[now][i]:
            ans+=dfs(i,depth+1)
    used[now]=0
    return ans
edge=[[int(i)for i in input().split()]for i in range(m)]#入力値受け取り、グラフの初期設定
connect=[[0 for i in range(n)]for i in range(n)]
for i in range(m):
    connect[edge[i][0]-1][edge[i][1]-1]=1
    connect[edge[i][1]-1][edge[i][0]-1]=1
used=[0]*n
print(dfs(0,1))

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
s=[[]for i in range(N)]
w=0
for i in range(M):
    x,y=map(int,input().split())
    x,y=x-1,y-1
    s[x].append(y)
    s[y].append(x)
from itertools import permutations
for j in permutations(range(1,N)):
    j=[0]+list(j)
    for k in range(1,N):
        if j[k] not in s[j[k-1]]:
            break
    else:
        w+=1
print(w)

Submission status: Accepted

Solution code:
def dfs(x,c):
	if x==N-1:
		if all(visited):
			global ans
			ans += 1
		return

	for i in range(N):
		if neighbor[c][i] and not visited[i]:
			visited[i] = True
			dfs(x+1,i)
			visited[i] = False
		
N, M = map(int,input().split())
edge = [[int(i) for i in input().split()] for i in range(M)]
neighbor = [[False for i in range(N)] for i in range(N)]
visited = [False for i in range(N)]
for i in range(M):
	neighbor[edge[i][0]-1][edge[i][1]-1] = True
	neighbor[edge[i][1]-1][edge[i][0]-1] = True
	
ans = 0
visited[0] = True
dfs(0,0)
print(ans)

Submission status: Accepted

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

def dfs(v, N, visited):
  for i in range(1,N+1):
    if not visited[i]: break
    # すでに全て到達済みだったら
    if i == N: return 1

  ret = 0
  for i in range(1, N+1):
    if not graph[v][i]: continue
    if visited[i]: continue

    visited[i] = 1
    ret += dfs(i, N, visited)
    visited[i] = 0

  return ret

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

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

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

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n, m = [int(x) for x in input().split()]
adj = [[0]*n for i in range(n)]
visited = [0]*n
for i in range(m):
    a, b = [int(x) for x in input().split()]
    adj[a-1][b-1] = 1
    adj[b-1][a-1] = 1

ans = 0
def dfs(v):
    global ans
    if sum(visited) == n:
        ans += 1
    for i in range(n):
        if adj[v-1][i] == 1 and visited[i] == 0:
            visited[i] = 1
            dfs(i+1)
            visited[i] = 0

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

Submission status: Accepted

Solution code:
def bfs(g, n):
	tovisit = []
	for i in range(0, n):
		tovisit.append(i)
	queue = []
	tovisit.remove(0)
	queue.append([0, tovisit])
	cnt = 0

	while queue != []:
		status = queue.pop(0)
		now = status[0]
		currenttovisit = status[1]
		if currenttovisit == []: cnt = cnt + 1
		else:
			for i in range(0, n):
				newtovisit = []
				for j in range(0, len(currenttovisit)):
					newtovisit.append(currenttovisit[j])
				if i in currenttovisit and graph[now][i]:
					newtovisit.remove(i)
					queue.append([i, newtovisit])
	return cnt

N, M = map(int, raw_input().split())
graph = []
for i in range(0, N):
	arrow = []
	for j in range(0, N):
		arrow.append(False)
	graph.append(arrow)

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

print bfs(graph, N)