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:
def DFS(num):
    global ans,color
    color[num]="black"
    if "white" not in color:
        ans +=1
    for i in M[num]:
        if color[i]=="white":
            DFS(i)
    color[num]="white"


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

M=[[] for _ in range(n)]
color=["white" for _ in range(n)]
for a,b in AB:
    M[a-1].append(b-1)
    M[b-1].append(a-1)

ans=0
DFS(0)
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
G = dict([(i,[]) for i in range(1,N+1)])
for i in range(M):
  a,b = map(int,input().split())
  G[a].append(b)
  G[b].append(a)
#深さ優先探索  
l = [0]
def dfs(p,s):
  for i in G[p]:
    if s[i] == "0":
      a = s[:i] + "1" + s[i+1:]
      dfs(i,a)
  if s == "0" + N*"1":
    l[0] += 1
#捜査
s = "01"+(N-1)*"0"
    
dfs(1,s)
print(l[0])

Submission status: Accepted

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

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

ans = 0
for value in itertools.permutations([int(x) for x in range(1, n)]):
  if not node[0][value[0]]:
    continue
  flag = True
  for i in range(n-2):
    if not node[value[i]][value[i+1]]:
      flag = False
  if flag:
    ans += 1

print(ans)

Submission status: Accepted

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

G = {k: [] for k in range(N)}  # 0-indexed
for _ in range(M):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)


def dfs(p, arrived):
    if arrived == 2**N-1:
        return 1

    ret = 0
    for n in G[p]:
        if (arrived >> n) & 1 == 0:
            ret += dfs(n, arrived+2**n)
    return ret


arrived = 1
print(dfs(0, arrived))

Submission status: Accepted

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

conn = []
for _ in range(n):
    conn.append([False]*n)

visited = [False]*n #訪れたことのあるノード

#入力を元にconnを完成させる
v = []
for i in range(m):
    tmp = list(map(int, input().split()))
    v.append([x-1 for x in tmp])

#vを元にconnを作成
for start, end in v:
    conn[start][end] = conn[end][start] = True

def dfs(now, depth):
    if visited[now]:
        return 0
    if depth == n-1: #最後まで辿り着くことが出来た場合
        return 1

    visited[now] = True
    ret = 0

    for i in range(n):
        if conn[now][i]:
            ret += dfs(i, depth+1)

    visited[now] = False

    return ret

print(dfs(0, 0))

Submission status: Accepted

Solution code:
import itertools
def judge(a,b,edge): #a,bがedgeで繋がっていたらTrue、いなかったらFalse
    if edge[a][b] == 1:
        return True
    else:
        return False
n,m = map(int,input().split())
edge=[[0 for _ in range(n+1)] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int,input().split())
    edge[a][b] = 1
    edge[b][a] = 1
lis_permutations = itertools.permutations(range(2,n+1))
count = 0
for one_case in lis_permutations:
    one_case_1 = [1]
    for j in one_case:
        one_case_1.append(j)
    true = 1
    for i in range(len(one_case_1)-1):
        start = one_case_1[i]
        goal = one_case_1[i+1]
        if not judge(start,goal,edge):
            true = 0
            break
    if true ==1:
        count += 1
print(count)

Submission status: Accepted

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

c = 0
P = [0]*N
P[0] = 1
def bfs(start,used):
    global c
    for i in K[start]:
        M = used[:]
        k = 0
        if M[i] == 0:
            M[i] = 1
            for j in M:
                if j != 1:
                    k = 1
                    break
            if k == 0:
                c += 1
            else:
                bfs(i,M)

bfs(0,P)
print(c)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():

    N, M = map(int, input().split())
    G = defaultdict(lambda: [])

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

    # print(G)

    def dfs(v, is_visited):
        if sum(is_visited) == N:
            return 1
        ans = 0
        for u in G[v]:
            if is_visited[u]:
                continue
            is_visited[u] = True
            ans += dfs(u, is_visited)
            is_visited[u] = False

        return ans

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

    print(dfs(0, is_visited))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def DFS(s):
    global ans,color
    color[s]="black"
    if "white" not in color:
        ans +=1
    for i in M[s]:
        if color[i]=="white":
            DFS(i)
    color[s]="white"


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

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

