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())

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

cnt = 0
for each in permutations(range(N)):
    if each[0] != 0:
        break

    factor = 1
    for i in range(N-1):
        factor *= path_matrix[each[i]][each[i+1]]
    cnt += factor

print(cnt)

Submission status: Accepted

Solution code:
from collections import deque

def main():
    ans = 0
    N, M = map(int, input().split())
    graph = [[] for _ in range(N)]
    for _ in range(M):
        ai, bi = map(int, input().split())
        for j in range(1, N+1):
            if ai == j:
                graph[j-1].append(bi)
            elif bi == j:
                graph[j-1].append(ai)
        
    q = deque()
    q.append([1, {_ for _ in range(2, N+1)}])

    while q:
        prev, exist = q.popleft()

        if not exist:
            ans += 1
        for next in exist:
            if next in graph[prev-1]:
                q.append([next, exist-{next}])

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,M = LI()
    root = [[] for _ in range(N)]
    for _ in range(M):
        a,b = LI()
        root[a-1].append(b-1)
        root[b-1].append(a-1)
    node = [0] * N

    ans = 0
    q = []
    q.append((0,1))

    while q:
        u,d = q.pop()
        if d < 0:
            node[u] = 0
        else:
            node[u] = d
            q.append((u,-1))
            for v in root[u]:
                if node[v]: continue
                if d+1 == N: ans += 1
                else:
                    q.append((v,d+1))

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = list(map(int,input().split()))
graph = [[-1 for i in range(N)] for i in range(N)]
for i in range(M):
    a, b = list(map(int,input().split()))
    graph[a - 1][b - 1] = 1
    graph[b - 1][a - 1] = 1
    
def dfs(node, depth):
    global visited
    global ans
    if depth == N - 1:
        if sum(visited) == N:
            ans += 1
        return
    for i in range(1, N):
        if graph[node][i] == 1 and visited[i] == -1:
            visited[i] = 1
            dfs(i, depth + 1)
            visited[i] = -1
            
visited = [-1 for i in range(N)]
visited[0] = 1

ans = 0
dfs(0, 0)

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

side = [[] for k in range(n+1)] 

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

ans = 0  
for i in list(itertools.permutations(range(1, n+1), n)):
  if i[0] != 1:
    continue
  for j in range(n-1):
    if not i[j+1] in side[i[j]]:
      break
    if j == n-2:
      ans +=1
print(ans)

Submission status: Accepted

Solution code:
# C. One-stroke Path
# https://atcoder.jp/contests/abc054/tasks/abc054_c

from collections import deque

def dfs(i, visited):
    stack = deque()
    total = 0
    stack.append((i, visited))
    while stack:
        idx, vis = stack.popleft()
        if all(vis):
            total += 1
        for j in graph[idx]:
            if not vis[j]:
                v = vis[:]
                v[j] = True
                stack.append((j, v))
    return total

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)

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

Submission status: Accepted

Solution code:
# C. One-stroke Path
# https://atcoder.jp/contests/abc054/tasks/abc054_c

from collections import deque

def dfs(i, visited):
    stack = deque()
    total = 0
    stack.append((i, visited))
    while stack:
        idx, vis = stack.pop()
        if all(vis):
            total += 1
        for j in graph[idx]:
            if not vis[j]:
                v = vis[:]
                v[j] = True
                stack.append((j, v))
    return total

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)

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

Submission status: Accepted

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

dp = [[0]*n for _ in range(1<<n)]
dp[1][0] = 1
for num in range(1<<n):
    for v in range(n):
        if num & (1<<v) == 0:
            continue
        sub = num ^ (1<<v)

        for u in range(n):
            if sub & (1<<u) and list_MAP[v][u]:
                dp[num][v] += dp[sub][u]
ans = sum(dp[(1 << n) - 1])
print(ans)

Submission status: Accepted

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

dp = [[0]*n for _ in range(1<<n)]
dp[1][0] = 1
for num in range(1<<n):
    for v in range(n):
        if num & (1<<v) == 0:
            continue
        sub = num ^ (1<<v)

        for u in range(n):
            if sub & (1<<u) and list_MAP[v][u]:
                dp[num][v] += dp[sub][u]
