Problem:


Score : 300 points

Problem Statement

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

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

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

Here, the endpoints of a path are considered visited.  

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

Figure 1: an example of an undirected graph

The following path shown in Figure 2 satisfies the condition.

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

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

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

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

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

Constraints

2≦N≦8 

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

1≦a_i<b_i≦N 

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

Input

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

N M  
a_1 b_1  
a_2 b_2
:  
a_M b_M  

Output

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

Sample Input 1

3 3
1 2
1 3
2 3

Sample Output 1

2

The given graph is shown in the following figure:

The following two paths satisfy the condition:

Sample Input 2

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

Sample Output 2

1

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



Sample input:
3 3
1 2
1 3
2 3


Sample output:
2

Submission status: Accepted

Solution code:
from itertools import permutations
n,m=map(int,input().split())
g=[[] for i in range(n)]
for _ in range(m):
  u,v=map(int,input().split())
  g[u-1].append(v-1)
  g[v-1].append(u-1)
ans=0
for v in permutations([int(i) for i in range(n)],n):
  if v[0]!=0:
    continue
  for i in range(n-1):
    if not v[i+1] in g[v[i]]:
      break
  else:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
def bit_DP(N,Adj):
    dp=[[0]*N for i in range(1<<N)]
    dp[1][0]=1
    for S in range(1<<N):
        for v in range(N):
            if (S&(1<<v))==0:
                continue
            sub=S^(1<<v)
            
            for u in range(N):
                if (sub&(1<<u)) and (Adj[u][v]):
                    dp[S][v]+=dp[sub][u]
    ans=sum(dp[(1<<N)-1][u] for u in range(1,N))
    return ans
def main():
    N,M=map(int,input().split())
    Adj=[[0]*N for i in range(N)]
    for _ in range(M):
        a,b=map(int,input().split())
        Adj[a-1][b-1]=1
        Adj[b-1][a-1]=1
    ans=bit_DP(N,Adj)
    print(ans)
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
# https://img.atcoder.jp/abc054/editorial.pdf

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

graph = [[False for _ in range(N)] for i 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, visited):
  all_visited = True
  for i in range(N):
    if not visited[i]:
      all_visited = False
      
  if all_visited:
    return 1
  
  ret = 0
  for i in range(N):
    if not graph[v][i]: continue
    if visited[i]: continue
    
    visited[i] = True
    ret += dfs(i, visited)
    visited[i] = False
  
  return ret

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

Submission status: Accepted

Solution code:
import sys
INF = 10**10
MOD = 10**9 + 7
sys.setrecursionlimit(100000000)
from functools import lru_cache
from itertools import permutations

def main():
    n,m = map(int,input().split())
    dist = [[1] * n for _ in range(n)]
    for _ in range(m):
        a,b = map(int,input().split())
        a -= 1
        b -= 1
        dist[a][b] = 0
        dist[b][a] = 0
    
    cnt = 0
    for ptr in permutations(range(1,n)):
        flag = True
        if  dist[0][ptr[0]]:
            continue

        for i in range(n - 2):
            if dist[ptr[i]][ptr[i + 1]]:
                flag = False
                break
        
        if flag:
            cnt += 1
    
    print(cnt)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

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

perms = itertools.permutations(range(1, N+1))
ans = 0
for perm in perms:
  if perm[0] != 1:
    continue
  is_goal = True
  for i in range(N-1):
    a = perm[i]
    b = perm[i+1]
    if not a < b:
      a, b = b, a
    if not [a, b] in ab:
      is_goal = False
  if is_goal:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def dfs(k,dep):
    if dep==n:
        return 1
    sm = 0
    for i in dst[k]:
        if used[i]:
            continue
        used[i] = True
        sm += dfs(i,dep+1)
        used[i] = False
    return sm

n,m = inm()
dst = {}
for i in range(m):
    a,b = inm()
    if a not in dst:
        dst[a] = {}
    dst[a][b] = 1
    if b not in dst:
        dst[b] = {}
    dst[b][a] = 1
used = [False]*(n+1)
used[1] = True
print(dfs(1,1))

Submission status: Accepted

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

ans = 0


# pos:現在地 visit:巡回済み頂点のリスト
def dfs(pos, visit):
    global l, ans
    f = True
    visit.append(pos)
    for d in l[pos]:
        if (d in visit):
            continue
        f = False
        dfs(d, visit.copy())

    if (f):
        if (len(visit) == N):
            ans += 1


