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 copy

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

V = []

def dfs(node, seen):

    if seen[node]==True:
        return 0

    seen[node] = True
    if not(False in seen):
        return 1
    ret = 0
    for next_node in V[node]:
        ret += dfs(next_node, copy.deepcopy(seen))
    return ret

for _ in range(N):
    V.append(set())

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

print(dfs(0, copy.deepcopy([False]*N)))

Submission status: Accepted

Solution code:
#python3
from itertools import permutations

def main():
    n, m = map(int, input().split())
    edge = set()
    for _ in range(m):
        a, b = map(int, input().split())
        edge.add((a-1, b-1))
        edge.add((b-1, a-1))
    
    node = []
    for i in range(n):
        node.append(i)
    cnt = 0
    for p in permutations(node):
        if p[0] == 0:
            f = True
            for j in range(n-1): 
                if (p[j], p[j+1]) not in edge:
                    f = False
            if f:
                cnt += 1 
    print(cnt)
main()

Submission status: Accepted

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

    edge = set()
    for _ in range(m):
        a, b = map(lambda x: int(x)-1, input().split())
        edge.add((a, b))  
        edge.add((b, a))

    #全ノード間に辺が張っていると仮定する
    #このとき全てのノードを廻る順番は順列の数だけある
    #ここから条件を絞って数えるべきものを数えていく 

    #ノードを廻る順を構成する 
    node_num = []
    for i in range(n):
        node_num.append(i)
    
    cnt = 0
    for p in permutations(node_num):
        #数える経路は始点が0である
        if p[0] == 0:
            #この順列pの通りに辿れるように辺が張っているならこの経路は数えるべき経路である
            flag = True
            for i in range(n-1):
                #この順列のあるノード間に辺が存在しないならこの経路は不可能
                if (p[i], p[i+1]) not in edge:
                    flag = False
            if flag:
                cnt += 1 
    print(cnt) 
main()

Submission status: Accepted

Solution code:
from itertools import permutations

def int0(s):
    return int(s) - 1

def main():
    N, M = map(int, input().split())
    edges = [tuple(map(int0, input().split())) for _ in range(M)]

    to = [[False]*N for _ in range(N)]
    for a, b in edges:
        to[a][b] = True
        to[b][a] = True
    
    ans = 0
    for p in permutations(range(1, N)):
        if to[0][p[0]] and all(to[p[i]][p[i+1]] for i in range(N-2)):
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, m = [int(x) for x in input().split()] # n: 頂点, m: 辺
line = [ tuple( int(x)-1 for x in input().split() ) for _ in range(m) ]

matrix = [ [False]*n for _ in range(n) ] # n x n 行列
for a, b in line:
    matrix[a][b] = True
    matrix[b][a] = True

visited = [False]*n

def dfs(point, depth):
    if visited[point]:
        return 0

    if depth == n - 1:
        return 1

    visited[point] = True
    total = 0
    for i, np in enumerate(matrix[point]):
        if np:
            total += dfs(i, depth + 1)

    visited[point] = False
    return total

print(dfs(0, 0))

Submission status: Accepted