color=["white" for _ in range(n)]
ans=0
DFS(0)

print(ans)

Submission status: Accepted

Solution code:
def DFS(s):
    global ans,color
    color[s]="gray"
    if "white" not in color:
        ans +=1
    for i in M[s]:
        if color[i]=="white":
            DFS(i)
    color[s]="white"


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

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

color=["white" for _ in range(n)]
ans=0
DFS(0)

print(ans)

Submission status: Accepted

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

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

ans=0
for A in permutations(range(n),n):
    if A[0]==0:
        for i in range(n):
            if i==n-1:
                ans +=1
                break
            if A[i+1] not in M[A[i]]:break

print(ans)

Submission status: Accepted

Solution code:
import itertools
from pprint import pprint

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

sides = [list(map(int,input().split())) for _ in range(m)]

#頂点を並び変える順列の総パターンを考える（ただし最初は「1」で固定）。
#総数は(N-1)! -> 7! -> 5040
#よって全探索は余裕そう。

vertexes = list(itertools.permutations(range(2,n+1)))

#pprint(vertexes)

counter = 0


for v in vertexes:
    #最初は1が始点
    for s in sides:
        if s[0] == 1 and s[1] == v[0]:
            break
        elif s[1] == 1 and s[0] == v[0]:
            break
    else:
        #この数列vはダメなので次のループへ
        continue

    for j in range(n-2):
        for s in sides:
            if v[j] == s[0] and v[j+1] == s[1]:
                break
            elif v[j] == s[1] and v[j+1] == s[0]:
                break
        else:
            break
    else:
        counter += 1



print(counter)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
from collections import deque

def main():
    N, M = map(int, readline().rstrip().split())
    path = [[False] * N for _ in range(N)]
    for _ in range(M):
        a, b = map(int, readline().rstrip().split())
        path[a-1][b-1] = True
        path[b-1][a-1] = True
    
    que = deque([[0]])  # 訪れた順にノードを格納
    cnt = 0
    while que:
        visited = que.popleft()
        if len(visited) == N:
            cnt += 1
            continue
        pre = visited[-1]
        for next in range(N):
            if next not in visited and path[pre][next]:
                que.append(visited+[next])
            
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

n, m = map(int, input().split())
graph = [[] for i in range(n)]
for i in range(m):
  a, b = map(int, input().split())
  graph[a-1].append(b)
  graph[b-1].append(a)
  
seen = [False]*n
finished = [False]*n
count = 0

def dfs(v):
  global graph
  global seen
  global count
  
  seen[v] = True
  if seen == [True]*n:
    count += 1

  for next_v in graph[v]:
    if seen[next_v-1]: 
      continue
    dfs(next_v-1)
    
  seen[v] = False
  	
dfs(0)
print(count)

Submission status: Accepted

Solution code:
import itertools

N, M = map(int, input().split())
pl = itertools.permutations([i for i in range(1, N + 1)])
ab = [list(map(int, input().split())) for _ in range(M)]
ans = 0
for l in pl:
    if l[0] != 1:
        continue
    f = True
    for i in range(N - 1):
        if not ([l[i], l[i + 1]] in ab or [l[i + 1], l[i]] in ab):
            f = False
            break
    if f:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import permutations
sys.setrecursionlimit(1000000) # 再帰上限を増やす

def main():
    input = sys.stdin.readline  # 文字列に対してinputした場合は、rstripするのを忘れずに！
    N, M = map(int, input().rstrip().split())
    path_list = []
    for _ in range(M):
        a, b = map(int, input().rstrip().split())
        path_list.append((a-1, b-1))
        path_list.append((b-1, a-1))

    count = 0
    for path in permutations(range(1, N)):
        now_posi = 0
        for next_posi in path:
            if (now_posi, next_posi) not in path_list:
                break
            now_posi = next_posi
        else:
            count += 1
    print(count)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from itertools import permutations

n, m = map(int, readline().split())
graph = [[] for _ in range(n + 1)]
for i in range(m):
    a, b = map(int, readline().split())
    graph[a].append(b)
    graph[b].append(a)