ans = sum(dp[(1 << n) - 1][u] for u in range(1, n))
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

for i in range(m):
    a, b = map(int, input().split())
    my_set.add(a * 10 + b)
    my_set.add(b * 10 + a)

ret = 0
for item in itertools.permutations(range(1, n + 1)):
    is_ok = True
    if item[0] != 1:
        is_ok = False
    for i in range(len(item)-1):
        a, b = item[i], item[i+1]
        if a * 10 + b in my_set:
            continue
        else:
            is_ok = False
    if is_ok:
        ret += 1

print(ret)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
import itertools
graph={i:{} for i in range(1,N+1)}
for _ in range(M):
    a,b=map(int,input().split())
    graph[a][b]=1
    graph[b][a]=1
    
seq=[i+1 for i in range(N)]
Q=list(itertools.permutations(seq))
ans=0
for que in Q:
    flag=True
    s=que[0]
    if s!=1:
        flag=False
    for i in range(1,N):
        node=que[i]
        if node in graph[s]:
            s=node
        else:
            flag=False
        if flag==False:
            break
    ans+=int(flag)
print(ans)

Submission status: Accepted

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

graph=[[] for _ in range(N+1)]
for _ in range(M):
  a,b=map(int,input().split())
  graph[a].append(b)
  graph[b].append(a)
#print(graph)

answer=0
for perm in itertools.permutations(range(2,N+1)):
  path=[1]+list(perm)
  #print(path)
  
  for i in range(1,N):
    u=path[i-1]
    v=path[i]
    if not v in graph[u]:
      break
  else:
    answer+=1
    
print(answer)

Submission status: Accepted

Solution code:
A,B=list(map(int,input().split()))
n_l=[[] for i in range(A)]
from collections import deque
import itertools
for i in range(B):
   N,M= list(map( int,input().split()))
   n_l[N-1].append(M)
   n_l[M-1].append(N)
all_l=list(range(2,A+1))
first_list=[]
for i in n_l[0]:
   all_l_n=all_l.copy()
   for v in itertools.permutations(all_l_n):
      first_list.append(v)
ans=0
first_list=list(set(first_list))
for x in first_list:
   if x[0] in n_l[0]:
      s=1
      for k in range(len(x)-1):
         if x[k+1] in n_l[x[k]-1]:
            pass
         else:
            s=0
            break
      if s == 1:
         ans+=1
print(ans)

Submission status: Accepted

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

from itertools import permutations
lis=[i for i in range(2,n+1)]
permu=list(permutations(lis))

ans=0
for pl in permu:
    c=1
    j=1
    for i in pl:
        if j in G[i]:
            j=i
        else:
            c=0
            break
    ans+=c
print(ans)

Submission status: Accepted

Solution code:
def main():
    お寿司, 食べたい = map(int, input().split())
    築地 = [[] for _ in range(お寿司)]
    for _ in range(食べたい):
        鮪, 蛸 = map(lambda x: int(x) - 1, input().split())
        築地[鮪].append(蛸)
        築地[蛸].append(鮪)

    やってるかい = [False] * お寿司
    寿司くいねぇ = おなかすいた(0, 築地, やってるかい, 0)

    print(寿司くいねぇ)


def おなかすいた(市場, 築地, やってるかい, お勘定):
    やってるかい[市場] = True
    if all(やってるかい):
        return お勘定 + 1

    for 豪遊 in 築地[市場]:
        if やってるかい[豪遊]:
            continue
        お勘定 = おなかすいた(豪遊, 築地, やってるかい, お勘定)
        やってるかい[豪遊] = False

    return お勘定


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    g = [[] for _ in range(n)]
    for _ in range(m):
        u, v = map(lambda x: int(x) - 1, input().split())
        g[u].append(v)
        g[v].append(u)

    vis = [False] * n
    ans = dfs(0, g, vis, 0)

    print(ans)


def dfs(v, g, vis, count):
    vis[v] = True

    if all(vis):
        return count + 1

    for i in g[v]:
        if vis[i]:
            continue
        count = dfs(i, g, vis, count)
        vis[i] = False

    return count


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools 

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

