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: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = []
B = []

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

result = []
stack = []

def path(start, visited):

    if len(visited) == N:
        if visited not in result:
            result.append(visited[:])
        exit
    stack.append(start)
    while len(stack) > 0:
        nextpoint = stack.pop()
        if nextpoint in visited:
            continue
        visited.append(nextpoint)
        for i in range(2*M):
            if A[i] == start:
                path(B[i], visited)
        visited.pop()

path(1, [])
print(len(result))

Submission status: Time Limit Exceeded

Solution code:
def lensetlist(A):
    B = []
    for i in A:
        if i not in B:
            B.append(i)
    return len(B)

N, M = map(int, input().split())
A = []
B = []

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

result = []
stack = []
ans = 0

def path(start, visited, count):
    count += 1
    if count > 10000:
        exit
    if len(visited) == N:
        result.append(visited[:])
        exit
    stack.append(start)
    while len(stack) > 0:
        nextpoint = stack.pop()
        if nextpoint in visited:
            continue
        visited.append(nextpoint)
        for i in range(2*M):
            if A[i] == start:
                path(B[i], visited, count)
        visited.pop()

path(1, [], 0)
print(lensetlist(result))

Submission status: Time Limit Exceeded

Solution code:
def lensetlist(A):
    B = []
    for i in A:
        if i not in B:
            B.append(i)
    return len(B)

N, M = map(int, input().split())
A = []
B = []

