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:
'''
頂点1から全頂点通る一筆書きが何個あるか
頂点数(N)は最大で8なので道順を全列挙して調べてもいける
'''
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)

    res = []
    visited = [0]*N

    def dfs(node):
        visited[node]=1
        if sum(visited)==N:
            res.append(1)
            return
        for n_node in g[node]:
                if not visited[n_node]:
                    dfs(n_node)
                    visited[n_node] = 0
    dfs(0)
    print(len(res))


    # My
    # n,m = map(int, input().split())
    # edge = [list(map(int, input().split())) for _ in range(m)]
    # res = []
    # visited = [0]*n

    # def dfs(node):
    #     visited[node-1]=1
    #     if sum(visited)==n:
    #         res.append(1)
    #         return
    #     for x,y in edge:
    #         if x == node:
    #             if not visited[y-1]:
    #                 dfs(y)
    #                 visited[y-1] = 0
    #         if y == node:
    #             if not visited[x-1]:
    #                 dfs(x)
    #                 visited[x-1] = 0

    # for a,b in edge:
    #     if a==1:
    #         dfs(a)
    #         print(len(res))
    #         exit()
    #     if b==1:
    #         dfs(b)
    #         print(len(res))
    #         exit()

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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())
    edge = [list(map(int, input().split())) for _ in range(m)]
    res = []
    visited = [0]*n

    def dfs(node):
        visited[node-1]=1
        if sum(visited)==n:
            res.append(1)
            return
        for x,y in edge:
            if x == node:
                if not visited[y-1]:
                    dfs(y)
                    visited[y-1] = 0
            if y == node:
                if not visited[x-1]:
                    dfs(x)
                    visited[x-1] = 0

    for a,b in edge:
        if a==1:
            dfs(a)
            print(len(res))
            exit()

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from itertools import permutations
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    e = set(zip(a, b))
    print(sum(
        1 for p in permutations(range(2, N + 1))
        if all((n1, n2) in e or (n2, n1) in e for n1, n2 in zip((1,) + p, p))
    ))


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:
from collections import deque
from itertools import permutations

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

graph = [[False]*(N+1) for _ in range(N+1)]
for i in l:
    graph[i[0]][i[1]] = True
    graph[i[1]][i[0]] = True

cnt = 0

for i in permutations(range(1,N+1)):
    if i[0] != 1:
        continue
    isJoin = True
    for j in range(1,N):
        if not graph[i[j-1]][i[j]]:
            isJoin = False
            break
    if isJoin:
        cnt += 1
print(cnt)

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 dfs(path, n, cnt):
    if(len(path) == N):
        return cnt+1
    for j in graph[n]:
        if(j in path):
            continue
        cnt = dfs(path+[j], j, cnt)
    return cnt
print(dfs([1], 1, 0))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,M = inputMap()
	ck = {}
	for i in range(M):
		a,b = inputMap()
		if a in ck:
			ck[a].append(b)
		else:
			ck[a] = [b]
		if b in ck:
			ck[b].append(a)
		else:
			ck[b] = [a]

	tmp = [i for i in range(2,N+1)]
	ans = 0
	for v in itertools.permutations(tmp, N-1):
		ato = list(v)
		saki = [1]
		saki += ato
		flg = True
		for i,val in enumerate(saki):
			if i == 0:
				continue
			if val in ck[saki[i-1]]:
				pass
			else:
				flg = False
				break
		if flg == True:
			ans += 1

	print(ans)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# special thanks :
#  https://nagiss.hateblo.jp/entry/2019/07/01/185421
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

Submission status: Accepted

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

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


def solve(n, visit):
    if all(visit):
        return 1
    c = 0
    for i in range(N):
        b = ab[n][i]
        if b and not visit[i]:
            visit[i] = True
            c += solve(i, visit)
            visit[i] = False
    return c