Solution code:
import itertools
n,m = map(int,input().split())
vert = [[0] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    vert[a].append(b)
    vert[b].append(a)
parents = [0]
now = 1
ans = 0
for i in list(itertools.permutations(range(1,n+1))):
    if i[0] == 1:
        for j in range(1,n):
            if i[j] not in vert[i[j-1]]:
                break
        else:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
def dfs(now,parents):
    global ans
    global n
    for i in vert[now]:
        if i not in parents:
            dfs(i,parents+[now])
    if len(parents) == n:
        ans += 1
n,m = map(int,input().split())
vert = [[0] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    vert[a].append(b)
    vert[b].append(a)
parents = [0]
now = 1
ans = 0
dfs(1,parents)
print(ans)
# while parents:
#     if len(vert[now]) > 1:
#         next_place = vert[now].pop()
#         if vert[next_place][0] == 0:
#             now = next_place
#             vert[now][0] = 1

Submission status: Accepted

Solution code:
from collections import deque
N,M = map(int,input().split())
T = [[] for i in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    T[a].append(b)
    T[b].append(a)
Q = deque([(1,[1])])
ans = 0
while Q:
    p,V = Q.pop()
    if len(V)==N:
        ans += 1
        continue
    for c in T[p]:
        if not(c in V):
            Q.append((c,V+[c]))
print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m = map(int,input().split())
e = [[False]*n for _ in range(n)]
for _ in range(m):
  a,b = map(int,input().split())
  e[a-1][b-1] = True
  e[b-1][a-1] = True

ans = 0
l = [i for i in range(1,n)]
for p in itertools.permutations(l):
  p = [0] + list(p)
  reach = 1
  for i in range(n-1):
    if not e[p[i]][p[i+1]]:
      reach = 0
      break
  ans += reach

print(ans)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs,copy
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""





co = 0



n,k = m()

dp = [[0 for i in range(n)] for j in range(n)]

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

def dfs(now,li,dp):
    global co

    for i in range(n):
        if dp[now][i] == 1 and li[i] == 0:
            po = copy.deepcopy(li)
            po[i] = 1
            dfs(i,po,dp)
    if sum(li) == n:
        co += 1
nnn = [0 for i in range(n)]
nnn[0] = 1
dfs(0,nnn,dp)
print(co)

Submission status: Accepted

Solution code:
from itertools import permutations

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

g = permutations(range(1, N + 1))

count = 0
for order in g:
    flag = True
    for i in range(N-1):
        if set((order[i], order[i + 1])) not in graph or order[0] != 1:
            flag = False
            break
    if flag:
        count += 1

print(count)

Submission status: Accepted

Solution code:
from itertools import  permutations

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

A = []
for i in range(2,N+1):
    A.append(i)

def f(m,n):  #(m,n)の組が結ばれているか
    if m > n:
        l = m
        m = n
        n = l
    for i in range(M):
        if d[i][0] == m and d[i][1] == n:
            return 1
    else:
        return 0

ans = 0
for i in permutations(A,N-1):
    for j in range(N-1):
        if j == 0:
            if f(1,i[0]) == 1:
                continue
            else:
                break
        else:
            if f(i[j-1],i[j]) == 1:
                continue
            else:
                break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from itertools import permutations


def main():
    N, M = list(map(int, input().split()))
    AB = [list(map(int, input().split())) for _ in range(M)]
    AB = sorted(AB, key=lambda x: (x[0], x[1]))

    result = 0
    P = permutations(range(2, N + 1), N - 1)

    for i in P:
        li = [1] + list(i)
        if sum(list(sorted(edge)) in AB for edge in zip(li, li[1:])) == N - 1:
            result += 1
    print(result)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin

ans = 0


def dfs(cnt, current, path):
    if cnt == N:
        global ans
        ans += 1
        # print(cnt, current, path)
        return
    for i in range(N):
        # print(path)
        if s[current-1][i] == 1 and i+1 not in path:
            # print(i)
            # global path
            path.append(i+1)
            dfs(cnt+1, i+1, path)
            for i in range(cnt, len(path)):
                path.pop()


N, M = [int(x) for x in stdin.readline().rstrip().split()]
s = [[0 for i in range(N)] for j in range(N)]
cnt = 1
for i in range(M):
    a, b = [int(x) for x in stdin.readline().rstrip().split()]
    s[a-1][b-1] = 1
    s[b-1][a-1] = 1
path = [1]
dfs(cnt, 1, path)
# print(s)
print(ans)

Submission status: Accepted

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

visited=[False]*(N+1)

visited[1]=True
def dfs(start):
    global N
    global visited
    all_visited=True
    sum=0

    for p in range(1,N+1):
        if not visited[p]:
            all_visited=False

    if all_visited:
        return 1
    else:
        for next in range(1,N+1):#N小より全探索
            if not G[start][next]:
                continue
            if visited[next]:
                continue
            visited[next]=True
            sum+=dfs(next)
            visited[next]=False   #backtrack

        return sum

print(dfs(1))

Submission status: Accepted

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

glaph={}

for i in range(1,n+1):
    glaph[i]=[]

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

#print(glaph)

import itertools
junretsu=[]
for i in range(2,n+1):
    junretsu.append(i)
cnt=0

junretsu=list(itertools.permutations(junretsu))

#print(junretsu)
for item in junretsu:
    i=0
    flag=0
    if item[0] not in glaph[1]:
        flag=1

    while i<n-2:
        #print(item,i)
        if item[i+1] not in glaph[item[i]]:
            flag=1
        i+=1
    if flag==0:
        cnt+=1
        #print(item)
print(cnt)

Submission status: Accepted

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

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

ans=0
stack=[]

for i in ab:
    if i[0]==1:
        stack.append([i[1],1+2**(i[1]-1)])

while len(stack)>0:
    p=stack.pop()

    if p[1]==2**N-1:
        ans+=1
    else:
        for i in ab:
            if i[0]==p[0] and not(2**(i[1]-1)&p[1]):
                stack.append([i[1],p[1]+2**(i[1]-1)])
            if i[1]==p[0] and not(2**(i[0]-1)&p[1]):
                stack.append([i[0],p[1]+2**(i[0]-1)])

print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    from itertools import permutations
    # readline = sys.stdin.buffer.readline
    readlines = sys.stdin.readlines
    N, M = map(int, input().split())
    edge = [[0] * N for _ in range(N)]
    for s in readlines():
        a, b = map(int, s.split())
        a -= 1; b -= 1
        edge[a][b] = 1
        edge[b][a] = 1

    cnt = 0
    for path in permutations(range(1, N)):
        path = [0] + list(path)
        for i in range(N - 1):
            v = path[i]
            nv = path[i + 1]
            if edge[v][nv] == 0:
                break
        else:
            cnt += 1
    print(cnt)


if __name__ == "__main__":
    main()

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 heapq import heapify, heappop, heappush

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)
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)]))
permu = []
for p in per:
    p = [0] + list(p)
    permu.append(p)