for i in range(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

used = [0 for i in range(N)]
result = []
stack = []
ans = 0
def path(start, visited):
    if len(visited) == N:
        result.append(visited[:])
        exit
    stack.append(start)
    while len(stack) > 0:
        nextpoint = stack.pop()
        if nextpoint in visited:
            continue
        visited.append(nextpoint)
        for i in range(M):
            if A[i] == start:
                path(B[i], visited)
            if B[i] == start:
                path(A[i], visited)
        visited.pop()

path(1, [])
print(lensetlist(result))

Submission status: Time Limit Exceeded

Solution code:
import copy

N, M = [ int(x) for x in input().split()]

class Node:
    def __init__(self, id):
        self.id = id
        self.path = []
        self.passed = False
    def __str__(self):
        return "id: " + str(self.id) + " path: " + str(self.path) + " passed: " + str(self.passed)

nodes = []
for i in range(N):
    nodes.append(Node(i))

for i in range(M):
    from_id, to_id = [ int(x) - 1 for x in input().split()]
    nodes[from_id].path.append(to_id)
    nodes[to_id].path.append(from_id)

def if_all_passed(nodes_current):
    for node in nodes_current:
        if not node.passed:
            return False
    return True

def go_child(id_new, nodes_current):
    nodes_current[id_new].passed = True
    if if_all_passed(nodes_current):
        return 1

    count = 0
    for i in nodes[id_new].path:
        if not nodes_current[i].passed:
            count += go_child(i, copy.deepcopy(nodes_current))
    return count

count = go_child(0, nodes)
print(count)

Submission status: Time Limit Exceeded

Solution code:
N, M=map(int,input().split())
a=[0]*0
b=[0]*0
choice=[0]*(N-1)
chosen_a=[0]*(N-1)
chosen_b=[0]*(N-1)
c_patern=0
for i in range(M):
    a_tmp, b_tmp=map(int,input().split())
    a.append(a_tmp)
    b.append(b_tmp)
# for i in range(M):
#     c_point = [0] * N
#     if a[i]==1:
#         c_point[a[i]-1]+=1
#     for j in range(M):
#         if a[j]==b[i]:
# for i in range(N):
#     if c_point[i]!=1:
#         break
#     c_patern+=1
for i in range(pow(M,(N-1))):
    flg=0
    for j in range(N-1):
        choice[j]=i//pow(M,(N-1)-j-1)
        chosen_a[j]=a[choice[j]]
        chosen_b[j]=b[choice[j]]
        i=i%pow(M,(N-1)-j-1)
    if chosen_a[0]!=1:
        flg=1
    for k in range(N-1):
        if k>0:
            if chosen_a[k]!=chosen_b[k-1]:
                tmp=chosen_a[k]
                chosen_a[k]=chosen_b[k]
                chosen_b[k]=tmp
                if chosen_a[k]!=chosen_b[k-1]:
                    flg=1
    chosen_b_sorted=sorted(chosen_b)
    for l in range(N-1):
        if chosen_b_sorted[l]!=l+2:
            flg=1
    if flg==0:
        c_patern+=1
print(c_patern)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy


def solve(road, num, ans, n):
    pattern = 0
    test = deepcopy(road)
    if ans.count(str(num)) > 1:
        return 0
    if len(ans) is n:
        return 1
    if len(road[num - 1]) == int(0):
        return 0
    else:
        for i in range(len(road[num - 1])):
            tmp = test[num - 1][-1]
            if tmp is not 0:
                word = ans + str(tmp)
            test[num - 1].pop()
            pattern += solve(test, tmp, word, n)
    return pattern


N, M = [int(i) for i in input().split()]
town = []
for i in range(N):
    town.append(deepcopy([]))

for i in range(M):
    a, b = [int(i) for i in input().split()]
    town[a - 1].append(b)
    town[b - 1].append(a)
print(solve(town, 1, '1', N))

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy


def solve(road, num, ans, n):
    pattern = 0
    test = deepcopy(road)
    if ans.count(str(num)) > 1:
        return 0
    if len(ans) is n:
        return 1
    if len(road[num - 1]) == int(0):
        return 0
    else:
        for i in range(len(road[num - 1])):
            tmp = test[num - 1][0]
            if tmp is not 0:
                word = ans + str(tmp)
            test[num - 1].pop(0)
            pattern += solve(test, tmp, word, n)
    return pattern


N, M = [int(i) for i in input().split()]
town = []
for i in range(N):
    town.append(deepcopy([]))

for i in range(M):
    a, b = [int(i) for i in input().split()]
    town[a - 1].append(b)
    town[b - 1].append(a)
print(solve(town, 1, '1', N))

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy


def solve(road, num, ans, n):
    pattern = 0
    test = deepcopy(road)
    if len(ans) is int(n):
        for i in range(1, n + 1):
            if ans.count(str(i)) == 0:
                return 0
        return 1
    if len(road[num - 1]) == int(0):
        return 0
    else:
        for i in range(len(road[num - 1])):
            tmp = test[num - 1][0]
            if tmp is not 0:
                word = ans + str(tmp)
            test[num - 1].pop(0)
            pattern += solve(test, tmp, word, n)
    return pattern


N, M = [int(i) for i in input().split()]
town = []
for i in range(N):
    town.append(deepcopy([]))

for i in range(M):
    a, b = [int(i) for i in input().split()]
    town[a - 1].append(b)
    town[b - 1].append(a)
print(solve(town, 1, '1', N))

Submission status: Memory Limit Exceeded

Solution code:
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq
from bisect import bisect_left, insort_left

def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iip_ord():
    return [ord(i) - ord("a") for i in input()]


def main():
    r = solve()
    if r is not None:
        print(r)

def solve():
    N, M = iip(True)
    lines = {}
    for i in range(N):
        lines[i] = []

    for i in range(M):
        a, b = iip(True)
        lines[a-1].append(b-1)
        lines[b-1].append(a-1)

    c = [[0]]
    for a in range(1, N):
        n = []
        for i in c:
            for j in range(N):
                ct = [k for k in i]
                ct.append(j)
                n.append(ct)
        c = n

    kh = []
    for i in c:
        for j in range(N):
            if j not in i:
                break
        else:
            kh.append(i)

    ans = 0
    for root in kh:
        for i in range(N):
            if i == N-1:
                ans += 1
                break
            else:
                if not root[i+1] in lines[root[i]]:
                    #print(root)
                    #print(i)
                    #print(lines[i])
                    #print(root[i+1])
                    break

    #print(n)
    #print(kh)
    print(ans)
    #print(lines)
    #print(8**8* 64)

#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def OneStrokePath():
    from collections import deque
    import copy
    n, m = map(int, input().split())
    graph = [[] for _ in range(n)]
    ans = 0
    
    for _ in range(m):
        a, b = map(int, input().split())
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    q = deque()
    q.append([0, []])
        
    while q:
        x0, route0 = q.pop()
        if x0 in route0:
            continue
        route1 = copy.deepcopy(route0)
        route1.append(x0)
        if len(route1) == n:
            ans += 1
        for i in graph[x0]:
            if i in route1:
                continue
            q.append([i, route1])
    print(ans)  

if __name__ == '__main__':
    OneStrokePath()

Submission status: Accepted

Solution code:
import copy
N,M = map(int,input().split())
ls = [[] for i in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    ls[a].append(b)
    ls[b].append(a)
cnt = 0
q = []
q.append([1,1,[False for i in list(range(N+1))]])
while len(q) > 0:
    [x,n,path] = q.pop()
    path[x] = True
    # print(x,n,path)
    if path.count(True) == N:
        cnt += 1
        continue
    for j in ls[x]:
        if path[j] == False:
            q.append([j,n+1,path.copy()])
print(cnt)

Submission status: Accepted

Solution code:
import itertools
n,m=map(int,input().split())
num=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    num[a-1].append(b)
    num[b-1].append(a)
cnt=list(itertools.permutations(list(range(2,n+1))))
ans=0
for i in range(len(cnt)):
    num1=1
    num2=cnt[i]
    yn=0
    for j in range(n-1):
        if num2[j] not in num[num1-1]:
            yn=1
            break
        num1=num2[j]
    if yn==0:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import itertools as it
n,m=map(int,input().split())
e=[[0 for i in range(n)] for j in range(n)]
for i in range(m):
  a,b=map(lambda x:int(x)-1,input().split())
  e[a][b]=1
  e[b][a]=1
 
c=0
for t in it.permutations([j+1 for j in range(n-1)]):
  i=(0,)+t
  c+=1
  for j in range(n-1):
    if e[i[j]][i[j+1]]==0:
      c-=1
      break
print(c)

Submission status: Accepted

Solution code:
import sys,os
from collections import defaultdict, deque
from math import ceil, floor
import itertools
if sys.version_info[1] >= 5:
    from math import gcd
else:
    from fractions import gcd
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    MOD = 10**9+7

    N,M = LMIIS()
    edges = defaultdict(list)
    for i in range(M):
        a,b = LMIIS()
        edges[a].append(b)
        edges[b].append(a)
    ans = 0
    for l in itertools.permutations(range(2,N+1), N-1):
        prev = 1
        for v in l:
            if v in edges[prev]:
                prev = v
            else:
                break
        else:
            ans += 1
    print(ans)




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools as it
n,m=map(int,input().split())
e=[[0 for i in range(n)] for j in range(n)]
for i in range(m):
  a,b=map(lambda x:int(x)-1,input().split())
  e[a][b]=1
  e[b][a]=1

c=0
for t in it.permutations([j+1 for j in range(n-1)]):
  i=(0,)+t
  c+=1
  for j in range(n-1):
    if e[i[j]][i[j+1]]==0:
      c-=1
      break
print(c)

Submission status: Accepted

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


def dfs(node):
    if sum([1 for v in visited if v]) == N:
        return 1
    ret = 0
    for n in graph[node]:
        if visited[n]:
            continue
        visited[n] = True
        ret += dfs(n)
        visited[n] = False
    return ret


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

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

Submission status: Accepted

Solution code:
import itertools

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

# generate permunations from Node 2 to Node n
p = itertools.permutations(range(2, n + 1), n - 1)

cnt = 0
for v in p:
    if [1, v[0]] not in ab and [v[0], 1] not in ab:
        continue
    else:
        if all([n0, n1] in ab or [n1, n0] in ab for n0, n1 in zip(v, v[1:])):
            cnt += 1
print(cnt)

Submission status: Accepted

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

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

ans = 0
def dfs(i):
  global ans
  if all(reach[1:]):
    ans += 1
  for j in ma[i]:
    if reach[j] == 1:
      continue
    reach[j] = 1
    dfs(j)
    reach[j] = 0

reach=[0]*(n+1)
reach[1] = 1
dfs(1)
print(ans)

Submission status: Accepted

Solution code:
import itertools
N,M=map(int,input().split())
edges={tuple(sorted(map(int,input().split()))) for i in range(M)}
ans=0
for i in itertools.permutations(range(2,N+1),N-1):
    l=[1]+list(i)
    #ans+=sum(1 for edge in zip(l,l[1:]) if tuple(sorted(edge)) in edges)==N-1 以下はこの式を展開して書き直したもの
    sum=0
    for edge in zip(l,l[1:]): #これでlの1個目と2個目をとりだしたもの→2個目と3個目をとりだしたものみたいな感じになる
        if tuple(sorted(edge)) in edges:
            sum+=1
    if sum==N-1:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
# coding=utf-8
from math import floor, ceil, sqrt, factorial, log, gcd, log10
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement, chain
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heappushpop, heapify
from copy import copy, deepcopy
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 8)


def lcm(a, b): return a * b / gcd(a, b)

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


# https://qiita.com/greenteabiscuit/items/31c46ab3ceac07e749d2


n, m = LI()
graph = [[] for _ in range(n)]
v = [False] * n

for i in range(m):
    a, b = LI()
    graph[a - 1].append(b)
    graph[b - 1].append(a)


def dfs(now, depth):
    if v[now - 1]:
        return 0
    if depth == n-1:
        return 1
    ans = 0
    v[now - 1] = True
    for node in graph[now - 1]:
        ans += dfs(node, depth+1)

    v[now - 1] = False
    # ここが大事.上で探索の一つが終わるからリセットしている.

    return ans


print(dfs(1, 0))

Submission status: Accepted

Solution code:
#Nはノード数、Mはエッジ数
N, M = map(int, input().split())

path_matrix = []

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

#まず無向グラフを表す行列を作る
for m in range(M):
    line = map(int, input().split())
    paths = [x - 1 for x in line]
    path_matrix[paths[0]][paths[1]] = True
    path_matrix[paths[1]][paths[0]] = True

#最初はvisited、つまり訪問したことのあるノードはひとつもないので、Falseにする
visited = [False] * N


#再帰関数、ここが難しいかもしれない。
def dfs(now, depth):
    if visited[now]:
        return 0
    if depth == N - 1:
        return 1

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

    visited[now] = False

    return total_paths

print(dfs(0, 0))

Submission status: Accepted

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
import bisect
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    global L
    N,m = i_map()
    l = [[0]*N for i in range(N)]

    for i in range(m):
        a,b = i_map()
        a -= 1
        b -= 1
        l[a][b] = 1
        l[b][a] = 1

    L = 0
    v = [0] * N
    v[0] = 1

    def dfs(n):
        global L
        if 0 not in v:
            L += 1
            return

        for i in range(N):
            if l[n][i] == 1 and v[i] == 0:
                v[i] = 1
                dfs(i)
                v[i] = 0

    dfs(0)
    print(L)



if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
import bisect
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    N,m = i_map()
    l = [[0]*N for i in range(N)]

    for i in range(m):
        a,b = i_map()
        a -= 1
        b -= 1
        l[a][b] = 1
        l[b][a] = 1

    L = []

    def dfs(n,a):
        a = a + str(n)
        if len(a) == N:
            L.append(1)
            return

        for i in range(N):
            if l[n][i] == 1 and str(i) not in a:
                dfs(i,a)

    dfs(0,"")
    print(len(L))





if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
def dfs(place,number,checkedList,path):
  checkedList[place] = 1
  if sum(checked) == number:
    return 1
  pathNumber = 0
  for i in path[place]:
    if checkedList[i] == 1:
      continue
    pathNumber += dfs(i,number,checkedList,path)
    checkedList[i] = 0
  return pathNumber  

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

checked = [0] * 8
path = [ [] for _ in range(8)]
for i in range(m):
  a, b = map(int, input().split())
  path[a-1].append(b-1)
  path[b-1].append(a-1)
  #print(path)
  
print(dfs(0,n,checked,path))

Submission status: Accepted

Solution code:
def li():
    return [int(x) for x in input().split()]


import itertools as it
from collections import defaultdict

N, M = li()
G = defaultdict(list)

for _ in range(M):
    a, b = li()
    G[a].append(b)
    G[b].append(a)

L = range(2, N+1)

# 順列列挙
p = it.permutations(L)
cnt = 0
for t in p:
    b = 1
    ok = True
    for i in range(len(t)):
        a, b = b, t[i]
        if b not in G[a]:
            ok = False
            break
    if ok:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import itertools
N, M = map(int, input().split())
edges = [list(map(int, input().split())) for i in range(M)]#辺の集合
graph =[[] for i in range(N+1)]#隣接リスト
for edge in edges:
    graph[edge[0]].append(edge[1])
    graph[edge[1]].append(edge[0])

node = [i for i in range(1, N+1)]
per_list = list(itertools.permutations(node))#順列生成
count = 0
for l in per_list:#全ての順列について条件を満たすかどうか探索
    if l[0] != 1:#開始ノードが1じゃなかったらダメ
        continue
    flg = 0
    for i in range(len(l)-1):
        if not (l[i+1] in graph[l[i]]):#グラフの間に辺がなかったら
            flg = 1
            break
    if not flg:#フラグがたってなかったら
        count += 1

print(count)

Submission status: Accepted

Solution code:
import math as mt
import sys, string
from collections import Counter, defaultdict
input = sys.stdin.readline

# input functions
I = lambda : int(input())
M = lambda : map(int, input().split())
ARR = lambda: list(map(int, input().split()))

ans = 0
def dfs(u, graph, visited, curr_len, req_len):
    global ans
    if visited[u]:
        return
    visited[u] = 1
    if curr_len == req_len:
        ans += 1
        visited[u] = 0
        return
    for kid in graph[u]:
        dfs(kid, graph, visited, curr_len+1, req_len)
    visited[u] = 0

def main():
    global ans
    n, m = M()
    graph = defaultdict(list)
    for _ in range(m):
        u, v = M()
        graph[u].append(v)
        graph[v].append(u)
    visited = [0 for _ in range(n+1)]
    dfs(1, graph, visited, 0, n - 1)
    print(ans)

tc = 1
# tc = I()
for _ in range(tc):
    main()

Submission status: Accepted

Solution code:
from itertools import permutations
from math import factorial

n, m = map(int, input().split(' '))
edge = []
for i in range(m):
    ai, bi = map(int, input().split(' '))
    edge.append([ai, bi])

l = [i for i in range(1, n+1)]
ls = list(permutations(l))
ans = 0
for i in range(factorial(n-1)):
    y = 0
    for j in range(n-1):
        for k in edge:
            if (ls[i][j+1] in k) and (ls[i][j] in k):
                y += 1
    if y == n-1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
#グラフのパスを全探索する関数(再帰)
def dfs(now_node, depth):#deptt:今まで列挙した頂点数
    if seen[now_node]:#探索済みであった場合はreturn
        return 0
    if depth == N:#全ての頂点を通っていた場合、1を返す
        return 1
    seen[now_node] = True  #今から探索するノードを探索済みにする
    connect_nodes = graph[now_node]
    ans = 0
    for node in connect_nodes:#全ての遷移先をチェックする
        ans += dfs(node, depth+1)
    seen[now_node] = False  # 探索済みフラグを折る(ポイント)
    return ans

N, M = map(int, input().split())
edges = [list(map(int, input().split())) for i in range(M)]#辺の集合
graph =[[] for i in range(N+1)]#隣接リスト
for edge in edges:
    graph[edge[0]].append(edge[1])
    graph[edge[1]].append(edge[0])

#訪問済みかどうかを表すリストを用意
seen = [False for i in range(N+1)]
seen[0] = True

print(dfs(1, 1))

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(int, input().split())
    a, b = a - 1, b - 1
    G[a].append(b)
    G[b].append(a)

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

print(res)

Submission status: Accepted

Solution code:
from itertools import permutations


N, M = map(int, input().split())
S = []
for i in range(M):
    a, b = map(int, input().split())
    S.append([a, b])
    
vertex = (i+1 for i in range(N))
all_path = list(permutations(vertex))

ans = 0
for p in all_path:
    flag = True
    if p[0] == 1:
        for i in range(N-1):
            if [p[i], p[i+1]] not in S and [p[i+1], p[i]] not in S:
                flag = False
                break
        if flag:
            ans += 1
                
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

def getval():
    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)
    return n,m,g