print(solve(0, [True]+[False]*(N-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 dfs(root):
    now = root[-1]
    ret = []
    for i in graph[now]:
        if i in root:
            pass
        else:
            ret.append(dfs(root + [i]))
    if not ret:
        if len(root) == n:
            return 1
        return 0

    return sum(ret)


print(dfs([1]))

Submission status: Accepted

Solution code:
from itertools import permutations

N, M = list(map(int, input().split()))
G = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
for _ in range(M):
    ai, bi = list(map(int, input().split()))
    G[ai][bi] = 1
    G[bi][ai] = 1

count = 0
for idx, perm in enumerate(permutations(range(1, N+1))):
    if perm[0] != 1:
        continue

    flag = True
    for i in range(len(perm) - 1):
        if G[perm[i]][perm[i + 1]] == 0:
            flag = False
            break
    if flag:
        count += 1

print(count)

Submission status: Accepted

Solution code:
import itertools

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

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

ans = 0
for p in itertools.permutations(list(range(n)), n):
    if p[0] != 0:
        continue

    isok = True
    for i in range(len(p)-1):
        if not am[p[i]][p[i+1]]:
            isok = False
            break

    if isok:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

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

    g[a][b] = 1
    g[b][a] = 1
# print(g)
check = set()

path = list(permutations(range(N)))

for t in path:
    if t[0] != 0:
        continue
    flag = True
    for i in range(N - 1):
        if g[t[i]][t[i + 1]] != 1:
            flag = False
            break
    if flag:
        check.add(t)

# print(check)
print(len(check))

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    def dfs(u=0,cnt=1):
        if cnt==n:return 1
        res=0
        for cu in to[u]:
            if vis[cu]:continue
            vis[cu]=True
            res+=dfs(cu,cnt+1)
            vis[cu]=False
        return res

    n,m=MI()
    to=defaultdict(list)
    for _ in range(m):
        a,b=MI1()
        to[a].append(b)
        to[b].append(a)
    vis=[False]*n
    vis[0]=True
    print(dfs())

main()

Submission status: Accepted

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

data = [i for i in range(2, n+1)]

ans = 0
for a in itertools.permutations(data, n-1):
    a = [1] + list(a)
    flag = True
    for i in range(1, len(a)):
        if not ([a[i-1], a[i]] in ab or [a[i], a[i-1]] in ab):
            flag = False
            break
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
path = [[] for i in range(N)] 
for i in range(M):
    nums = list(map(int, input().split()))
    path[nums[0]-1].append(nums[1]-1)
    path[nums[1]-1].append(nums[0]-1)

memo = [] 
def search(idx, memo_str):
    if len(memo_str) == N and memo_str not in memo:
        memo.append(memo_str)
        return
    
    if str(idx) in memo_str:
        return
    
    tmp_memo = memo_str + str(idx)
    
    for num in path[idx]:
        search(num, tmp_memo)

search(0, '')

print(len(memo))

Submission status: Accepted

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


def dfs(v):
    visited[v] = True
    if all(visited):
        visited[v] = False
        return 1
    ret = 0
    for u in range(N):
        if v == u or visited[u] or G[v][u] == 0:
            continue
        ret += dfs(u)
    visited[v] = False
    return ret


print(dfs(0))

Submission status: Accepted

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

res = 0
L = list(itertools.permutations(range(N)))

for l in L:
    if l[0] != 0:
        break
    ok = True
    for i in range(N-1):
        from_ = l[i]
        to_ = l[i+1]
        if not G[from_][to_]:
            ok = False
    if ok:
        res += 1
print(res)

Submission status: Accepted

Solution code:
#深さ優先探索
N, M = map(int,input().split())
graph = [[] for j in range(N)]
for i in range(M):
  a, b = map(int,input().split())
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)
judge = [False]*N
judge[0] = True

def dfs(v,judge):#vは今いる場所
  if all(judge):
    return 1
  res = 0
  for nv in graph[v]:#vと隣り合っている場所
    if judge[nv]:#すでに探索済み
      continue #if文の初めに戻る
    judge[nv] = True
    res += dfs(nv,judge)
    judge[nv] = False
  return res
print(dfs(0,judge))

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 lcm(a,b):
    return a*b//gcd(a,b)
def main():
    N,M=MI()
    edge = [[0]*N for _ in range(N)]
    for _ in range(M):
        a,b = MI_()
        edge[a][b] = 1
        edge[b][a] = 1
    
    ans = 0
    for it in permutations([i for i in range(N)]):
        l  =  [i for i in it]
        ok = True
        if l[0]!=0:
            continue
        for i in range(N-1):
            if not edge[l[i]][l[i+1]]:
                ok = False
        ans += ok
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import permutations

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

ans = 0
for path in permutations(range(n)):
        if path[0]: continue
        can = 1
        for i in range(n-1):
                if links[path[i]][path[i+1]]==0: can = 0
        ans += can
print(ans)

Submission status: Accepted

Solution code:
def main():
    N, M = (int(i) for i in input().split())
    G = [[] for i in range(N)]
    for i in range(M):
        x, y = (int(i)-1 for i in input().split())
        G[x].append(y)
        G[y].append(x)
    ans = 0
    from itertools import permutations
    for p in permutations(range(1, N)):
        j = 0
        # print(p)
        for i in range(N-1):
            if p[i] in G[j]:
                j = p[i]
            else:
                break
        else:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

for i in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    g[a].add(b)
    g[b].add(a)
#print(g)

import itertools
ans = 0
for per in itertools.permutations(range(n)):
    if per[0] != 0:
        continue
    for i in range(n-1):
        if per[i+1]  not in g[per[i]]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

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


def isOK(seq):
    s = 1
    for t in seq:
        if t in edge[s]:
            s = t
        else:
            return False
    return True


ans = 0
for seq in itertools.permutations(range(2, N + 1)):
    if isOK(seq):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import permutations

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

    count = 0
    for s in permutations(range(N), N):
        Visited = [False for _ in range(N)]
        for i, n in enumerate(s):
            if i == 0:
                if n != 0: break
                else: Visited[0] = True
            else:
                if n in Edge[s[i-1]]: Visited[n] = True
                else: break
        else: count += 1
    print(count)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import itertools

n,m=map(int,input().split())
g=[list(map(int,input().split())) for _ in range(m)]
v=list(itertools.permutations(range(1,n+1)))

ans=0

for x in v:
    tf=True
    if x[0]!=1:
        tf=False
    else:
        for i in range(n-1):
            if not ([x[i],x[i+1]] in g or [x[i+1],x[i]] in g):
                tf=False
                break
    if tf:
        ans+=1
print(ans)

Submission status: Accepted

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

n,w = map(int,readline().split()) #n:頂点数　w:辺の数
g = [[] for i in range(n)] #g[i]:点iに隣接している点のリスト
for i in range(w):
    x,y = map(int,readline().split())
    x,y = x-1,y-1
    g[x].append(y)
    g[y].append(x)

def dfs():
    ans = 0
    queue = deque([[0]]) #queueの中身をvisitedにするlen(queue)==nの時ans+=1
    while queue:
        lst = queue.popleft()
        if len(lst)==n:
            ans += 1
            continue
        for i in g[lst[-1]]:
            if not i in lst:
                queue.append(lst+[i])
    
    return ans

print(dfs())

Submission status: Accepted

Solution code:
from itertools import permutations
n, m = map(int, input().split())
ab = [[] for i in range(n)]
for i in range(m):
    a, b = map(lambda x: int(x) - 1, input().split())
    ab[a].append(b)
    ab[b].append(a)
cnt = 0
if n == 2:
    if 1 in ab[0]:
        print(1)
    else:
        print(0)
    exit()
for p in permutations(range(1, n)):
    if p[0] in ab[0]:
        flag = True
        for i in range(n - 2):
            if p[i + 1] not in ab[p[i]]:
                flag = False
                break
        if flag:
            cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import itertools
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N, M, *ab = map(int, read().split())
    E = [[] for _ in range(N+1)]

    for a, b in zip(*[iter(ab)] * 2):
        E[a].append(b)
        E[b].append(a)
    
    ans = 0
    fact_p = itertools.permutations(range(2,N+1))
    for p in fact_p:
        par = 1
        flag = True
        for i in p:
            if par not in E[i]:
                flag = False
                break
            par = i
            
        if flag:
            ans += 1
    
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools

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

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

cnt=0

for p in itertools.permutations(range(n),n):
    if p[0]>0:
        continue

    for i in range(n-1):
        a=p[i]
        b=p[i+1]

        if not (b in c[a]):
            break
    else:
        cnt+=1

print(cnt)

Submission status: Accepted

Solution code:
def dfs(i):
  global count
  global seen
  global G

  end = True
  for n in range(N):
    if seen[n] == 0 and n != i:
      end = False

  if (end):
    count += 1
    return

  seen[i] = 1
  for g in G:
    if g[0] == i:
      if seen[g[1]] == 1:
        continue
      dfs(g[1])
  
    if g[1] == i:
      if seen[g[0]] == 1:
        continue
      dfs(g[0])

  seen[i] = 0

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

G = []

for i in li:
  G.append([i[0]-1, i[1]-1])

count = 0
seen = [0] * N
dfs(0)

print(count)

Submission status: Accepted

Solution code:
#始点1から全ノードを通る経路の総数
#解答：
#基本DFSだが、ゴールしたらゴールの訪問予定フラグを消す
#ゴールしたら分岐点からまたDFS


N,M=map(int,input().split())
#dc={}
lc=[[] for _ in range(N)]#インデは-1、要素はそのまま
for i in range(M):
    a,b=map(int,input().split())
    #if not a in
    lc[a-1].append(b)
    lc[b-1].append(a)
#st=[1]
#print(lc)
st=[[1,0]]
#df={1:1}
df={}
lp=[0]
ans=0
while st:
    #tmp=st.pop()
    tmptp=st.pop()
    #print("tmptp",tmptp)
    tmp=tmptp[0]
    ptmp=tmptp[1]
    p=lp.pop()
    while p!=ptmp:
        del df[p]
        p=lp.pop()
    lp.append(p)
    lp.append(tmp)
    df[tmp]=1
    if len(df)==N:
        ans+=1
        #del df[tmp]
        #print("lp",lp)
        #print("df",df)
    for c in lc[tmp-1]:
        if not c in df:
            #st.append(c)
            st.append([c,tmp])
            #df[c]=1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
link = [[] for _ in range(n)]
for i in range(m):
    tmp = list(map(int,input().split()))
    link[tmp[0]-1].append(tmp[1]-1)
    link[tmp[1]-1].append(tmp[0]-1)
lis = list(range(1,n))
ans=0
from itertools import *
for perm in list(permutations(lis)):
    last=0
    ok=1
    for i in range(len(perm)):
        if perm[i] not in link[last]:
            ok=0
        last=perm[i]
    ans+=ok
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
link = [[] for _ in range(n)]
for i in range(m):
    tmp = list(map(int,input().split()))
    link[tmp[0]-1].append(tmp[1]-1)
    link[tmp[1]-1].append(tmp[0]-1)

lis=[]
for i in range(1,n):
    lis.append(i)
ans=0
from itertools import *
for perm in list(permutations(lis)):
    last=0
    ok=True
    for i in range(len(perm)):
        if perm[i] not in link[last]:
            ok=False
            break
        last=perm[i]
    if ok:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
link = [[] for _ in range(n)]
for i in range(m):
    tmp = list(map(int,input().split()))
    link[tmp[0]-1].append(tmp[1]-1)
    link[tmp[1]-1].append(tmp[0]-1)

from collections import deque
Q = deque()
Q.append([0,[0]]) # now, history

import copy
ans=0
while Q:
    now,org_hist = Q.popleft()

    for nxt in link[now]:
        if nxt in org_hist:
            continue
        hist = copy.copy(org_hist)

        hist.append(nxt)
        if len(hist) >= n:
            ans+=1
        else:
            Q.append([nxt,hist])
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

ans = 0
pattern = list(itertools.permutations(list(range(2, n+1))))
for i in pattern:
    li = list(i)
    li.insert(0, 1)
    pattern_check = True
    for j in range(0, n-1):
        path_check = False
        for k in range(m):
            if len({li[j], li[j+1]} & set(ab[k])) == 2:
                path_check = True
                break
        if not path_check:
            pattern_check = False
            break
    if pattern_check:
        #print(li)
        ans += 1
print(ans)

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:
  a,b=a-1,b-1
  path[a].append(b)
  path[b].append(a)
ans=0
for ptn in itertools.permutations(range(1,n)):
  s=0
  for nex in ptn:
    if s not in path[nex]: break
    s=nex
  else:
    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)]

