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:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,M=MI()
    edge_matrix = [[False]*N for _ in range(N)]
    for _ in range(M):
        a,b = MI_()
        edge_matrix[a][b] = True
        edge_matrix[b][a] = True
    ans = 0
    for it in permutations([i for i in range(N)]):
        path = [i for i in it]
        if path[0]!=0:
            continue
        ok = True
        for i in range(N-1):
            from_ = path[i]
            to_ = path[i+1]
            if not edge_matrix[from_][to_]:
                ok = False
                break
        if ok:
            ans += 1
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

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


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):

    paths = list(zip(a, b))

    permutations = []
    for permutation in itertools.permutations(range(1, N + 1)):
        if permutation[0] == 1:
            permutations.append(permutation)
        else:
            break
    # print(permutations)
    result = 0
    for permutation in permutations:
        able = True
        for i in range(N - 1):
            if (
                permutation[i : i + 1 + 1] in paths
                or tuple(reversed(list(permutation[i : i + 1 + 1]))) in paths
            ):
                pass
            else:
                able = False
                break

        if able:
            result += 1

    print(result)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]"
    b = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, M, a, b)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

g = {}
n_path = 0
for i in range(N):
    g[i] = set()
for _ in range(M):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    g[a].add(b)
    g[b].add(a)

dp = [[0 for _ in range(N)] for _ in range(1 << N)]
dp[1][0] = 1

for bit in range(1 << N):
    for v in range(N):

        if bit & (1 << v) is False:
            continue

        sub = bit ^ (1 << v)

        for u in range(N):
            if (v in g[u]) and (sub & (1 << u)):
                dp[bit][v] += dp[sub][u]

print(sum(dp[-1]))

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
G = [[]for i in range(N)]
for i in range(M):
    a,b = map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
ans = 0
H = [[0]]
while H:
    h = H.pop()
    if len(h)==N:
        ans+=1
        continue
    p = h[-1]
    for v in G[p]:
        if not(v in h):
            H.append(h+[v])
print(ans)

Submission status: Accepted

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

g = {}
n_path = 0
for i in range(N):
    g[i] = []
for _ in range(M):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    g[a].append(b)
    g[b].append(a)


def advance(v, passed):

    global n_path
    passed.append(v)
    if len(passed) == N:
        n_path += 1

    for n in g[v]:
        if n not in passed:
            advance(n, passed)

    passed.remove(v)


advance(0, [])
print(n_path)

Submission status: Accepted

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

path=[[] for _ in range(n)]
for a,b in AB:
  path[a-1].append(b-1)
  path[b-1].append(a-1)

ans=0
for ptn in itertools.permutations(range(1,n)):
  start=0
  for nex in ptn:
    if start not in path[nex]: break
    start=nex
  else:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    G[a - 1].append(b - 1)
    G[b - 1].append(a - 1)
cnt = [0]
def dfs(V, s):
    V[s] = 1
    if sum(V) == N:
        cnt[0] += 1                    
    else:
        for adj in G[s]:
            if V[adj] == 0:             
                dfs(V[:adj] + [1] + V[adj + 1:], adj)  #ここで分岐がたくさん発生する
dfs([0] * N, 0)
print(cnt[0])

Submission status: Accepted

Solution code:
import numpy as np
def DFS(answer,matrix,color,N,i):
    if not 0 in color:
        answer[0]+=1
    for j in range(N):
        if color[j]==0 and matrix[i][j]==1:
            color[j] = 1
            DFS(answer,matrix,color,N,j)
            color[j] = 0
    
def main():
    N,M = map(int,input().split())
    S = [list(map(int,input().split())) for _ in range(M)]
    matrix = np.zeros([N,N],dtype=np.int32)
    for s in S:
        matrix[s[0]-1][s[1]-1]=1
        matrix[s[1]-1][s[0]-1]=1
    color = [0]*N
    color[0] = 1
    answer = [0]
    DFS(answer,matrix,color,N,0)
    print(answer[0])
    

if __name__=='__main__':
    main()

Submission status: Accepted

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

for i in range(n):
    paths.append([0]*n)

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

def dfs(now,depth):
    if visited[now]==1:
        return 0
    elif depth==n-1:
        return 1
    else:
        visited[now]=1
        total=0
        for i in range(n):
            if paths[now][i]==1:
                total+=dfs(i,depth+1)
        visited[now]=0
        return total