dfs(0, [])
print(ans)

Submission status: Accepted

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

connect = [[0 for _ in range(n)] for _ in range(n)]
for a, b in edge:
    connect[a-1][b-1] = 1
    connect[b-1][a-1] = 1

import itertools
ans = 0
for l in itertools.permutations(range(1, n)):
    ok = True
    pre = 0
    for x in l:
        if connect[pre][x] == 0:
            ok = False
            break
        pre = x
    if ok:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
E = [[0] * N for i in range(N)] 
for i in range(M):
  a_i, b_i = map(int, input().split())
  a_i = a_i - 1
  b_i = b_i - 1
  E[a_i][b_i] = 1
  E[b_i][a_i] = 1

visited = [0]*N

def dfs(n, depth):
  if visited[n]: # already visited
    return 0
  
  if depth == N:
    return 1
  
  visited[n] = 1
  
  ans = 0
  for next_n in range(N):
    if E[n][next_n]:
      ans += dfs(next_n, depth+1)
  
  visited[n] = 0
  return ans

print(dfs(0,1))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
root = {i: [] for i in range(N)}
for i in range(M):
  a, b = map(int, input().split())
  root[a-1].append(b-1)
  root[b-1].append(a-1)
fact = 1
for i in range(N-1):
  fact *= (i+1)
realcnt = 0
for i in range(fact):
  p = [i for i in range(1, N)]
  L = []
  for j in range(N-1):
    L.append(i % (j + 1))
    i //= (j + 1)
  LL = [0]
  for j in range(N-1):
    LL.append(p[L[N-2-j]])
    p.remove(p[L[N-2-j]])
  cnt = 1
  for j in range(N-1):
    if LL[j+1] in root[LL[j]]:
      cnt += 1
  if cnt == N:
    realcnt += 1
print(realcnt)

Submission status: Accepted

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

root_dict = {str(i) : [] for i in range(1, N+1)}
for i in range(M):
    root = input().split()
    root_dict[root[0]] = root_dict[root[0]] + [root[1]]
    root_dict[root[1]] = root_dict[root[1]] + [root[0]]
result = 0
numbers = [str(i) for i in range(2, N+1)]
numbers = ''.join(numbers)

for order in itertools.permutations(numbers, N-1):#1以降の順列
    prev_num = "1"
    flag = True
    for num in order:
        if num not in root_dict[prev_num]:
            flag = False
            break
        prev_num = num
    if flag:
        result += 1

print(result)

Submission status: Accepted

Solution code:
from itertools import permutations

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

graph = [[] for _ in range(N)]

for a, b in ab:
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)

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

ans = 0

for p in permutations(perm):
    # 1開始でないならNG（辞書順なのでbreakでOK）
    if p[0] != 0:
        break
    flag = False
    for i in range(len(p) - 1):
        if not p[i + 1] in graph[p[i]]:
            flag = True
            break

    if not flag:
        # print(p)
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools


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

ans = 0
for p in itertools.permutations(range(1, n + 1)):
    if p[0] != 1:
        break

    for i in range(n - 1):
        for ai, bi in ab:
            if (p[i] == ai and p[i + 1] == bi
                    or p[i] == bi and p[i + 1] == ai):
                break
        else:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

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

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

for e in E:
    graph[e[0] - 1][e[1] - 1] = 1
    graph[e[1] - 1][e[0] - 1] = 1

res = 0

dp = [[0 for j in range(N)] for i in range(2**N)]
dp[1][0] = 1

for i in range(2**N):
    for j in range(N):
        for k in range(N):
            if not (i >> k & 1) and graph[j][k]:
                dp[(i)|(1 << k)][k] += dp[i][j]

print(sum(dp[-1]))

Submission status: Accepted

Solution code:
class Graph(): #non-directed
    def __init__(self,n,edge):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.deg = [0 for _ in range(n)]
        for e in edge:
            self.graph[e[0] - 1].append(e[1] - 1)
            self.graph[e[1] - 1].append(e[0] - 1)
            self.deg[e[0] - 1] += 1
            self.deg[e[1] - 1] += 1

from itertools import permutations

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

G = Graph(N, E)
res = 0

for p in permutations(range(N)):
    if p[0] != 0:
        continue
    for i in range(N - 1):
        if not p[i + 1] in G.graph[p[i]]:
            break
    else:
        res += 1

print(res)

Submission status: Accepted

Solution code:
import itertools