ans = 0
for check in permutations(range(1, n + 1)):
    if check[0] != 1:
        break
    for u, v in zip(check, check[1:]):
        if v not in graph[u]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
import copy
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)

ans=0
def bfs(v,chk,G):
    global ans
    #print(chk)
    if chk[v]!=0:
        return
    chk[v]=1
    if sum(chk)==N:
        ans+=1
    for tmp in G[v]:
        chk1=copy.copy(chk)
        bfs(tmp,chk1,G)

chk=[0]*N
bfs(0,chk,G)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict


n, m = map(int, input().split())
e = [list(map(int, input().split())) for _ in range(m)]
g = defaultdict(set)

for dep, dest in e:
    g[dep].add(dest)
    g[dest].add(dep)

def dfs(i, visited=[]):
    if len(visited) == n:
        return 1
    res = 0
    for node in g[i]:
        if node not in visited:
            visited.append(node)
            res += dfs(node, visited)
            visited.pop()
    return res

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

Submission status: Accepted

Solution code:
import itertools
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
s=list(itertools.permutations(range(1,n+1)))
count=0
for lis in s:
    flag=False
    if lis[0]==1:
        if all([lis[i],lis[i+1]] in l or [lis[i+1],lis[i]] in l for i in range(n-1)):
            count+=1          
print(count)

Submission status: Accepted

Solution code:
from itertools import permutations
from math import factorial

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

l = [i+1 for i in range(N)]
P = list(permutations(l))
P = P[:factorial(N-1)]

ans = 0
for p in P:
    path = True
    for i in range(len(p)-1):
        if not ((p[i],p[i+1]) in ab or (p[i+1],p[i]) in ab):
            path = False
            break
    if path:
        ans += 1

print(ans)

Submission status: Accepted

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

AB = []
for i in range(M):
    ab = list(map(int, input().split()))
    AB.append(ab)
    
import itertools

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

count = 0
for i in range(len(per)):
    #print(per[i])
    path = [1] + list(per[i])
    #print(path)
    
    for j in range(len(path)-1):
        p1 = [path[j], path[j+1]]
        p2 = [path[j+1], path[j]]
        if (p1 not in AB) and (p2 not in AB):
            break
    else:
        count += 1
        
print(count)

Submission status: Accepted

Solution code:
import itertools
import math
N, M = map(int, input().split())
a = []
ans = 0
for _ in range(M):
  a.append(set(map(int, input().split())))
for ind in itertools.permutations([i for i in range(N)]):
  if ind[0] != 0:
    break
  flag = True
  for i in range(N):
    if i == N-1:
      break
    if not(set([ind[i]+1, ind[i+1]+1]) in a):
      flag = False
  if flag:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m = map(int,input().split())
ab = []
count = 0
for i in range(m):
  ab.append(set(map(int,input().split())))
ns = [i for i in range(1,n+1)]
ptn = [i for i in list(itertools.permutations(ns)) if i[0]==1]
for i in ptn:
  first = i[0]
  for s in range(1,n):
    if {first,i[s]} not in ab:
      break
    first=i[s]
  else:
    count +=1
print(count)

Submission status: Accepted

Solution code:
import sys

N, M = map(int, sys.stdin.readline().rstrip().split())
edges = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

# N, Mが十分小さいため、全探索
ans = 0
visited = set()
def dfs(s, count):
    global ans;
    # print(s, visited)
    if count == N:
       ans += 1
       return
    visited.add(s)
    for e in edges[s]:
        if e not in visited:
            dfs(e, count+1)
    visited.remove(s)

dfs(0, 1)
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())))
ct = 0
N_lis = [(i + 2) for i in range(n - 1)]
Pat = itertools.permutations(N_lis)
for one_case in Pat:
    tmp = 1
    all_flag = True
    for j in one_case:
        flag = False
        for k in range(m):
            if AB[k][0] == tmp:
                if AB[k][1] == j:
                    tmp = j
                    flag = True
                    break
            elif AB[k][1] == tmp:
                if AB[k][0] == j:
                    tmp = j
                    flag = True
                    break
        if not flag:
            all_flag = False
            break
    if all_flag:
        ct += 1
print(ct)