def main(n,m,g):
    ans = 0
    for p in permutations(range(n-1)):
        flag = True
        idx = 0
        for i in p:
            if not i+1 in g[idx]:
                flag = False
                break
            idx = i+1
        if flag:
            ans += 1
    print(ans)

if __name__=="__main__":
    n,m,g = getval()
    main(n,m,g)

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(lambda x: int(x) - 1, input().split())
    G[a].append(b)
    G[b].append(a)
pattern = [i for i in range(N)]

ans = 0
for i in itertools.permutations(pattern):
    flag = True
    if i[0] != 0:
        continue
    for j in range(len(i) - 1):
        now = i[j]
        next = i[j+1]
        if not next in G[now]:
            flag = False
    if flag:
        ans += 1
print(ans)

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(lambda x: int(x) - 1, input().split())
    G[a].append(b)
    G[b].append(a)
pattern = [i for i in range(N)]

ans = 0
for i in itertools.permutations(pattern):
    flag = True
    if i[0] != 0:
        continue
    for j in range(len(i) - 1):
        if not i[j+1] in G[i[j]]:
            flag = False
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
from math import factorial

n, m = map(int, input().split(' '))
edge = []

for i in range(m):
    ai, bi = map(int, input().split(' '))
    edge.append([ai,bi])


x = [i for i in range(1,n+1)]
ls = list(permutations(x))
ans = 0
for l in range(factorial(n-1)):
    cnt = 0
    for i in range(n-1):
        for j in range(m):
            if (ls[l][i] in edge[j]) and (ls[l][i+1] in edge[j]):
                cnt += 1
    if cnt == n-1:
        ans += 1


print(ans)

Submission status: Accepted

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

def dfs(x, G, seen):
    seen[x] = True
    flag = True
    for i in seen:
        if i == False:
            flag = False
    if flag:
        return 1
    res = 0
    for i in G[x]:
        if seen[i]:
            continue
        res += dfs(i, G, seen)
        seen[i] = False
    return res

print(dfs(0, G, seen))

Submission status: Accepted

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


def dfs(n, path):
    count = 0
    path.append(n)
    if len(path) == N:
        count += 1
        return count

    for i in range(len(d[n])):
        if d[n][i] not in path:
            count += dfs(d[n][i], path)
            path.pop()

    return count


print(dfs(1, []))