def resolve():
    n, m = map(int, input().split())
    S = [[0]*n for i in range(n)]

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

    ans = 0
    for p in itertools.permutations(range(n)):
        if p[0] != 0:
            break
        tmp = 1
        for i in range(n-1):
            tmp *= S[p[i]][p[i+1]]
        ans += tmp

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from itertools import permutations
N, M, *L = map(int, open(0).read().split())
dic = [[] for i in range(N+1)]
for a, b in zip(*[iter(L)]*2):
  dic[a].append(b)
  dic[b].append(a)

ans = 0
for l in permutations(range(2,N+1)):
  l = [1]+list(l)
  for i in range(N-1):
    if l[i+1] not in dic[l[i]]:
      break
  else:
    ans += 1
print(ans)

Submission status: Accepted

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

list_l = []
list_r = []
seen = [0]*n
sta = []
count = 0
sta.append(1)

for i in range(m):
  temp = list(map(int,input().split()))
  list_l.append(temp[0])
  list_r.append(temp[1])
  
def dfs(count):
  a = sta.pop()
  seen[a-1] = 1
  
  if not (0 in seen):
    count = count + 1

  for i,x in enumerate(list_l):
    if x == a:
      next_num = list_r[i]
      if seen[next_num-1] == 0:
        sta.append(next_num)
        count = dfs(count)
        seen[next_num-1] = 0
    
  for i,x in enumerate(list_r):
    if x == a:
      next_num = list_l[i]
      if seen[next_num-1] == 0:
        sta.append(next_num)
        count = dfs(count)
        seen[next_num-1] = 0
      
  return count

ans = dfs(0)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
n, m = map(int, input().split())
e = [[0] * n for i in range(n)]
v = [i for i in range(1, n)]
for i in range(m):
    a, b = map(int, input().split())
    e[a -1][b - 1] = e[b - 1][a - 1] = 1


ans = 0
for i in permutations(v):
    s = (0,)
    t = s + i
    flag = 1
    for j in range(n - 1):
        if e[t[j]][t[j + 1]] == 0:
            flag = 0
            break
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

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

tu = [[] for j in range(n+1)]

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

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

for nara in permutations(na):
    st = 1
    f = True
    for i in range(n-1):
        if not nara[i] in tu[st]:
            f = False
        st = nara[i]
    if f == True:
        ans += 1



print(ans)

Submission status: Accepted

Solution code:
import itertools

def resolve():
    n, m = map(int, input().split())
    S = [[0] * n for i in range(n)]

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

    ans = 0
    for p in itertools.permutations(range(n)):
        if p[0] != 0:
            break
        tmp = 1
        for i in range(n-1):
            tmp *= S[p[i]][p[i + 1]]
        ans += tmp

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
# サンプルコード計算量お試し

import itertools

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

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

cnt = 0

for each in itertools.permutations(range(N)):
    if each[0] != 0:
        break
    factor = 1
    for i in range(N-1):
        factor *= adj_matrix[each[i]][each[i+1]]
    cnt += factor

print(cnt)

Submission status: Accepted

Solution code:

import sys
import itertools
n,m = map(lambda x: int(x),input().split())
tree = [[]*n for i in range(n)]
l = [int(i) for i in range(n)]
ans_count = 0
for _ in range(m) :
    a,b = map(lambda x: int(x),input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
for v in itertools.permutations(l) :
    if v[0] != 0 :
        continue
    flag = 1
    for w in range(n-1) :
        if not v[w] in tree[v[w+1]] :
            flag = 0
    if flag == 1 :
        ans_count += 1
print(ans_count)

Submission status: Accepted

Solution code:
from collections import deque
import sys
n,m = map(lambda x: int(x),input().split())
sys.setrecursionlimit(26000)

tree = [[]*n for j in range(n)]
seen = [0]*n
seen[0] = 1
ans_conut = 0
def DFS(x) :
    global ans_conut
    if seen.count(1) == n :
        ans_conut +=1
        return

    for i in tree[x] :
        if seen[i] == 0 :
            seen[i] += 1
            DFS(i)
            seen[i] = 0



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

DFS(0)
print(ans_conut)

Submission status: Accepted

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

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

flag = (1<<n)-1

def dfs(v=0, visited=1):
    if visited == flag:
        return 1

    cnt = 0
    for to in G[v]:
        if visited & (1<<to):
            continue
        cnt += dfs(to, visited^(1<<to))
    return cnt

print(dfs())

Submission status: Accepted

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

#無向行列
path_matrix = []

#無向行列の初期化
for _ in range(N):
    path_matrix.append([False] * N)

for _ in range(M):
  line = map(int, input().split())
  paths = [x-1 for x in line]
  path_matrix[paths[0]][paths[1]] = True
  path_matrix[paths[1]][paths[0]] = True
  
visited = [False]*N

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
adj = [[] for _ in range(N)]
for _ in range(M):
  i,j = map(int, input().split())
  adj[i-1].append(j-1)
  adj[j-1].append(i-1)

ans = 0
def dfs(path):
  if len(path) == N:
    global ans
    ans += 1
  for next in adj[path[-1]]:
    if next not in path:
      dfs(path+[next])
dfs([0])
print(ans)

Submission status: Accepted

Solution code:
import itertools
n, m = map(int, input().split())
ab = []
for i in range(m):
    ab.append(list(map(int, input().split())))
per = list(itertools.permutations([i+1 for i in range(n)]))
ans = 0
for i in range(len(per)//n):
    # print(per[i])
    flug = True
    for j in range(n-1):
        way = list(per[i][j:j+2])
        # print(way, way[::-1], ab)
        if not((way in ab) or (way[::-1] in ab)):
            flug = False
            break
    if flug:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

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

# ２つの頂点間に辺がある時1に、ないときは0に設定する
for i in range(m):
    a, b = map(int, input().split())
    edge[a-1][b-1] = 1
    edge[b-1][a-1] = 1

# 頂点の順列の全てのパターンを[itertools.permutations()]で生成する
# 各並びで辺がない箇所があるかどうかの確認を積で行う
# 全ての頂点間の積が1であれば辺がすべて存在し、そのルートがあるということになる
res = 0
for each in itertools.permutations(range(n)):
    if each[0] != 0:
        break

    x = 1
    for i in range(n-1):
        x *= edge[each[i]][each[i+1]]
    
    res += x

print(res)

Submission status: Accepted

Solution code:
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]: continue

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

    return ret


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

graph = [[False for _ in range(8)] for _ in range(8)]


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 _ in range(N)]
visited[0] = True

print(dfs(0, N, visited))

Submission status: Accepted

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

N, M = map(int, input().split(' '))
path_map = {i:[] for i in range(1, N+1)}
for _ in range(M):
    a, b = map(int, input().split(' '))
    path_map[a].append(b)
    path_map[b].append(a)

ans = 0
for path in itertools.permutations(list(range(1, N+1))):
    if path[0] != 1:
        continue
    exist = True
    for i in range(N-1):
        if not path[i+1] in path_map[path[i]]:
            exist = False
            break
    if exist:
        ans += 1
print(ans)

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
import itertools

def main():
    mod=10**9+7
    N,M=MI()
    adj=[[] for _ in range(N)]
    for _ in range(M):
        a,b=MI()
        a-=1
        b-=1
        adj[a].append(b)
        adj[b].append(a)
        
        
    ans=0
    for ite in itertools.permutations(range(1,N), N-1):
        v=0
        f=1
        for nv in ite:
            if nv in adj[v]:
                v=nv
            else:
                f=0
                break
        ans+=f
        
    print(ans)
        
            
    

main()

Submission status: Accepted

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

def dfs(c, n, vis):
  for i in range(n):
    if not vis[i]:
      break
  else:
    return 1
  ret = 0
  for i in range(n):
    if not graph[c][i]:
      continue
    if vis[i]:
      continue
    vis[i] = True
    ret += dfs(i, n, vis)
    vis[i] = False
  return ret

print(dfs(0, N, visit))

Submission status: Accepted

Solution code:
from sys import stdin
import itertools 
N,M = [int(x) for x in stdin.readline().rstrip().split()]

edges = []
for m in range(M):
    a,b = [int(x) for x in stdin.readline().rstrip().split()]
    edges.append((a,b))
    edges.append((b,a))
    
node = list(range(1,N+1))

ans = 0
for i in itertools.permutations(node):
    f = True
    for j in range(len(i)-1):
        if (not (i[j],i[j+1]) in edges):
            f = False
    if f and i[0] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

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

for i in range(M):
    n,m=map(int,input().split())
    G[n].append(m)
    G[m].append(n)

visited=[0]*(N+1)
ans=0
def dfs(now, num_visited=0):
    global ans
    visited[now] = 1
    num_visited+=1
    
    if num_visited==N:
        ans+=1
    
    for i in G[now]:
        next=i
        if visited[next]!=1:dfs(next,num_visited)

    visited[now] = 0