Submission status: Accepted

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

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

graph_data = [[0] * N for i in range(N)]

for i in range(M):
    if A[i][0] > A[i][1]: A[i][0], A[i][1] = A[i][1], A[i][0]
    graph_data[A[i][0]-1][A[i][1]-1] = graph_data[A[i][1]-1][A[i][0]-1] = 1
    
visited = [False] * N

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

print(dfs(0,0))

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 itertools

N,M = map(int, input().split())
path = [[False] * N for x in range(N)]

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

count = 0
for j in itertools.permutations(range(N)):
    if j[0] != 0:
        continue
    for k in range(N):
        if k == N-1:
            count += 1
            break
        if not path[j[k]][j[k+1]]:
            break
print(count)

Submission status: Accepted

Solution code:

def dfs(node, paths, visited, n):
  # 全て訪問済みだったら全部を訪問できる経路として1を返す
  if not False in visited:
    return 1

  count = 0

  for nn in paths[node]:
    # 既に訪問済みなら処理をしない
    if(visited[nn]):
      continue

    visited[nn] = True
    count += dfs(nn, paths, visited, n)
    visited[nn] = False

  return count

def main():
  N, M = list(map(int, input().split()))
  paths = [[] for i in range(N)]
  visited = [False] * N

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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

ab=[[] for _ in range(n)]#１から順にどの頂点からどの頂点に辺が続いているか
for i in range(m):
    a,b=map(int,input().split())
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)

#print(ab)

l=list(range(1,n))
p = list(permutations(l, n - 1))#頂点をたどる順番。Nの階乗

ans=0
for i in p:
#    print(p)
    flg=0
    if i[0] not in ab[0]:
        continue   
    for j in range(n-2):
        if i[j+1] in ab[i[j]]:
            continue
        else:
            flg=1
            break
    if flg==0:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
n,m=map(int,input().split())
ab=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)
l=list(range(1,n))
p=list(permutations(l,n-1))
ans=0
for i in p:
    flg=0
    if i[0] not in ab[0]:
        continue   
    for j in range(n-2):
        if i[j+1] in ab[i[j]]:
            continue
        else:
            flg=1
            break
    if flg==0:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

n, m = [int(i) for i in input().split()]
g = [[False] * n for i in range(n)]
for i in range(m):
    a, b = [int(i) - 1 for i in input().split()]
    g[a][b] = g[b][a] = True

ans = 0
for i in permutations(list(range(n)), n):
    if i[0] != 0:
        break

    for j in range(n):
        if j == n - 1:
            ans += 1
            break
        if not g[i[j]][i[j+1]]:
            break

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for i in range(M):
  a, b = map(int, input().split())
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)
dp = [[0]*N for _ in range(1<<N)]
#dp[i][j]:=集合iをすでに通っていて、最後が頂点jのときの組み合わせ
dp[1][0] = 1

for bit in range(1<<N):
  for n in range(N):
    if(bit>>n & 1 == 0):
      continue
    for to in graph[n]:
      if(bit>>to & 1 == 1):
        continue
      next_bit = bit | (1<<to)
      dp[next_bit][to] += dp[bit][n]

ans = 0
for i in range(1, N):
  ans += dp[(1<<N)-1][i]
print(ans)

Submission status: Accepted

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

rel_t = [[False for i in range(n)] for j in range(n)]

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

cnt=0
n_list = [i for i in range(n)]
for l in permutations(n_list,len(n_list)):
    if(l[0]!=0):
        continue
    judge=[rel_t[l[i]][l[i+1]] for i in range(n-1)]
    if all(judge):
        cnt+=1