print(dfs(0,0))

Submission status: Accepted

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

from collections import defaultdict
d = defaultdict(list)
for _ in range(m):
    a, b = map(int, input().split())
    d[a].append(b)
    d[b].append(a)

from itertools import permutations
C = permutations(range(2, n+1))
C = list(map(lambda x: [1]+list(x), C))

ans = 0
for c in C:
    for i in range(n-1):
        if c[i+1] not in d[c[i]]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
import copy

n, m = map(int, input().split())
List = [list(map(int, input().split())) for i in range(m)]
check = [0 for _ in range(n)]
res = 0

def all_1(res_list):
    leng = len(res_list)
    for i in range(leng):
        if res_list[i] == 0:
            return False
    return True

def coo(i, check):
    global res
    b = copy.deepcopy(check)
    if b[i-1] == 0:
        b[i-1] = 1
        if all_1(b):
            res += 1
        length = len(List)
        for j in range(length):
            if List[j][0] == i:
                coo(List[j][1], b)
        for j in range(length):
            if List[j][1] == i:
                coo(List[j][0], b)
        
        
coo(1, check)
print(res)

Submission status: Accepted

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

def func(path,p,count):
  if len(path) == n:
    return count + 1
  for i in graph[p]:
    if i in path:
      continue
    count = func(path+[i],i,count)
  return count
print(func([1],1,0))

Submission status: Accepted

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

def func(path,p,count):
  if len(path) == n:
    return count + 1
  for i in graph[p]:
    if i in path:
      continue
    count = func(path+[i],i,count)
  return count
print(func([1],1,0))

Submission status: Accepted

Solution code:
import itertools
N, M = [int(x) for x in input().split()]
lst = [[int(x) for x in input().split()] for i in range(M)]
N_lst = list(range(1, N + 1))
per = []

def check(tup):
    for i in range(N - 1):
        x = tup[i]
        y = tup[i + 1]
        if x > y:
            x, y = y, x
        if not [x, y] in lst:
            return False
    return True

for v in itertools.permutations(N_lst):
    if v[0] == 1:
        per.append(v)
cnt = 0
for p in per:
    if check(p): cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import numpy as np
nmax = 8
graph = np.array([[False]*nmax]*nmax)
 
n, m = map(int, input().split())
for i in range(m):
    a, b = map(int, input().split())
    graph[a-1][b-1] = graph[b-1][a-1] = True
    
visited = [False]*nmax
visited[0] = True
 
def dfs(v, n, visited): # v：今訪れた頂点
    all_visited = True
    for i in range(n):
        if visited[i] == False:
            all_visited = False
 
    if all_visited:
        return 1 #1通り
    
    ret = 0 #最初は0通り
    
    for i in range(n):
        if graph[v][i] == False: #vからiに行けない場合は除外
            continue
        if visited[i]: #iを訪問済みだったら行かない
            continue
        
        visited[i] = True #vからiに訪問
        ret += dfs(i, n, visited) #今iにいる時の次の動作
        visited[i] = False #iではないところにいくケース
        
    return ret
  
print(dfs(0, n, visited))

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):
    #print(i)
    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:
import sys
sys.setrecursionlimit(10 ** 6)
n,m=map(int,input().split())
g=[[]for i in range(n)]; ans=0
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(x,visited):
  global ans
  # print(x,visited)
  for p in g[x]:
    if visited[p]==0:
      visited[p]=1
      if visited.count(1)==n:
        ans+=1
        # print(ans)
      else: 
        dfs(p,visited)
      visited[p]=0
v=[0]*n
v[0]=1
dfs(0,v)
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
A=[list(map(int,input().split())) for _ in range(M)]
D=[[]for i in range(N)]
for u,v in A:
  D[u-1].append(v-1)
  D[v-1].append(u-1)

def dfs(x,used):
  if len(used)==N:
    return 1
  ans=0
  for i in D[x]:
    if i not in used:
      ans+=dfs(i,used+[i])
  return ans
print(dfs(0,[0]))

Submission status: Accepted

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

def dfs(i, used):
    if len(used) == N:
        return 1
    ans = 0
    for j in edges[i]:
        if j not in used:
            ans += dfs(j, used+[j])
    return ans
print(dfs(0, [0]))

Submission status: Accepted

Solution code:
import itertools

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