ans = 0
for p in permu:
    cnt = 0
    for i in range(N-1):
        a, b = p[i], p[i+1]
        if rinsetsu[a][b] == 1:
            cnt += 1
    if cnt == N - 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))
MIIZ = lambda: list(map(lambda x: x-1, MII()))

def dfs(g,e,now,ret):
    e[now] = True
    if all(e): ret += 1
    for next in g[now]:
        if e[next]: continue
        ret = dfs(g,e,next,ret)
    e[now] = False
    return ret

def main():
    n, m = MII()
    g = {i: [] for i in range(n)}
    for _ in range(m):
        x, y = MIIZ()
        g[x].append(y)
        g[y].append(x)
    ret = 0
    e = [False]*n
    e[0] = True
    ret = dfs(g,e,0,ret)
    print(ret)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
n, m = map(int, input().split())
edge = [[0 for i in range(n)] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    edge[a-1][b-1] = 1
    edge[b-1][a-1] = 1

def ok(l):
    return all([edge[l[i]-1][l[i+1]-1] for i in range(n-1)])
ans = 0
for x in itertools.permutations(range(2,n+1)):
    l = [1] + list(x)
    if ok(l):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
N,M=map(int,input().split())
edges=set()
for _ in range(M):
  a,b=map(int,input().split())
  edges.add((a,b))
  edges.add((b,a))
  
  
answer=0


for p in itertools.permutations(range(1,N+1)):
  if p[0] !=1:
    continue
  bl=True
  for i in range(N-1):
    if (p[i],p[i+1]) not in edges:
      bl =False
      
  if bl:
    answer +=1
    
    
print(answer)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
a=[0 for k in range(M)]
b=[0 for k in range(M)]
for k in range(M):
    a[k],b[k]=map(int, input().split())
def dfs(route,new):
    route=route+new
    if len(route)==N+1:
        return 1
    count=0
    for k in range(M):
        if a[k]==route[-1] and b[k] not in route:
            count+= dfs(route,[b[k]])
    for k in range(M):
        if b[k]==route[-1] and a[k] not in route:
            count+= dfs(route,[a[k]])
    return count

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

Submission status: Accepted

Solution code:
import sys
import os
import math

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

MOD = 10 ** 9 + 7


def dfs(graph, edges, now, ret):
    edges[now] = True
    if all(edges): ret += 1

    for next in graph[now]:
        if edges[next]: continue
        ret = dfs(graph, edges, next, ret)
    edges[now] = False
    return ret


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    g = {n: [] for n in range(N)}
    for m in range(M):
        a, b = il()
        g[a - 1].append(b - 1)
        g[b - 1].append(a - 1)

    ret = 0
    edges = [False] * N
    edges[0] = True
    ret = dfs(g, edges, 0, ret)
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
n,m = map(int,input().split())
ways = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    ways[a-1].append(b-1)
    ways[b-1].append(a-1)
checklist = [0]*n
position = 0 #first position
cnt = 0
if n == 2:
    if 1 in ways[0]:
        print(1)
    else:
        print(0)
    exit()
for p in itertools.permutations(range(1,n)):
    if p[0] in ways[0]:
        flag = True
        for i in range(n-2):
            if p[i+1] not in ways[p[i]]:
                flag = False
                break
        if flag:
            cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import sys
import os
import math

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

MOD = 10 ** 9 + 7


def dfs(graph, edgs, now, ret):
    edgs[now] = True
    if all(edgs): ret += 1

    for next in graph[now]:
        if edgs[next]: continue
        ret = dfs(graph, edgs, next, ret)
    edgs[now] = False
    return ret


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    g = {n: [] for n in range(N)}
    for m in range(M):
        a, b = il()
        g[a - 1].append(b - 1)
        g[b - 1].append(a - 1)

    ret = 0
    edgs = [False] * N
    edgs[0] = True
    ret = dfs(g, edgs, 0, ret)
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

n_list = []
for i in range(1, n+1):
    n_list.append(i)
n_array = sorted(list(itertools.permutations(n_list)))

count = 0

for i in range(math.factorial(n-1)):
    for j in range(n-1):
        if not (set(n_array[i][j:j + 2]) in e):
            break
    else:
        count += 1
print(count)

Submission status: Accepted

Solution code:
import itertools
N,M=map(int,input().split())
edges=set()
for _ in range(M):
  a,b =map(int,input().split())
  edges.add((a,b))
  edges.add((b,a))
  
  
answer=0


for p in itertools.permutations(range(1,N+1)):
  if p[0] !=1:
    continue
  bl=True
  for i in range(N-1):
    if(p[i],p[i+1]) not in edges:
      bl =False
      break
  if bl:
    answer +=1
    
    
print(answer)

Submission status: Accepted

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

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

def solve(route):
    if len(route) == n:
        return 1
    count = 0
    for i in path[route[-1]]:
        if i in route: continue
        count += solve(route + [i])
    return count

print(solve([0]))

Submission status: Accepted

Solution code:
# 全探索で間に合う
from collections import deque

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

count=0
stack=deque([str(0)])
while stack:
    tmp=stack.pop()
    if len(tmp)==N:
        count+=1
    else:
        label=[-1]*N
        for i in range(len(tmp)):
            label[int(tmp[i])]=1
        for i in friend[int(tmp[-1])]:
            if label[i]==-1:
                stack.append(tmp+str(i))
print(count)

Submission status: Accepted

Solution code:
import itertools as it

N, M = map(int, input().split())
ab = tuple(set(map(int, input().split())) for _ in range(M))

P = it.permutations(range(1, N + 1), N)

res = 0
for p in P:
    if p[0] == 1:
        for i in range(N - 1):
            if not(set({p[i], p[i + 1]}) in ab):
                break
        else:
            res += 1

print(res)

Submission status: Accepted

Solution code:
import itertools

N,M = map(int,input().split())
lis = [x+1 for x in range(N-1)]
path = [list(map(int, input().split())) for _ in range(M)]
pb = [[False] * N for i in range(N)]
for i in range(M):
  p = path[i][0]-1
  q = path[i][1]-1
  pb[p][q] = True
  pb[q][p] = True

c = 0
for ps in itertools.permutations(lis):
  if pb[0][ps[0]]:
    for i in range(N-2):
      if not pb[ps[i]][ps[i+1]]:
        break
    else:
      c += 1

print(c)

Submission status: Accepted

Solution code:
import sys

n, m, *ab = map(int, sys.stdin.read().split())
graph = [[] for _ in range(n)]
for a, b in zip(*[iter(ab)] * 2):
    a -= 1; b -= 1
    graph[a].append(b)
    graph[b].append(a)

def main():
    stack = [(0, 0)]
    paths = 0
    while stack:
        i, visited = stack.pop()
        visited |= 1 << i
        if visited == (1 << n) - 1:
            paths += 1
            continue
        for j in graph[i]:
            if visited >> j & 1: continue
            stack.append((j, visited))
    print(paths)

if __name__ ==  '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

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

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

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations as pmt

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

import numpy as np
Mat = [[0 for i in range(N)] for j in range(N)]
for i in range(M):
    a,b = [int(x) for x in input().split()]
    Mat[a-1][b-1] = 1

Mat = np.array(Mat)
Mat += Mat.T

ans = 0
for od in pmt([i for i in range(1,N)]):
    order = [0] + list(od)
    ok = True
    for i in range(N-1):
        ok &= (Mat[order[i]][order[i+1]] > 0)
    ans += int(ok)    

print(ans)

Submission status: Accepted

Solution code:
Vertex, Line = map(int, input().split())
LineList = [[int(_) for _ in input().split()] for i in range(Line)]
graph = [[] for _ in range(Vertex)]

for a, b in LineList:
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

total_one_stroke_path = 0
def search_path(now_node = 0, check_passed = 0):
    check_passed += 1 << now_node
    global total_one_stroke_path

    for next_node in graph[now_node]:
        if check_passed & (1 << next_node) == 0:
            search_path(next_node, check_passed)

    if check_passed == (1 << Vertex) - 1:
        total_one_stroke_path += 1

    return

search_path()
print(total_one_stroke_path)
exit()

Submission status: Accepted

Solution code:
from collections import deque
from copy import deepcopy
n, m = map(int, input().split())
tree = [[] for i in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)
result = 0
visit = [-1 for _ in range(n+1)]
visit[1] = 1
q = deque([[1, deepcopy(visit)]])
while q:
    p, v = q.pop()
    if v[p] == n:
        result += 1
    for j in tree[p]:
        if v[j]<0:
            next_v = deepcopy(v)
            next_v[j] = next_v[p]+1
            q.appendleft([j, next_v])
print(result)

Submission status: Accepted

Solution code:
# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def dfs(now,N,sides,visited):

    all_visited = True

    if False in visited:
        all_visited = False

    if all_visited:
        return 1

    res = 0

    for i in range(N):
        if not sides[now][i]:
            continue
        if visited[i]:
            continue
        visited[i] = True
        res += dfs(i,N,sides,visited)
        visited[i] = False

    return res


def main():
    N,M = map(int,input().split())

    sides = [[False for j in range(N)] for i in range(N)]

    for i in range(M):
        A,B = map(int,input().split())
        sides[A-1][B-1] = sides[B-1][A-1] = True

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

    res = dfs(0,N,sides,visited)

    print(res)



main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
input_lines = [[int(j)-1 for j in input().split()] for i in range(m)]

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

for line in input_lines:
    map_list[line[0]].append(line[1])
    map_list[line[1]].append(line[0])

stack = [[0],]
visited = [0 for i in range(n)]

def dfs(stack,visited):
    if sum(visited)==n:
        return 1
    ans = 0
    
    search = stack.pop(-1)
    for s in search:
        if visited[s]==1:
            continue
        visited[s]=1
        stack.append(map_list[s])
        ans += dfs(stack,visited)
        visited[s]=0
    return ans

ans = dfs(stack,visited)
print(ans)

Submission status: Accepted

Solution code:
import itertools

n,m = map(int,input().split())#頂点の数、辺の数

graph = [[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
    graph[a][b] = True
    graph[b][a] = True

ans = 0
for i in itertools.permutations(range(n)):
    if i[0] != 0:
        continue
    visited = [0]*n
    visited[0] += 1
    for j in range(n):
        if j == n-1:
            if 0 not in visited:
                ans += 1
            break
        if graph[i[j]][i[j+1]] == True:
            visited[i[j+1]] += 1
        
            
print(ans)

Submission status: Accepted

Solution code:
def dfs(i,d,c):
    global n,f,ans
    c2=c.copy()
    c2[d]=1
    #print("#",i,d,c2)
    if i==n:
        ans+=1
        return
    for j in range(n):
        #print(d,j,c2)
        if (f[d][j]==1 or f[j][d]==1) and c2[j]==0:
            #print(d,j)
            dfs(i+1,j,c2)

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

Submission status: Accepted

Solution code:
import itertools

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

lst = [[0 for _ in range(n)] for _ in range(n)]

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

l = list(range(n))

cnt = 0
for v in itertools.permutations(l):
	flg = True
	if v[0] == 0:
		for i in range(n-1):
			x, y = v[i], v[i + 1]
			if lst[x][y] == 0: # pathがなければ
				flg = False
		if flg:
			cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
#
# Written by NoKnowledgeGG @YlePhan
# ('ω')
#
#import math
#mod = 10**9+7
#import itertools
#import fractions
#import numpy as np
#mod = 10**4 + 7
"""def kiri(n,m):
  r_ = n / m
  if (r_ - (n // m)) > 0:
    return (n//m) + 1
  else:
    return (n//m)"""

""" n! mod m 階乗
mod = 1e9 + 7
N = 10000000
fac = [0] * N
def ini():
  fac[0] = 1 % mod
  for i in range(1,N):
    fac[i] = fac[i-1] * i % mod"""

"""mod = 1e9+7
N = 10000000
pw = [0] * N
def ini(c):
  pw[0] = 1 % mod
  for i in range(1,N):
    pw[i] = pw[i-1] * c % mod"""

"""
def YEILD():
  yield 'one'
  yield 'two'
  yield 'three'
generator = YEILD()
print(next(generator))
print(next(generator))
print(next(generator))
"""
"""def gcd_(a,b):
  if b == 0:#結局はc,0の最大公約数はcなのに
    return a
  return gcd_(a,a % b) # a = p * b + q"""
"""def extgcd(a,b,x,y):
  d = a
  if b!=0:
    d = extgcd(b,a%b,y,x)
    y -= (a//b) * x
    print(x,y)
  else:
    x = 1
    y = 0
  return d"""


def readInts():
  return list(map(int,input().split()))
mod = 10**9 + 7
#def main():
n,m = readInts()
a = [0] * m
b = [0] * m

graph = [[False for i in range(n)] for j in range(n)]

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

cnt = 0
now = [0] * n

def dfs(pos,nya):
  global cnt
  if pos == n:
    if now[0] == 0:
      for i in range(n-1):
        if graph[now[i]][now[i+1]] == False:
          break
        if i == n-2:
          cnt += 1
    return
  for i in range(n):
    if nya & (1 << i):
      now[pos] = i
      dfs(pos+1,nya^(1<<i))
dfs(0,(1<<n)-1)
print(cnt)
  
#if __name__ == '__main__':
#  main()

Submission status: Accepted

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

from itertools import permutations
ans=0
for p in permutations([x for x in range(1,n)]):
    ok=True
    t=[0]+list(p)
    for i in range(1,n):
        if G[t[i-1]][t[i]]==0:ok=False
    if ok:ans+=1
print(ans)

Submission status: Accepted

Solution code:
import itertools
N, M = map(int,input().split())
AB = [0] * M
for i in range(M):
  AB[i] = list(map(int, input().split()))
  
lis = [x for x in range(1, N + 1)] # 1からnまでのリスト
 
permutations_lis = itertools.permutations(lis)# 全ての場合のリストを生成
# 以下出力

ans = 0
for one_case in permutations_lis: 
  #print(one_case) #(1,2,3)など
  if one_case[0] == 1:
    m = 0
  else:
    m = N
  for i in range(N - 1):
    #print(one_case[i])
    path = [one_case[i], one_case[i + 1]]
    path2 = [one_case[i + 1], one_case[i]]
    if path in AB:
      m += 1
    elif path2 in AB:
      m += 1
  if m == N - 1:
    ans += 1
    
print(ans)