ans = 0
for p in P:

  for i in range(n-1):

    if i==0:
      pnow = 0
      pnext = p[0]
    else:
      
      pnow = p[i-1]
      pnext = p[i]
    if pnext not in G[pnow]:
      break
  else:
    ans += 1
    continue
  
  
print(ans)

Submission status: Accepted

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

routes = [[] for _ in range(n)]
for i in range(m):
    routes[ab[i][0]-1].append(ab[i][1]-1)
    routes[ab[i][1]-1].append(ab[i][0]-1)

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

combinations = ["0"]
for k in range(n-1):
    combinations = [i+str(j) for j in options for i in combinations if str(j) not in i]

allcount = 0
for i in range(len(combinations)):
    for j in range(n-1):
        if int(combinations[i][j+1]) not in routes[int(combinations[i][j])]:
            break
    else:
        allcount+=1

print(allcount)

Submission status: Accepted

Solution code:
def dfs(v,children,checked):
  if len(checked)==len(children):
    return 1
  ans = 0
  for child in children[v]:
    if child in checked:
      continue
    ncheck = set(checked)
    ncheck.add(child)
    ans += dfs(child,children,ncheck)
  return ans

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

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

ans = dfs(0,children,set([0]))

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
G = [[] for k in range(N)]

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

def dfs(ima,visited):
    global ans
    visited[ima] = 1
    for tsugi in G[ima]:
        if visited[tsugi] == 0:
            visited[tsugi] = 1
            if sum(visited) == N:
                ans += 1
            dfs(tsugi,visited)
            visited[tsugi] = 0
ans = 0
dfs(0,[0]*N)
print(ans)

Submission status: Accepted

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

P=list(range(2,N+1))
ans=0
for p in permutations(P):
    que=[1]+list(p)
    #print(que)
    to=que.pop(0)
    route=G[to-1]
    count=1
    while len(que)>0:
        to=que.pop(0)
        if to-1 in route:
            count+=1
            route=G[to-1]
        else:
            #print("ok")
            break
    
    if count==N:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

INF = float("inf")

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

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

def I():
    return int(input())

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

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

def CI(n):
    return [ int(input()) for _ in range(n) ]

def LI(n):
    return [ list(map(int,input().split())) for _ in range(n) ]

def S():
    return input()

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

def RS():
    return list(input().split())

def CS(n):
    return [ input() for _ in range(n) ]

def LS(n):
    return [ list(input().split()) for _ in range(n) ]

n,m = RI()
ab = LI(m)

g = [ [] for _ in range(n) ]
for i in range(m):
    a = ab[i][0] - 1
    b = ab[i][1] - 1
    g[a].append(b)
    g[b].append(a)
# print(g)

l = list(range(1,n))
ls = list( permutations(l) )
# print(ls)