count = 0
for path in itertools.permutations([i for i in range(2, N+1)], N-1):
  flag = True
  if [1, path[0]] in ab or [path[0], 1] in ab:
    pass
  else:
    flag = False
    continue
  for i in range(1, N):
    if flag:
      if i == N-1:
        count += 1
        continue
      if [path[i-1], path[i]] in ab or [path[i], path[i-1]] in ab:
        continue
      else:
        flag = False
print(count)

Submission status: Accepted

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

sum_n = sum([i for i in range(n + 1)])

all_route = []
def dfs(i, r, o):
  route = r
  o_v = o
  route.append(i)
  o_v.append(i)
  v_num = [v[1] for v in a if v[0] == i and v[1] not in o_v]
  v_num += [v[0] for v in a if v[1] == i and v[0] not in o_v]
  if len(v_num) == 0:
    all_route.append(route[:])
    
  else:
    for v in v_num:
      dfs(v, route[:],o_v[:])    

dfs(1, [], [])
all_route_scores = [sum(route) for route in all_route]
r = all_route_scores.count(sum_n)

print(r)

Submission status: Accepted

Solution code:
import itertools


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

ans = 0
node = list(range(1, N+1))
for x in itertools.permutations(node):
    if x[0] == 1:
        for i in range(N-1):
            if not edge[x[i]][x[i+1]]:
                break
        else:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc054/tasks/abc054_c

import math,itertools,fractions,heapq,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

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

def dfs(n,v,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 visited[i]:
      continue
    if graph[i][v]==False:
      continue
    visited[i]=True
    ret+=dfs(n,i,visited)
    visited[i]=False

  return ret

def main():
  n,m=LI()
  for _ in range(m):
    a,b=LI()
    a-=1
    b-=1
    graph[a][b]=True
    graph[b][a]=True

  visited=[False]*n
  visited[0]=True
  return dfs(n,0,visited)

# main()
print(main())

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD

N,M = imn()

graph = [[False for _ in range(N)] for _ in range(N)]
for i in range(M):
    A,B = map(lambda x:int(x)-1, input().split())
    graph[A][B] = True
    graph[B][A] = 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, copy.deepcopy(visited))
        visited[i] = False

    return ret

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

print(dfs(0, visited))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
import sys, heapq, bisect, math, itertools, string, queue, copy, time
from fractions import gcd
import numpy as np
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
EPS = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())


ans = 0
N, M = map(int, input().split())
path = [[False]*N for _ in range(N)]
# 0 to N-1, N nodes
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    path[a][b] = True
    path[b][a] = True


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

print(ans)

Submission status: Accepted

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

edges = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)
cnt = 0
for path in itertools.permutations(range(1, n)):
    # 0はじまり
    path = [0] + list(path)
    flg = True
    for i in range(1, n):
        if path[i] not in edges[path[i-1]]:
            flg = False
            break
    if flg:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
from itertools import permutations
n,m = map(int, input().split())
d = {}
for _ in range(m):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    if a not in d:
        d[a] = {}
    if b not in d:
        d[b] = {}
    d[a][b] = d[b][a] = 1

ans = 0
for route in permutations(range(1,n)):
    if route[0] not in d[0]:
        continue
    for j in range(n-2):
        if route[j+1] not in d[route[j]]:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
ab = {i:[] for i in range(N)}
for _ in range(M):
    a, b = list(map(int, input().split()))
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)
    
cand = [[0]+[one] for one in ab[0]]
while len(cand)>0 and len(cand[0])<N:
    tmp_cand = []
    for c in cand:
        last = c[-1]
        n = []
        for nc in ab[last]:
            if nc not in c:
                n.append(c+[nc])
        tmp_cand.extend(n)
    cand = tmp_cand
print(len(cand))

Submission status: Accepted