dfs(1)
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
original_paths={}
paths={}
for n in range(1,N+1):
    original_paths[n]=[]
    paths[n]=[]
for m in range(1,M+1):
    s,e=map(int,input().split())
    original_paths[s].append(e)
    original_paths[e].append(s)
    paths[s].append(e)
    paths[e].append(s)#以上地図作り
    
visited=[1]
current_point=1
answer=0

while len(paths[1])!=0:#すべてのルートを探索済み==点1から動けない
    
    if len(paths[current_point])!=0:
        next_point=paths[current_point][0]
    
        if next_point in visited:#next_pointに行ったことがある

            if len(paths[current_point])!=1:#next_point以外に選択肢がある
                paths[current_point].remove(next_point)#next_pointを選択肢から消す

            else:#next_point以外に選択肢がない(current_pointは行き止まり)
                if len(visited)==N:#すべての点を訪れたかチェック
                    answer+=1
                prior_point=visited[-2]#ひとつ前にいた点をprior_pointとし、
                paths[current_point]=original_paths[current_point].copy()#current_pointからの選択肢を初期化
                paths[prior_point].remove(current_point)#prior_pointの選択肢からcurrent_pointを除く
                visited.remove(current_point)#current_pointをvisitedから除き、
                current_point=prior_point#prior_pointに戻る

        else:#next_pointに行ったことがない
            visited.append(next_point)#next_pointをvisitedに加え、
            current_point=next_point#next_pointに進む

    else:
        prior_point=visited[-2]#ひとつ前にいた点をprior_pointとし、
        paths[current_point]=original_paths[current_point].copy()#current_pointからの選択肢を初期化
        paths[prior_point].remove(current_point)#prior_pointの選択肢からcurrent_pointを除く
        visited.remove(current_point)#current_pointをvisitedから除き、
        current_point=prior_point#prior_pointに戻る
        
print(answer)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
original_paths={}
for n in range(1,N+1):
    original_paths[n]=[]
for m in range(1,M+1):
    s,e=map(int,input().split())
    original_paths[s].append(e)
    original_paths[e].append(s)#以上地図(原本)作り
    
visited=[1]
current_point=1
answer=0
import copy
paths=copy.deepcopy(original_paths)

while len(paths[1])!=0:#すべてのルートを探索済み==点1から動けない
    
    if len(paths[current_point])!=0:
        next_point=paths[current_point][0]
    
        if next_point in visited:#next_pointに行ったことがある

            if len(paths[current_point])!=1:#next_point以外に選択肢がある
                paths[current_point].remove(next_point)#next_pointを選択肢から消す

            else:#next_point以外に選択肢がない(current_pointは行き止まり)
                if len(visited)==N:#すべての点を訪れたかチェック
                    answer+=1
                prior_point=visited[-2]#ひとつ前にいた点をprior_pointとし、
                paths[current_point]=original_paths[current_point].copy()#current_pointからの選択肢を初期化
                paths[prior_point].remove(current_point)#prior_pointの選択肢からcurrent_pointを除く
                visited.remove(current_point)#current_pointをvisitedから除き、
                current_point=prior_point#prior_pointに戻る

        else:#next_pointに行ったことがない
            visited.append(next_point)#next_pointをvisitedに加え、
            current_point=next_point#next_pointに進む

    else:
        prior_point=visited[-2]#ひとつ前にいた点をprior_pointとし、
        paths[current_point]=original_paths[current_point].copy()#current_pointからの選択肢を初期化
        paths[prior_point].remove(current_point)#prior_pointの選択肢からcurrent_pointを除く
        visited.remove(current_point)#current_pointをvisitedから除き、
        current_point=prior_point#prior_pointに戻る
        
print(answer)

Submission status: Accepted

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

check = [0] * n
check[0] = 1


def dfs(x):
    ans = 0
    if min(check) == 1:  # 全ての探索が完了した時
        return 1  # 1を返す。
    for i in range(n):  # n個の頂点から一つずつ取り出して
        if vertex[x][i] == 1 and check[i] == 0:  # 頂点xから頂点iに移動でき、かつ未探索の時
            check[i] = 1  # 探索済みにする
            ans += dfs(i)  # pathの本数を加える
            check[i] = 0  # 未探索に戻す
    return ans  # pathの本数を出力する


print(dfs(0))

Submission status: Accepted

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

