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 itertools
n,m = map(int,input().split())
mat = [[0]*n for i in range(n)]
for i in range(m):
    u,v = map(int,input().split())
    mat[u-1][v-1] = 1
    mat[v-1][u-1] = 1

cnt = 0
arr = [i for i in range(1,n)]
for road in itertools.permutations(arr):
    start = 0
    for r in road:
        if mat[start][r] ==0:
            break
        else:
            start = r
    else:cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
import copy

def func(graph, array, n):
  ans = 0
  for v in graph[n]:
    if not array[v]:
      cp_array = copy.deepcopy(array)
      cp_array[v] = True
      
      if [True]*len(array) == cp_array:
        ans += 1
      else:
        ans += func(graph, cp_array, v)

  return ans

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

for i in range(m):
  a,b = map(int, input().split())
  a -= 1
  b -= 1
  graph[a].append(b)
  graph[b].append(a)
  
array = [False] * n
array[0] = True
print(func(graph, array, 0))

Submission status: Accepted

Solution code:
import itertools
n,m = map(int,input().split())
M = [[0] * n for i in range(n)]

for i in range(m):
  a,b = map(int,input().split())
  M[a-1][b-1] = 1
couse = list(itertools.permutations(range(n)))
result = 0
#M = np.array(M)
for c in couse:
  con = 0
  if(c[0] == 0):
    for i in range(len(c)-1):
      if(M[c[i]][c[i+1]] == 1 or M[c[i+1]][c[i]] == 1):
        con += 1
        #print(c[i],c[i+1])
    if (len(c)-1 == con):
      result += 1
print(result)

Submission status: Accepted

Solution code:
import itertools

n,m = [int(x) for x in input().split()]
li = []
for _ in range(m):
    li.append({int(x) for x in input().split()})

a = itertools.permutations(range(2,n+1))
count = 0
for i in a:
    x = [1] + list(i)
    for i in range(n-1):
        if not {x[i],x[i+1]} in li:
            break
    else:
        count += 1
print(count)

Submission status: Accepted

Solution code:
from itertools import permutations

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

ed = list(range(1, N+1))
temp = permutations(ed)

ans = 0

for i in temp:
    flg = True
    if i[0] != 1:
        continue
    else:
        for j in range(1, N):
            a, b = i[j-1], i[j]
            if a > b:
                ab = a
                a = b
                b = ab
            if [a, b] in edge:
                continue
            else:
                flg = False
                break
    if flg:
        ans += 1

print(ans)

Submission status: Accepted

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

import itertools
p=itertools.permutations(range(1,n))
p=list(p)

def check(x,y):
    if y in a[x]:
        return True
    else:
        return False
ans=0
for route in p:
    flag=True
    for i in range(n-1):
        if i==0:
            if check(0,route[i])==True:
                pass
            else:
                flag=False
        else:
            if check(route[i-1],route[i])==True:
                pass
            else:
                flag=False
    if flag==True:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import itertools as it
n,m = map(int, input().split())
keiro = []
for i in range(m):
    a,b = map(int, input().split())
    keiro.append([a,b])
per = it.permutations(range(2,n+1),n-1)
ans = 0
for pe in per:
    Flag = True
    pe = list(pe)
    pe.insert(0,1)
    for i in range(len(pe)-1):
        if [pe[i],pe[i+1]] not in keiro and [pe[i+1],pe[i]] not in keiro:
            Flag = False
            break
    if Flag == True:
        ans +=1
print(ans)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
L = [LIST() for i in range(M)]

graph = defaultdict(list)
# E = defaultdict(list)
rinsetsu = [[0] * N for i in range(N)]

for a, b in L:
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    rinsetsu[a-1][b-1] = 1
    rinsetsu[b-1][a-1] = 1

per = list(permutations([n for n in range(1, N)]))
# print(permu)
permu = []
for p_list in per:
    p_list = [0] + list(p_list)
    permu.append(p_list)

ans = 0