Solution code:
import itertools
n,m=map(int,input().split())
es=[set() for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    es[a-1].add(b-1)
    es[b-1].add(a-1)
ans=0
for v in itertools.permutations(range(1,n)):
    u=0
    link=True
    for i in v:
        if i in es[u]:
            u=i
        else:
            link=False
            break
    if link:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

for _ in range(M):
	ta, tb = map(int, input().split())
	E[ta-1].append(tb-1)
	E[tb-1].append(ta-1)

ans = 0

for p in itertools.permutations(range(1,N)):
	p = [0] + list(p)
	cond = 1
	for i in range(N-1):
		if p[i+1] not in E[p[i]]:
			cond = 0
	if cond:
		ans += 1


print(ans)

Submission status: Accepted

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

for _ in range(M):
	ta, tb = map(int, input().split())
	E[ta-1].append(tb-1)
	E[tb-1].append(ta-1)


def next_permutation(out, cnt, flg):
	if cnt == N:
		for i in range(N-1):
			if out[i+1] not in E[out[i]]:
				return 0
		return 1

	ans = 0

	for i in range(N):
		if flg[i] == 0:
			out.append(i)
			flg[i] = 1

			ans += next_permutation(out, cnt+1, flg)

			out.pop()
			flg[i] = 0

	return ans

perm = [0]
cnt = 1
flg = [0 for _ in range(N)]
flg[0] = 1

answer = next_permutation(perm, cnt, flg)

print(answer)

Submission status: Accepted

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

def dfs(v, used, cnt):
    used[v] = 1
    if all(used):
        cnt.append(1)
    for nv in es[v]:
        if used[nv]:
            continue
        dfs(nv, used, cnt)
    used[v] = 0

used = [0] * N
cnt = []
dfs(0, used, cnt)

print(sum(cnt))

Submission status: Accepted

Solution code:
import numpy as np
import itertools #from itertools import *
N,M=map(int,input().split())
G=np.zeros((N+1,N+1),dtype=np.int32)
for i in range(M):
  a,b=map(int,input().split())
  G[a][b]=1
  G[b][a]=1
#print(G)
ans=0
for i in itertools.permutations(range(2,N+1)):
  cnt=0
  for j in range(N-2):
    if G[i[j]][i[j+1]]!=0:
      cnt+=1
  if G[1][i[0]]==1:
    cnt+=1
  if cnt==N-1:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
N , M = map(int , input().split())
A = [list(map(int,input().split())) for i in range(M)]
tf = [False]*N

for i in range(M):
    A.append(list(reversed(A[i])))

def saiki(aaa):
    ans = 0
    if all(tf) == True:
        return 1
    stack = []
    for i in range(len(A)):
        if A[i][0] == aaa and tf[A[i][1]-1] == False:
            stack.append(A[i][1])

    for i in range(len(stack)):
        tf[stack[i]-1] = True
        ans += saiki(stack[i])
        tf[stack[i]-1] = False
    return ans

def main():
    tf[0] = True
    ans = saiki(1)
    print(ans)

if __name__ == '__main__':
    main()

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)

visited = [True]*N
visited_all = [False]*N
cnt = [0]

def dfs(visited, pos):
  visited[pos] = False
  if visited == visited_all:
    cnt[0] += 1
  else:
    for p in G[pos]:
      if visited[p] == False:
        continue
      dfs(visited, p)
      visited[p] = True

dfs(visited, 0) 
print(cnt[0])

Submission status: Accepted

Solution code:
import itertools
n, m = list(map(int, input().split()))
a = [list(map(int, input().split())) for _ in range(m)]
y = 0
s = []
for i in range(1, n):
  s.append(i+1)
for x in itertools.permutations(s):
  if [1, int(x[0])] in a:
      for i in range(n-2):
          if not [int(x[i]), int(x[i+1])] in a and not [int(x[i+1]), int(x[i])] in a:
            break
      else: y += 1
print(y)

Submission status: Accepted

Solution code:
import itertools
import copy
n, m = map(int, input().split())
graph = [[] * n for i in range(n)]
for _ in range(m):
    num_from, num_to = map(int, input().split())
    graph[num_from - 1].append(num_to - 1)
    graph[num_to - 1].append(num_from - 1)

count = 0
node_list = [i + 1 for i in range(n - 1)]
for pattern in itertools.permutations(node_list):
    pattern_list = list(pattern)
    pattern_list.insert(0, 0)
    can_arrive = False
    for i in range(n):
        if i == n - 1:
            can_arrive = True
            break
        if pattern_list[i + 1] not in graph[pattern_list[i]]:
            can_arrive = False
            break
    if can_arrive:
        count += 1

print(count)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, m = [int(x) for x in input().strip().split()]
g = [[0] * n for _ in range(n)]
for i in range(m):
    a, b = [int(x) for x in input().strip().split()]
    g[a-1][b-1] = 1
    g[b-1][a-1] = 1