ans = 0
for i in range(len(ls)):
    flag = True
    v = [0]*n
    p = [0] + list(ls[i])
    # print(p)
    for j in range(len(p)-1):
        if v[p[j]]!=0:
            flag = False
        else:
            if p[j+1] in g[p[j]]:
                v[p[j]] = 1
            else:
                flag = False
    if flag:
        ans += 1
    else:
        pass

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
G = [[] for _ in range(n)]
for i in range(m):
    a,b = map(lambda x: int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
SAW = [False] * n

def dfs(v,SAW):
    global res
    end = True
    for i in range(n):
        if not SAW[i] and i != v:
            end = False
    if end:
        res += 1
        return
    SAW[v] = True
    for nv in G[v]:
        if SAW[nv]:
            continue
        dfs(nv,SAW)
    SAW[v] = False
res = 0
dfs(0,SAW)
print(res)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    from itertools import permutations
    N, M = (int(i) for i in input().split())
    edge = [[] for _ in range(N)]
    for i in range(M):
        a, b = (int(i) for i in input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)

    ans = 0
    for p in permutations(range(1, N)):
        v = 0
        for nv in p:
            if nv in edge[v]:
                v = nv
            else:
                break
        else:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import *

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

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

ans = 0

for p in permutations(range(N)):
    if p[0]!=0:
        continue
    
    flag = True
    
    for i in range(N-1):
        if p[i+1] not in G[p[i]]:
            flag = False
    
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

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

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

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

ans = 0
for i in permutations(range(N)):
    if i[0] != 0:
        continue
    else:

        flag = True
        for j in range(N-1):
            if not mat[i[j]][i[j+1]]:##つながってない
                flag = False
                break
        if flag:
            ans += 1 

print(ans)

Submission status: Accepted

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

n, m = [int(x) for x in input().split()]
g = [[]*n for _ in range(n)]
for _ in range(m):
    a, b = [int(x) for x in input().split()]
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
v = [int(x) for x in range(n)]
from itertools import permutations
v_per = list(permutations(v, n))
ans = 0
for per in v_per:
    if per[0] != 0:
        continue
    flag = 1
    for i in range(len(per) - 1):
        if per[i + 1] not in g[per[i]]:
            flag = 0
            break
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

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

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

ans = 0

for p in permutations(range(1, n)):
    if p[0] not in g[0]: continue
    for i in range(n-2):
        if p[i+1] not in g[p[i]]: break
    else: ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
N, M = map(int, input().split())
G = [[False] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    G[a][b] = True
    G[b][a] = True

ans = 0
for p in permutations(range(2, N + 1)):
    bl = G[1][p[0]]
    for x, y in zip(p[:-1], p[1:]):
        bl &= G[x][y]
    ans += int(bl)

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

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

toList = [set() for _ in range(N)]
for _ in range(M):
    fr, to = map(lambda a: int(a) - 1, input().split())
    toList[fr].add(to)
    toList[to].add(fr)

def countPath():
    ret = 0
    for P in permutations(range(N), r=N):
        if P[0] != 0:
            continue
        for fr, to in zip(P, P[1:]):
            if not to in toList[fr]:
                break
        else:
            ret += 1
    return ret

print(countPath())

Submission status: Accepted

Solution code:
import sys
from itertools import permutations

def solve():
    N, M = map(int, input().split())
    Edge = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        Edge[a-1].append(b-1)
        Edge[b-1].append(a-1)
    count = 0
    for order in permutations(range(N)):
        if order[0] != 0: continue
        for i in range(N-1):
            if order[i+1] not in Edge[order[i]]: break
        else: count += 1
    print(count)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(4100000)
n, m = map(int, input().split())
P = [[] for i in range(n)]   #Pass
for i in range(m):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1  
    P[a].append(b)
    P[b].append(a)
#print(P)

c = 0   #cursol
R = [0 for i in range(n)]  #Record
tm = 1  #time

def all_search_dfs(c:int, tm:int, R:list):
    if R[c] == 0:
        R[c] = 1
        if  tm < n:
            return point_calculate(c, tm, R)
        elif tm == n:
            return 1
        else:
            return 0
    else:
        return 0

def point_calculate(c:int, tm:int, R:list):
    #print('c = ', c)
    p = 0
    #print('check = ', P[c])
    for i in range(len(P[c])):
        R2 = R[:]
        #print('before = ', R2)
        tmp = all_search_dfs(P[c][i], tm + 1, R2)
        #print('after = ', R2)
        #print('tmp = ', tmp)
        p += tmp
        #print('p = ', p)
    return p

print(all_search_dfs(c, tm, R))

Submission status: Accepted

Solution code:
from itertools import permutations
import copy
n,m = map(int,input().split())
g = [[0]*n for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    g[a-1][b-1] = 1
    g[b-1][a-1] = 1
stock = list(permutations([i for i in range(1,n)]))
#print(stock)
ans = 0
for i in stock:
    h = copy.deepcopy(g)
    cnt = 1
    p = 0
    for k in i:
        if h[p][k] == 0:
            break
        else:
            cnt += 1
            p = k
    if cnt == n:
        ans += 1
    #print(i,cnt,h,g)
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

path_matrix = []

# 無向グラフの作成
for n in range(N):
    path_matrix.append([0] * N)

for m in range(M):
    paths = [int(i) - 1 for i in input().split()]
    path_matrix[paths[0]][paths[1]] = 1
    path_matrix[paths[1]][paths[0]] = 1

list_per = list(itertools.permutations(range(N)))
ans = 0

for i in list_per:
    if i[0] != 0:
        break
    cnt = 1
    for index in range(N - 1):
        cnt *= path_matrix[i[index]][i[index + 1]]
    ans += cnt
    
print(ans)

Submission status: Accepted

Solution code:
ans = 0
to = []

def main():
    global to
    n, m = map(int, input().split())
    to = [[] for i in range(n)]
    for i in range(m):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        to[a].append(b)
        to[b].append(a)
    #print(f'{to = }')
    solve(n, m)
    print(ans)

def dfs(pos, arrived):

    global ans

    #print(f'{pos = }')
    ##print(f'{to[pos] = }')

    arrived[pos] = True

    #全部到達した
    if all(arrived):
        #print('arrived')
        ans += 1
        return

    for nt in to[pos]:
        if arrived[nt] == False:
            dfs(nt, [i for i in arrived])

def solve(n, m):
    arrived = [False for i in range(n)]
    dfs(0, arrived)
    return


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())
  a -= 1
  b -= 1
  path[a][b] = True
  path[b][a] = True
  
ans = 0
 
#頂点を並び替える順列を生成してループ
for i in itertools.permutations(range(n),n):
  #頂点1が始点
  if i[0] == 0:
    #生成した順列の中をさらにループ
    for j in range(n):
      # n-1まで続いたら条件を満たすパスが存在する
      if j == n-1:
        ans += 1
        break
      #i[j]からi[j+1]に行くパスがなければ終了
      if not path[i[j]][i[j+1]]:
        break
        
print(ans)

Submission status: Accepted

Solution code:
import itertools
import sys

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

if M < N-1:
  print(0)
  sys.exit()

p = [i for i in range(N)] #点の数
root = []
for i in range(M):
  a,b = map(int,input().split())
  root.append((a-1,b-1))

#たどる点の順番の全探索
pattern = list(itertools.permutations(p))
#print(pattern)

ans = 0
for i in range(len(pattern)):
  if pattern[i][0] != 0:
    break
  Flag = True
  for j in range(N-1):
    if (pattern[i][j], pattern[i][j+1]) in root:
      continue
    elif (pattern[i][j+1], pattern[i][j]) in root:
      continue
    else:
      Flag = False
      break
  if Flag:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
n, m = map(int, input().split())
list_AB = [ list(map(int,input().split(" "))) for i in range(m)]
list_MAP = [[0]*n for _ in range(n)]
list_N = [i for i in range(2, n+1)]

for a, b in list_AB:
    list_MAP[a-1][b-1] = 1
    list_MAP[b-1][a-1] = 1

ans = 0

for l in permutations(list_N, n-1):
    cnt = 0
    p = 1
    q = 0
    for num in l:
        q = num
        cnt += list_MAP[p-1][q-1]
        p = num

    if cnt == n-1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools
a,b=map(int,input().split())
A=[]
for _ in range(a-1):
  A.append(_+2)
List=[list(map(int,input().split())) for i in range(b)]
count=0
for i in itertools.permutations(A):
  ju=True
  if [1,i[0]] in List or [i[0],1] in List:
    ju=True
  else:
    ju=False
  for j in range(a-2):
    if not([i[j],i[j+1]] in List) and not([i[j+1],i[j]] in List):
      ju=False
  if ju:
    count+=1
print(count)

Submission status: Accepted

Solution code:
class Graph():
    def __init__(self):
        """ ノードのつながりを辞書型で表現する """
        self.adjacency_dict = {}
    
    def add_vertex(self, v):
        """ ノードを追加する """
        self.adjacency_dict[v] = []
    def add_edge(self, v1, v2):
        """ ノード同士をつなぐ。"""
        # 無向グラフの場合は双方向。もし有向グラフなら片側のみ。
        self.adjacency_dict[v1].append(v2)
        self.adjacency_dict[v2].append(v1)
    def remove_edge(self, v1, v2):
        """ ノード同士のつながりを削除する。"""
        self.adjacency_dict[v1].remove(v2)
        self.adjacency_dict[v2].remove(v1)
    def remove_vertex(self,v):
        """ ノードを削除する。"""
        while self.adjacency_dict[v] != []:
            adjacent_vertex = self.adjacency_dict[v][-1]
            self.remove_edge(v, adjacent_vertex)
        del self.adjacency_dict[v]
    
    def print_graph(self):
        print(self.adjacency_dict)

    def _init_internal_graph(self, graph_dict):
        self.adjacency_dict = graph_dict
    
    def get_edge(self, v):
        """ 指定されたノードに関するエッジを返す。"""
        return self.adjacency_dict[v]

def dprint(*args):
  if debug:
    if len(args)==1:
      print(args[0])
    else:
      print(args)

debug = False
if debug:
  g = Graph()
  # N,M = [7, 7]
  # g._init_internal_graph({0: [2], 1: [6], 2: [0, 3], 3: [2, 4, 5], 4: [3, 5], 5: [3, 4, 6], 6: [1, 5]})
  
  N,M = [3, 3]
  g._init_internal_graph({0: [1, 2], 1: [0, 2], 2: [0, 1]})
else:
  N, M = map(int, input().split())
  g = Graph()
  dprint(N,M)

  for n in range(N):
    g.add_vertex(n)

  # 0-origin    
  for m in range(M):
      v1,v2 = list(map(int, input().split()))
      g.add_edge(v1-1,v2-1)                     

# g.print_graph()

seen = [False] * N
count = 0

def dfs(node, depth):
    dprint(node,depth)        
    if seen[node]:
        return 0
    if depth == N - 1:
        dprint('count-up',seen)
        return 1

    seen[node] = True
    dprint(seen)
    
    total_paths = 0
    for next_node in g.get_edge(node):
      total_paths += dfs(next_node, depth + 1)

    # seenを未到達にして次へ
    seen[node] = False

    return total_paths

count = dfs(0, 0)
print(count)

Submission status: Accepted

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

lis=list(range(1,n+1))
per_lis =[i for i in list(itertools.permutations(lis)) if i[0]==1]

ans=0

for one_case in per_lis:
    tmp=0
    for j in range(n-1):
        for num in ab:
            if one_case[j]==num[0] and one_case[j+1]==num[1]:
                tmp+=1
            elif one_case[j]==num[1] and one_case[j+1]==num[0]:
                tmp+=1
                    

        if tmp==n-1:
            ans+=1

print(ans)

Submission status: Accepted

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

lis=list(range(1,n+1))
per_lis = itertools.permutations(lis) 

ans=0

for one_case in per_lis:
    if one_case[0]==1:
        tmp=0
        for j in range(n-1):
            for num in ab:
                if one_case[j]==num[0] and one_case[j+1]==num[1]:
                    tmp+=1
                elif one_case[j]==num[1] and one_case[j+1]==num[0]:
                    tmp+=1
                    

        if tmp==n-1:
            ans+=1

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
n, m = map(int, input().split())
v = [set(map(int, input().split())) for _ in range(m)]

ans = 0
x = [i for i in range(2, n+1)]
cand = permutations(x)
for i in cand:
    crnt = 1
    for nxt in i:
        if set([crnt, nxt]) in v:
            crnt = nxt
        else:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
n , m = map(int,input().split())
hen = [list(map(int,input().split())) for _ in range(m)]
#n , m = 3,3 # n頂点の数　m辺の数
#hen = [[1, 2], [1, 3], [2, 3]]

ans = 0
x = [i for i in range(2,n+1)]
candi = itertools.permutations(x)
for i in candi: #
  now = 1
  for next in i: # j 次の頂点
    if [now,next] in hen or [next,now] in hen:
      now = next
    else:
      ck = 0
      break
  else:
    ans += 1

print(ans)

Submission status: Accepted

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

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


def dfs(node, visited):
  if all(visited):
    return 1

  res = 0
  for nei in adj_list[node]:
    if not visited[nei]:
      visited[nei] = True
      res += dfs(nei, visited)
      visited[nei] = False

  return res

cnt = 0
for node in adj_list[1]:
  visited = [False]*(N+1)
  visited[0],visited[1],visited[node] = True,True,True
  cnt += dfs(node, visited)

print(cnt)