for p in permu:
    for i in range(N-1):
        # print(p[i], p[i+1])
        if rinsetsu[p[i]][p[i+1]] != 1:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from collections import Counter
from itertools import product, permutations,combinations
import sys
input = sys.stdin.readline
#文字列のときはうまく行かないのでコメントアウトすること
sys.setrecursionlimit(2147483647)

def main():
  n, m = map(int, input().split())
  #隣接リストを作る
  path = [[False for i in range(n)] for j in range(n)]
  for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    path[a][b] = True
    path[b][a] = True
  ans = 0
  for i in permutations(range(n), n):
    if i[0] == 0:
      for j in range(n):
        if j == n-1:
          ans += 1
          break
        if not path[i[j]][i[j+1]]:
          break
  print(ans)

if __name__ == '__main__':
  main()

Submission status: Accepted

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

flag = [False]*N
flag[0] = True
res = 0

def f(n):
    global res
    for fl in flag:
        if not fl:
            break
    else:
        res += 1
        return
    for i in x[n]:
        if flag[i]:
            continue
        flag[i] = True
        f(i)
        flag[i] = False
    return

f(0)
print(res)

Submission status: Accepted

Solution code:
import itertools

n, m = map(int, input().split())
l = [list(map(int, input().split())) for i in range(m)]
r = [[] for i in range(n + 1)]
ans = 0
for i in range(m):
    r[l[i][0]].append(l[i][1])
    r[l[i][1]].append(l[i][0])
p = "2345678"[:n-1]
p = list(itertools.permutations(p))
for i in range(len(p)):
    check = True
    t = "1" + "".join(p[i])
    for j in range(len(t)-1):
        if not int(t[j + 1]) in r[int(t[j])]:
            check = False
    if check:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m=map(int,input().split())
link=[[]for j in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  link[a-1].append(b-1)
  link[b-1].append(a-1)
s=list(range(1,n))
res=0
for perm in list(itertools.permutations(s)):
  last=0
  ok=True
  for i in range(n-1):
    if perm[i] not in link[last]:
      ok=False
      break
    else:
      last=perm[i]
  if ok==True:
    res=res+1
print(res)

Submission status: Accepted

Solution code:
import itertools
n, m = map(int, input().split())
l = [list(map(int, input().split())) for i in range(m)]
r = [[] for i in range(n + 1)]
ans = 0
for i in range(m):
    r[l[i][0]].append(l[i][1])
    r[l[i][1]].append(l[i][0])
p = []
for i in range(n):
    p.append(i + 1)
p = list(itertools.permutations(p))
for i in range(len(p)):
    check = True
    t = list(p[i])
    if t[0] != 1:
        check = False
    for j in range(len(t)-1):
        if not t[j + 1] in r[t[j]]:
            check = False
    if check:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
N,M=map(int,input().split())
path=[tuple(map(int,input().split())) for _ in range(M)]
cnt=0
for li in itertools.permutations([k for k in range(2,N+1)],N-1):
    flag=True
    li=list(li)
    li.insert(0,1)
    for i in range(N-1):
        if (li[i],li[i+1]) not in path and (li[i+1],li[i]) not in path:
            flag=False
    if flag:
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
def dfs(visted, graph, cur, count):
    n = len(visited)

    allNodeVisited = True
    for i in range(1, n):
        if visited[i] is False:
            allNodeVisited = False
            break

    if allNodeVisited:
        count += 1
        return count

    for i in range(1, n):
        if cur != i and visited[i] is False and graph[cur][i] == 1:
            visited[i] = True
            count = dfs(visited, graph, i, count)
            visited[i] = False

    return count


n, m = map(int, input().split())
visited = [False] * (n + 1)

graph = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for i in range(m):
    frm, to = map(int, input().split())
    graph[frm][to] = graph[to][frm] = 1


count = 0
visited[1] = True
count = dfs(visited, graph, 1, count)

print(count)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
G = [[] for _ in range(N)]
visited = [False]*N
visited_all = [True]*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 dfs(node):
  visited[node] = True
  if visited == visited_all:
    ans[0] += 1
  else:
    for i in range(len(G[node])):
      next_node = G[node][i]
      if visited[next_node] == True:
        continue
      dfs(next_node)
      visited[next_node] = False

dfs(0)
print(ans[0])

Submission status: Accepted

Solution code:
import itertools
N,M = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(M)]
r = list(range(1,N+1))
ok = 1
cnt = 0
for v in itertools.permutations(r):
    if(v[0] == 1):
        ok = 1
        for i in range(N-1):
            if(list(v[i:i+2]) not in ab and list(reversed(v[i:i+2])) not in ab):
                ok = 0
                break
        if(ok == 1):
            cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import copy