visited = [False] * N
visited[0] = True
d = {}
for a, b in A:
    d.setdefault(b-1, []).append(a-1)
    d.setdefault(a-1, []).append(b-1)

l = sorted(d.items())

def dfs(v, seen):
    if False not in seen: return 1
    
    c = 0
    for i in d[v]:
        if (seen[i]): continue
        seen[i] = True
        c += dfs(i, seen)
        seen[i] = False
    return c
    
print(dfs(0, visited))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
g = [[] for _ in range(N + 1)]
for _ in range(M):
    x, y = map(int, input().split())
    g[x].append(y)
    g[y].append(x)

ans = 0
todo = [(1, list(range(2, N + 1)))]
while todo:
    p, r = todo.pop()
    for np in g[p]:
        if np in r:
            if len(r) == 1:
                ans += 1
            else:
                nr = r[:]
                nr.remove(np)
                todo.append((np, nr))
print(ans)

Submission status: Accepted

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

N, M = [int(x) for x in input().split()]
G = [[] for _ in range(N + 1)]

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

import itertools
l = [x for x in range(2, N + 1)]
per = list(itertools.permutations(l))

cnt = 0

for i in range(len(per)):
    route = [1] + list(per[i])
    flag = 1
    for k in range(len(route) - 1):
        if route[k + 1] not in G[route[k]]:
            flag = 0
            break
    cnt += flag

print(cnt)

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