from collections import deque
def dws(st):
  ret = 0
  q = deque([])   # キュー
  q.append(st)
  while len(q) > 0:
    p = q.popleft()
    if len(p)==N:
      ret += 1
    else:
      for a in e[p[-1]]:
        if not a in p:
          q.append(p+[a])    # キュー追加
  return ret
print(dws([1]))

Submission status: Accepted

Solution code:
from itertools import permutations


n, m = map(int, input().split())
path = [[False] * n for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    path[a][b] = True
    path[b][a] = True
ans = 0
for i in permutations(range(n), n):
    if i[0] == 0:
        for j in range(n):
            if j == n - 1:
                ans += 1
                break
            elif not path[i[j]][i[j + 1]]:
                break
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
import copy
a=[0]*M
b=[0]*M
for i in range(M):
    a[i],b[i]=map(int,input().split())
D=[[1]]
def route(D):
    E=[]
    D1=copy.deepcopy(D)
    for j in range(len(D)):
        x=D[j][-1]
        for i in range(M):

            if a[i]==x:
                if not b[i] in D1[j]:
                    D[j]=copy.deepcopy(D1[j])
                    D[j].append(b[i])
                    E.append(D[j])
            elif b[i]==x:
                if not a[i] in D1[j]:
                    D[j]=copy.deepcopy(D1[j])
                    D[j].append(a[i])
                    E.append(D[j])
    return E
for i in range(N-1):
    D=copy.deepcopy(route(D))
print(len(D))

Submission status: Accepted

Solution code:
import itertools

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

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

reverse_edges = [e[::-1] for e in edges]
# print(edges)
# print(reverse_edges)
# print(edges + reverse_edges)
edges += reverse_edges

count = 0
start = 1
end = 1
for series in itertools.permutations(range(2, n + 1)):
    # print('candidate', series)
    start, end = 1, 1
    conflict = False
    for i in series:
        edge = (start, i)
        # print(edge)
        if edge not in edges:
            conflict = True
            # print('conflict', edge)
            break
        start = i
    if not conflict:
        count +=1

print(count)

Submission status: Accepted

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

def solve(cur, visited):
    if len(visited) == n:
        ans.append(1)
        return
    for i in graph[cur]:
        if not i in visited:
            solve(i, visited + [i])


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

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

solve(0, [0])
print(len(ans))

Submission status: Accepted

Solution code:
import itertools

n,m = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(m)]
pair = [[] for _ in range(n+1)]
for i in range(m):
    a = A[i][0]
    b = A[i][1]
    pair[a].append(b)
    pair[b].append(a)

ans = 0
li = [i for i in range(2,n+1)]
orders = list(itertools.permutations(li))

for order in orders:
    flag = True
    pre = 1
    for i in range(n-1):
        if not order[i] in pair[pre]:
            flag = False
        pre = order[i]
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools

def main():
    n, m = map(int, input().split())
    g = set([tuple(map(int, input().split())) for _ in range(m)])

    ans = 0
    for path in itertools.permutations(list(range(1, n+1)), n):
        if path[0] != 1:
            continue
        flag = True
        for i in range(n-1):
            if ((path[i], path[i+1]) not in g) and ((path[i+1], path[i]) not in g):
                flag = False
        if flag is True:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

visited = [0]*N
visited[0] = 1

def dfs(n) :
    ans = 0
    if min(visited) == 1 :
        return 1
    for i in range(N) :
        if G[n][i] == 1 and visited[i] == 0 :
            visited[i] = 1
            ans += dfs(i)
            visited[i] = 0
    return ans

print(dfs(0))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
graph = {i: [] for i in range(1, n + 1)}
for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

def dfs(i):
    ret = 0
    if all(han):
        return 1
    for j in range(1, n + 1):
        if han[j] == False and j in graph[i]:
            han[j] = True
            ret += dfs(j)
            han[j] = False
    return ret

han = [False] * (n + 1)
han[0] = True
han[1] = True
ans = dfs(1)
    
print(ans)

Submission status: Accepted

Solution code:
import itertools

[n,m] = [int(x) for x in input().split()]
data = [[int(x) for x in input().split()] for _ in range(m)]

total = 0
for x in itertools.permutations(range(2,n+1)):
    
    route = [1,]+list(x)
    
    for x in range(len(route)-1):
        flg = False
        
        for y in data:
            if {route[x],route[x+1]} == set(y):
                flg = True
                break
                
        if flg == False:
            break
            
    else:
        total += 1
        
print(total)