flags = [False] * n
def dfs(flags, v):
    if flags.count(False) == 1:
        return 1
    flags[v] = True
    ret = 0
    for i, f in enumerate(g[v]):
        if f == 0 or flags[i]:
            continue
        ret += dfs(flags[:], i)
    return ret

print(dfs(flags[:], 0))

Submission status: Accepted

Solution code:
n,m=[int(x) for x in input().split()]
edges=[[] for x in range(n)]
for i in range(m):
    a,b=[int(x)-1 for x in input().split()]
    edges[a].append(b)
    edges[b].append(a)
def ans(path):
    if len(path)==n:
        # print([x+1 for x in path])
        return 1
    res=0
    for i in range(n):
        if not i in path and  i in edges[path[-1]]:
            res+=ans(path+[i])
    return res
print(ans([0]))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
matrix=[[0]*N for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    matrix[a-1][b-1]=1
    matrix[b-1][a-1]=1
import itertools 
count=0
for i in itertools.permutations(range(N)):
    if i[0]==0:
        result=1
        for j in range(N-1):
            result*=matrix[i[j]][i[j+1]]
        if result==1:
            count+=1
    else:
        break
print(count)

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:
def dfs(v,been):
    if len(been) == n:
        ans.append(1)
        #print(been)
        return
    for i in graph[v]:
        if i in been:
            pass
        else:
            been.add(i)
            dfs(i,been)
            been.remove(i)
    return

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)

ans = []

dfs(1,set([1]))
print(sum(ans))

Submission status: Accepted

Solution code:
import sys
import copy

input = sys.stdin.readline

A = None


def dfs(i, v):
    global A
    v.add(i)

    ans = 0
    for j in A[i]:
        if j not in v:
            v2 = copy.deepcopy(v)
            ans += dfs(j, v2)

    if len(A) - 1 == len(v):
        ans += 1
    return ans


def main():
    global A
    N, M = [int(x) for x in input().split()]
    A = [[] for j in range(N + 1)]
    for _ in range(M):
        a, b = [int(x) for x in input().split()]
        A[a].append(b)
        A[b].append(a)

    print(dfs(1, set()))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(M)]
G = [[] for _ in range(N)]
for a, b in AB:
    G[a-1].append(b-1)
    G[b-1].append(a-1)
visited = [False] * N
visited[0] = True
ans = 0
def dfs(x):
    global ans
    if all(visited):
        ans += 1
        return
    for y in G[x]:
        if not visited[y]:
            visited[y] = True
            dfs(y)
            visited[y] = False
dfs(0)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
vertices, edges = map(int, input().split(" "))
connect = defaultdict(set)
for e in range(edges):
    a, b = map(lambda n:n - 1, map(int, input().split(" ")))
    connect[a] |= {b}
    connect[b] |= {a}
queue = [[0, set()]]
answer = 0
while queue:
    next_queue = []
    # print(queue)
    for q in queue:
        here, visited = q
        new_visited = set()
        new_visited |= visited | {here}
        if len(new_visited) == vertices:
            # print(new_visited, here, queue)
            answer += 1
        for conn in connect[here]:
            if conn not in new_visited:
                next_queue.append([conn, new_visited])
    queue = next_queue
print(answer)

Submission status: Accepted

Solution code:
import itertools

n,m=map(int,input().split())
L=[list(map(int,input().split())) for i in range(m)]
LL=[]
cnt=0
for i in range(len(L)):
    LL.append([L[i][1],L[i][0]])
Node=L+LL
Ans=[int(i)+1 for i in range(n)]
for v in itertools.permutations(Ans):
    v=list(v)
    if v[0]!=1:
        break
    tmp=0
    for i in range(n-1):
        if [v[i],v[i+1]] in Node:
            tmp+=1
    if tmp==n-1:
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
import copy
N, M = map(int, input().split())
edges = [[] for _ in range(N+1)]


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

ans = 0

def dfs(u, visited):
  global ans
  stack = [u]

  while stack:
    u = stack.pop()
    visited.add(u)

    e = list(filter(lambda x: x not in visited, edges[u]))
    l = len(e)
    if l == 0:
      if len(visited) == N:
        ans += 1
    elif l == 1:
      stack.append(e[0])
    else:
      for next in e:
        dfs(next, copy.copy(visited))


dfs(1, set())
print(ans)