def solve():
    N,M = map(int, input().split())
    graph = {i:[] for i in range(1,N+1)}
    for _ in range(M):
        a,b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
        
    stack = [1]
    ret = 0
    searched = [False]*(N+1)
    searched[1] = True
    
    def dfs(dom, searched, prev=-1):
        searched[dom] = True
        ret = 0
        
        if all(searched[1:]): 
            # print(dom,searched,ret)
            return ret+1
        
        for cod in graph[dom]:
            # print(dom,cod)
            if not searched[cod]:
                ret += dfs(cod, copy.copy(searched),dom)
        
        return ret
            
    ret = dfs(1, searched)
    print(ret)
    
solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の呼び出し制限
N, M = map(int, input().split())
A = [[0]* N for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    A[a-1][b-1] = 1
    A[b-1][a-1] = 1
visited=[1]+[0]*(N-1)
def DFS(now, visited):
    ans = 0
    if not 0 in visited:
        return 1
    for i in range(N):
        if A[now][i] == 0:
            continue
        if visited[i] == 1:
            continue
        visited[i] = 1
        ans += DFS(i, visited)
        visited[i] = 0
    return ans
print(DFS(0, visited))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc054/tasks/abc054_c
# なんか水パフォだけど全探索するだけ

import sys
read = sys.stdin.readline


from itertools import permutations


def read_ints():
    return list(map(int, read().split()))


def main():
    N, M = read_ints()

    from collections import defaultdict
    graph = defaultdict(lambda: [])
    for m in range(M):
        a, b = read_ints()
        graph[a].append(b)
        graph[b].append(a)

    def is_ok(p):  # 順序pにしたがってグラフがつながっているか
        for now, nx in zip(p, p[1:]):
            if nx not in graph[now]:
                return 0
        return 1

    ans = 0
    for perm in permutations(range(2, N + 1)):
        perm = [1] + list(perm)
        ans += is_ok(perm)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc054/tasks/abc054_c
# なんか水パフォだけど全探索するだけ

import sys
read = sys.stdin.readline


from itertools import permutations


def read_ints():
    return list(map(int, read().split()))


N, M = read_ints()
from collections import defaultdict
graph = defaultdict(lambda: [])
for m in range(M):
    a, b = read_ints()
    graph[a].append(b)
    graph[b].append(a)


def is_ok(p):  # 順序pにしたがってグラフがつながっているか
    for now, nx in zip(p, p[1:]):
        if nx not in graph[now]:
            return 0
    return 1


def main():
    ans = 0
    for perm in permutations(range(2, N + 1)):
        perm = [1] + list(perm)
        ans += is_ok(perm)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc054/tasks/abc054_c
# なんか水パフォだけど全探索するだけ

import sys
read = sys.stdin.readline


from itertools import permutations


def read_ints():
    return list(map(int, read().split()))


N, M = read_ints()
from collections import defaultdict
graph = defaultdict(lambda: [])
for m in range(M):
    a, b = read_ints()
    graph[a].append(b)
    graph[b].append(a)


def is_ok(p):  # 順序pにしたがってグラフがつながっているか
    for now, nx in zip(p, p[1:]):
        if nx not in graph[now]:
            return 0
    return 1


ans = 0
for perm in permutations(range(2, N + 1)):
    perm = [1] + list(perm)
    ans += is_ok(perm)

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

N,M = list(map(int, input().split()))
S = set([])
for _ in range(M):
    A,B = list(map(int, input().split()))
    S.add((A,B))
    S.add((B,A))
count = 0
node = [i for i in range(1,N+1)]
lis = list(permutations(node))

for v in lis:
    flag = 0
    if v[0] != 1:
        continue
    for i in range(N-1):
        if (v[i],v[i+1]) in S:
            continue
        else:
            flag += 1
    if flag == 0:
            count += 1

print(count)

Submission status: Accepted

Solution code:
from itertools import permutations
def solve(N,C):
    node = [i for i in range(1,N+1)]
    lis = list(permutations(node))
    ans = 0
    for v in lis:
        flag = 0
        if v[0] != 1:
            continue
        for i in range(N-1):
            if (v[i],v[i+1]) in C:
                continue
            else:
                flag += 1
        if flag == 0:
            ans += 1
    return ans


def main():
    N,M = map(int,input().split(" "))
    C = set([])
    for _ in range(M):
        a,b = map(int,input().split(" "))
        C.add((a,b))
        C.add((b,a))
    print(solve(N,C))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

ans = 0
st = [[0, [False] * N]]
while len(st) > 0:
    _st = st.pop()
    v = _st[0]
    visited = copy(_st[1])
    if visited[v]:
        continue
    visited[v] = True
    adj_all_visit = True
    for adj in G[v]:
        if visited[adj]:
            continue
        st.append([adj, visited])
        adj_all_visit = False
    if adj_all_visit and all(visited):
        ans += 1
print(ans)

Submission status: Accepted

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

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

visited = [False] * (n+1)

stack = [(1, 1, visited)]

count = 0
while stack:
    now, dist, visited_ = stack.pop()
    visited = visited_.copy()
    visited[now] = True
    if dist == n:
        count += 1
    for neighbor in graph[now]:
        if not visited[neighbor]:
            stack.append((neighbor, dist + 1, visited))

print(count)

Submission status: Accepted

Solution code:
import numpy as np

N, M = map(int, input().split())
adj = np.zeros((N+1, N+1))
for m in range(M):
  a, b = map(int, input().split())
  adj[a, b] = 1
  adj[b, a] = 1

from itertools import permutations

nodes = [n for n in range(2, N+1)]
ans = 0

for case in permutations(nodes):
  success = True
  for i, nd in enumerate(case):
    if i == 0:
      f = 1
    else:
      f = case[i-1]

    t = case[i]

    if adj[f, t] != 1:
      success = False
      break

  if success:
    ans += 1

print(ans)

Submission status: Accepted

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

def go(curr, used, count):
  if count == 1:
    return 1
  tmp = used + [curr]
  return sum(go(node, tmp, count - 1) for node in g[curr] if node not in used)

print(go(0, [], n))

Submission status: Accepted

Solution code:
def f(i):
    global ans
    if i == n - 1:
        if G[0][s[0]] == 0:
            return
        t = sorted(s)
        for j in range(n - 2):
            if t[j] == t[j + 1]:
                return
        for j in range(n - 2):
            if G[s[j]][s[j + 1]] == 0:
                return
        ans += 1
        return
    for j in range(n - 1, 0, -1):
        f(i + 1)
        s[i] = j

n, m = map(int, input().split())
G = [[0 for _ in range(n)] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    G[a - 1][b - 1] = 1
    G[b - 1][a - 1] = 1
s = [1] * (n - 1)
ans = 0
f(0)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

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

D = defaultdict(set)
for a, b in AB:
    D[a].add(b)
    D[b].add(a)

ans = 0
queue = deque([(1, {1})])
while queue:
    q = queue.popleft()
    for x in D[q[0]] - q[1]:
        s = q[1] | {x}
        if len(s) == N:
            ans += 1
        else:
            queue.append((x, s))
print(ans)

Submission status: Accepted

Solution code:
import sys

import numpy as np
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
INF = float("INF")
mod = 10 ** 9 + 7
"""dd = [(-1, 0), (0, 1), (1, 0), (0, -1)];
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)];
ddn9 = ddn + [(0, 0)]
for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""

def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]  # WideIntPoint
def ws(): return sys.stdin.readline().split()
def si(): return int(sys.stdin.readline())  # SingleInt
def ss(): return input()
def hi(n): return [si() for _ in range(n)]
def hs(n): return [ss() for _ in range(n)]  # HeightString
def s_list(): return list(input())
def mi(n): return [wi() for _ in range(n)]  # MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]  # NumberGrid
def grid(n): return [s_list() for _ in range(n)]


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

    G = defaultdict(list)
    for i in range(m):
        a, b = map(int,input().split())
        G[a].append(b)
        G[b].append(a)
    #print(G)

    # stackは次の探索候補?
    # visitedはもう探索済み
    stack = [(1, [1])]
    ans = 0
    # stack(次の探索候補)が空になるまで回す
    while stack:
        # xは今見ているノード
        x, visited = stack.pop()

        if len(visited) == n:
            ans += 1

        # vは今見ているノードの隣接ノード
        for v in G[x]:
            if v in visited:
                continue
            stack.append((v, visited + [v]))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
dict = {i+1:[] for i in range(N)}
for _ in range(M):
    a, b = map(int, input().split())
    dict[a].append(b)
    dict[b].append(a)
    
def DFS(visited, sight, cnt):
    if(len(visited) == N):
        return cnt+1
    for num in dict[sight]:
        if num in visited:
            continue
        cnt = DFS(visited+[num], num, cnt)
    return cnt

print(DFS([1], 1, 0))

Submission status: Accepted

Solution code:
import sys
from math import *
from collections import deque, Counter, defaultdict
from fractions import gcd
from itertools import permutations
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return


def main():
    n,m = map(int, input().split())
    graph = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(m):
        a,b = map(int, input().split())
        graph[a-1][b-1] = 1
        graph[b-1][a-1] = 1
    # n!通りの並べ方があり，各並べ方について成立するかどうかを調べる．
    # 成立しないと判明した時点で探索をやめる
   
    a = [i+1 for i in range(n)]
    p = permutations(a)

    def check(x):
        # x: (1,3,4,6,7,2)
        for i in range(n-1):
            if not graph[x[i]-1][x[i+1]-1]:
                return False
        return True
    cnt = 0
    for x in p:
        if x[0] != 1:
            continue
        if check(x):
            cnt += 1       
    print(cnt)
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque, defaultdict

N, M = map(int, input().split())
nodes = defaultdict(set)
for _ in range(M):
    u, v = map(int, input().split())
    nodes[u].add(v)
    nodes[v].add(u)

visited = [False]*N

def dfs(x, visited, st):
    res = 0
    v = visited.copy()
    v[x-1] = True
    if st == N:
        return 1

    for node in nodes[x]:
        if not v[node-1]:
            res += dfs(node, v, st+1)
    return res

print(dfs(1, visited, 1))

Submission status: Accepted

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

def my_permutations(nums, t, path):
    if len(nums) == 0:
        path.append(t)
        return
    for i in range(len(nums)):
        my_permutations(nums[:i] + nums[i + 1:], t + [nums[i]], path)

def dfs(graph, permu, n):
    visited = [False] * (n + 1)
    next_nodes = set([1])
    for p in permu:
        if visited[p]:
            return False
        if p not in next_nodes:
            return False
        visited[p] = True
        next_nodes = set(graph[p])
    return True

path = []
my_permutations([i for i in range(1, n + 1)], [], path)
ans = 0
for permu in path:
    if permu[0] != 1:
        continue
    if dfs(graph, permu, n):
        ans += 1
print(ans)

Submission status: Accepted

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


N,M=[int(i) for i in input().rstrip().split()]
ab_list=[[int(j) for j in input().split()] for i in range(M)]
#-----

vertex_dic={}  # dic{int:set()}

for va,vb in ab_list:
    vertex_dic.setdefault(va,set())
    vertex_dic[va].add(vb)
    vertex_dic.setdefault(vb,set())
    vertex_dic[vb].add(va)


def check(vertex_dic :dict, passed :set, start :int):
    if len(vertex_dic) == len(passed):
        return 1
    
    next_set = vertex_dic[start] - passed # :set
    
    ans=0
    for i_next in next_set:
        next_passed = passed | {i_next}
        ans += check(vertex_dic, next_passed, i_next)
    
    return ans
    

result=check(vertex_dic, {1}, 1 )
print(result)

Submission status: Accepted

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


N,M=[int(i) for i in input().rstrip().split()]
ab_list=[[int(j) for j in input().split()] for i in range(M)]
#-----

vertex_dic={}  # dic{int:set()}

for va,vb in ab_list:
    vertex_dic.setdefault(va,set())
    vertex_dic[va].add(vb)
    vertex_dic.setdefault(vb,set())
    vertex_dic[vb].add(va)


def check(vertex_dic :dict, passed :set, start :int, cnt :int):
    if cnt >= len(vertex_dic) and len(vertex_dic) == len(passed):
        return 1
    
    next_set = vertex_dic[start] - passed # :set
    cnt += 1
    
    ans=0
    for i_next in next_set:
        next_passed = passed | {i_next}
        ans += check(vertex_dic, next_passed, i_next, cnt)
    
    return ans
    
result=check(vertex_dic, {1}, 1 ,1 )
print(result)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
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 operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n,m=mii()
gra=[[] for _ in range(n)]
for i in range(m):
    a,b=mii()
    a-=1
    b-=1
    gra[a].append(b)
    gra[b].append(a)

ans=0
for i in permutations(range(1,n)):
    i=[0]+list(i)
    cnt=1
    for j in range(n-1):
        
        if i[j+1] in gra[i[j]]:
            cnt+=1

    if cnt==n:
        ans+=1

print(ans)

Submission status: Accepted

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

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

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

count = 0
for route in all_routes:
  cur_path = path.copy()
  current = 1
  valid = True
  for next_pos in route:
    if ([current, next_pos] in cur_path):
      cur_path.remove([current, next_pos])
      current = next_pos
      continue
    elif ([next_pos, current] in cur_path):
      cur_path.remove([next_pos, current])
      current = next_pos
      continue
    else:
      valid = False
      break
  
  if(valid == True):
    count += 1

print(count)

Submission status: Accepted

Solution code:
#054_C
from itertools import permutations
n,m=map(int,input().split())
edges=[[False for _ in range(n)] for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    edges[a][b]=edges[b][a]=True

ans=0
for l in permutations(range(1,n),n-1):
    l=[0]+list(l)
    if all(edges[l[i]][l[i+1]] for i in range(n-1)):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys 
sys.setrecursionlimit(1000000)
N, M = map(int, input().split())
ab = [list(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
adlist = [[] for _ in range(N)]
for a, b in ab:
  adlist[a] += [b] 
  adlist[b] += [a] 


used = [0]*N 
global ans 
ans = 0
def dfs(v):
  global ans 
  used[v] = 1 
  if sum(used) == N:
    ans += 1 
    return 

  for u in adlist[v]:
    if used[u] == 0:
      used[u] = 1 
      dfs(u)
      used[u] = 0  

  return 

dfs(0)
print(ans)

Submission status: Accepted

Solution code:
res = 0
def main():
    import sys
    #input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations
    #from itertools import accumulate, product, permutations
    from math import floor, ceil

    #mod = 1000000007


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

    visited = [0]*N

    def dfs(node):
        global res
        visited[node]=1
        if all(visited):
            res += 1
            return
        for n_node in g[node]:
                if not visited[n_node]:
                    dfs(n_node)
                    visited[n_node] = 0
    dfs(0)
    print(res)

if __name__ == '__main__':
    main()