print(cnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)
n,m = map(int,input().split())
rel = [[False for i in range(n+1)] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    rel[a][b] = True
    rel[b][a] = True

ans=0
def rec(l):
    global ans
    if(len(l)==n):
        ans+=1
    x = l[-1]
    for i in range(1,n+1):
        if(i in l):
            continue
        if(rel[x][i]):
            rec(l+[i])

rec([1])
print(ans)

Submission status: Accepted

Solution code:
import itertools
n, m = map(int, input().split())
lst = [[] for _ in range(n)]
for _ in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    lst[x].append(y)
    lst[y].append(x)

perms = list(itertools.permutations( [_ for _ in range(n)]))

ans = 0
flg = 0
for _ in perms:
    if _[0] == 0:
        visited = [0 for _ in range(n)]
        visited[0] = 1
        for i in range(n-1):
            st = _[i]
            ed = _[i+1]
            if ed in lst[st] and visited[ed] == 0:
                visited[ed] = 1
            else:
                pass
        if sum(visited) == n:
            ans += 1
    else:
        pass          
print(ans)

Submission status: Accepted

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


def readstr():
    return input().strip()


def readint():
    return int(input())


def readnums():
    return map(int, input().split())


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


def main():
    N, M = readnums()
    ab = [list(readnums()) for _ in range(M)]
    l = range(2, N + 1)
    ans = 0
    for v in permutations(l):
        if [1, v[0]] in ab:
            flag = 1
            for i in range(N - 2):
                if [v[i], v[i + 1]] not in ab and [v[i + 1], v[i]] not in ab:
                    flag = 0

            if flag:
                ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import permutations
def main():
    n, m = map(int, input().split())
    path = []
    for _ in range(m):
        path.append(tuple(map(int, input().split())))

    nodes = [i for i in range(2, n + 1)]
    routes = permutations(nodes, n-1)

    r = 0
    for route in routes:
        route = list(route)
        route.insert(0,1)
        for i1 in range(n-1):
            if (route[i1], route[i1+1]) not in path:
                if (route[i1+1], route[i1]) not in path:
                    break
        else:
            r += 1
    print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

n,m = map(int,input().split())
path=[[False]*n for _ in range(n)]
for _ 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 itertools.permutations(range(n),n):
   if i[0] == 0:
     for j in range(n):
       if j==n-1:
         ans+=1
         break
       if not path[i[j]][i[j+1]]:
         break

print(ans)

Submission status: Accepted

Solution code:
N ,M = list(map(int, input().split()))
path = [[0]*N for i in range(N)]
visited = [0]*N
visited[0]=1
ans = 0
for i in range(M):
  a, b = list(map(int, input().split()))
  path[a-1][b-1]=1
  path[b-1][a-1]=1
  
def solve(i):
  global ans
  if not 0 in visited:
    ans += 1
    return
  else:
    for j in range(N):
      if path[i][j]==1 and visited[j] == 0:
        visited[j] = 1
        solve(j)
        visited[j] = 0
    return

solve(0)
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin


def dfs(g, seen, n):
    all_seen = True

    for si in seen:
        if si == False:
            all_seen = False

    if all_seen:
        return 1

    ans = 0

    for m in g[n]:
        if seen[m]:
            continue

        seen[m] = True
        ans += dfs(g, seen, m)
        seen[m] = False

    return ans


def main():
    n, m = map(int, stdin.readline().split())
    ab = [map(int, stdin.readline().split()) for _ in range(m)]
    g = [[] for _ in range(n)]
    for abi in ab:
        a, b = abi
        g[a - 1].append(b - 1)
        g[b - 1].append(a - 1)
    seen = [False for _ in range(n)]
    seen[0] = True

    ans = dfs(g, seen, 0)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():

    import itertools
    n, m = map(int,input().split())
    way_lis = []
    for _ in range(m):
        way_lis.append(list(map(int, input().split())))
    #print(way_lis)
    ans = 0

    point_lis = [x for x in range (1, n+1)]
    per_lis = list(itertools.permutations(point_lis))       #町の順列を全パターン作る
    per_1_lis = []
    for lis in per_lis:
        if lis[0] == 1:
            per_1_lis.append(lis)
    #print(per_1_lis)


    for town_set in per_1_lis:           #一つずつ町のセットをチェック
        cnt = 0
        for i in range(n-1):
            way_i = []
            #print(point_lis, point_lis[i])
            way_i.append(town_set[i])
            way_i.append(town_set[i+1]) #way_i = 町iと町i+1をつなぐ道              
            way_i.sort()        #町i/ 町i+1で小さい方を前に
            #print(way_i)
            for way in way_lis:
                #print(way_i, way, way_i==way)
                if way_i == way:
                    cnt += 1
            if cnt == 0:
                break
            elif cnt == n-1:
                ans += 1
    print(ans)
                
            



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools

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

path = [[False] * N for i in range(N)]

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

count = 0
for i in itertools.permutations(list(range(N)),N):
    if i[0] == 0:
        for j in range(N):
            if j == N-1:
                count += 1
                break
            if not path[i[j]][i[j+1]]:
                break
    

print(count)

Submission status: Accepted

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

import itertools
T=[i+2 for i in range(N-1)]
PMT=list(itertools.permutations(T))
#print(MAP)
#print(PMT)

ans=0
for i in range(len(PMT)):
    t=[1]+list(PMT[i])
    flag=True
    for j in range(N-1):
        if t[j+1] not in MAP[t[j]]:
            flag=False
            break
    if flag:
        #print(t)
        ans+=1

print(ans)

Submission status: Accepted

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


N, M = [int(str) for str in input().strip().split()]
ab = [[int(str) - 1 for str in input().strip().split()] for _ in range(M)]


def solve():
    G = [[False] * N for _ in range(N)]
    for a, b in ab:
        G[a][b] = True
        G[b][a] = True
    ans = 0
    for p in itertools.permutations(range(1, N), N - 1):
        pp = [0] + list(p)
        ans += all([G[pp[i]][pp[i + 1]] for i in range(N - 1)])
    print(ans)

solve()

Submission status: Accepted

Solution code:
from itertools import permutations
import sys


sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, M = map(int, input().split())
    perm = list(permutations(range(1, N)))
    edges = [[False] * N for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        edges[a][b] = True
        edges[b][a] = True

    ans = 0
    for P in perm:
        i = 0
        for j in P:
            if edges[i][j]:
                i = j
            else:
                break
        else:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools
n,m=map(int,input().split())
edge=[list(map(int,input().split())) for i in range(m)]
ans=0
nums=[i for i in range(1,n+1)]
rout=itertools.permutations(nums,n)
for r in rout:
  if r[0]!=1:
    continue
  lim=0
  while lim<n-1:
    if [r[lim],r[lim+1]] in edge or [r[lim+1],r[lim]] in edge:
      lim+=1
    else:
      lim=0
      break
  if lim:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
edge=[list(map(int,input().split())) for i in range(m)]
ans=0
rout=[[0 for i in range(n)]]
rout[0][0]=1
for i in range(2,n+1):
  rout2=[]
  for j in range(len(rout)):
    for k in range(n):
      if rout[j][k]==0:
        r=rout[j][:]
        r[k]=i
        rout2.append(r)
  rout=rout2
for r in rout:
  lim=0
  while lim<n-1:
    if [r[lim],r[lim+1]] in edge or [r[lim+1],r[lim]] in edge:
      lim+=1
    else:
      lim=0
      break
  if lim:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n , m = map(int, input().split())
r = [[0]*(9) for i in range(9)]
ans = 0
c = 0
for i in range(m):
    a , b = map(int, input().split())
    r[a][b]=1
    r[b][a]=1
d = deque([[1,[0,1,0,0,0,0,0,0,0]]])
while d:
    p=d.popleft()
    for i in range(1,n+1):
        if r[p[0]][i]==1 and p[1][i]==0:
            t=p[1].copy()
            t[i]=1
            if sum(t)==n:
                c+=1
            d.append([i,t])
            p[1][i]=0
print(c)

Submission status: Accepted

Solution code:
import itertools


def main():
    # 入力
    n, m = map(int, input().split())

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

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

    count = 0
    for perlist in permutations_lis:
        # 1は特殊
        i_current = 1
        i_already = {1}

        root = []

        countable = True
        for p in perlist:
            i_target = p

            found = False
            for ab in ablist:
                if ab in root:
                    continue
                if ab[0] == i_current and ab[1] == i_target:
                    root.append(ab)
                    i_current = ab[1]
                    found = True
                    break
                elif ab[1] == i_current and ab[0] == i_target:
                    root.append(ab)
                    i_current = ab[0]
                    found = True
                    break

            if not found:
                countable = False
                break

        if countable:
            count += 1

    print(count)


main()