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:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 100000000

n, m = LI()
G = [[0] * n for _ in range(n)]
for u, v in LIR(m):
    G[u - 1][v - 1] = 1
    G[v - 1][u - 1] = 1


cnt = 0
for path in permutations(range(1, n)):
    for i in range(1, len(path)):
        if not G[path[i - 1]][path[i]]:
            break
    else:
        if G[0][path[0]]:
            cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import sys
import itertools
import math
input = sys.stdin.readline
#sys.setrecursionlimit(1e9)
N,M = map(int,input().split())

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

graph=[[0]*8 for _ in range(8)]
def dfs(v,visited):
    if sum(visited) == N:
        return 1
    ret =0
    for i in range(N):
        if graph[v][i] == 1 and visited[i] == 0:
            visited[i]=1
            ret += dfs(i,visited)
            visited[i]=0
    return ret
def main():
    """code here"""

    for i in range(M):
        a=ab[i][0]
        b=ab[i][1]
        graph[a-1][b-1]=1
        graph[b-1][a-1]=1

    visited=[0]*N
    visited[0]=1
    print(dfs(0,visited))
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

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

def main():
    ramain = 2 ** n - 1
    cnt = 0
    stack = [(0, 0)]
    while stack:
        v, visited = stack.pop()
        visited ^= 2 ** v
        if not visited ^ ramain: 
            cnt += 1
            continue
        for u in graph[v]:
            if visited >> u & 1:
                continue
            stack.append((u, visited))

    return cnt

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
import sys

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

def main():

    cnt = 0
    stack = [(0, set())]
    while stack:
        v, visited = stack.pop()
        visited.add(v)
        if len(visited) == n: 
            cnt += 1
            continue
        for u in graph[v]:
            if u in visited:
                continue
            stack.append((u, visited.copy()))

    return cnt

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

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

def search(now, hist,cnt):
    for i in tree[now]:
        if i in hist:
            pass
        else:
            cnt = search(i, hist+[i],cnt)
    if len(hist)==n: #found
        return cnt + 1
    else: #not found
        return cnt
print(search(1,[1],0))

Submission status: Accepted

Solution code:
import itertools

n, m = map(int, list(input().split(' ')))
paths = {}
for i in range(m):
    a, b = map(int, list(input().split(' ')))
    if a in paths:
        paths[a].add(b)
    else:
        paths[a] = set([b])

ans = 0
for t in itertools.permutations(range(2, n+1), n - 1):
    arr = list(t)
    arr.insert(0, 1)
    for i in range(len(arr) - 1):
        a = arr[i]
        b = arr[i + 1]
        if a > b:
            tmp = a
            a = b
            b = tmp
        if not a in paths:
            break
        if not b in paths[a]:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import queue,sys,collections,math,random;sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,M = Is()
mat = [[] for _ in range(N) ]
for _ in range(M):
    a,b = Is()
    a,b = a-1, b-1
    mat[a].append(b)
    mat[b].append(a)

c = 0
def dfs(visited,now):
    if len(visited) == N:
        global c
        c += 1
    else:
        q = mat[now]
        for e in q:
            if not e in visited:
                dfs(visited+[e],e)
dfs([0],0)
print(c)

Submission status: Accepted

Solution code:
import sys
if sys.platform == 'ios':
	sys.stdin = open('input.txt')
	
n,m = map(int,input().split())

#各頂点のパスはタプルで書く
path = {i+1:[] for i in range(n)}

#各頂点が、どの頂点に繋がっているかのリストを入力しながら作る。
for i in range(m):
	a,b = map(int,input().split())
	path[a].append(b)
	path[b].append(a)

#1は根なので不要。2,3,...,nのリストを作る。
chk = [i for i in range(2,n+1)]
ans = 0

import itertools

#fは辿った頂点の数
#intertools.permurationsで頂点の総並び替えを出す
for way in itertools.permutations(chk):
	#print(way)
	now = 1
	f = 0
	
	for j in way:
		if j in path[now]:
			f = f + 1
			now = j
		else:
			break
		
	if f + 1 == n: # +1するのは根の分
		ans = ans + 1

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import permutations
inf = 10**10
n,m = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(m)]
lin = [[0 for i in range(n)]for j in range(n)]
for i in li:
    lin[i[0]-1][i[1]-1] = 1
    lin[i[1]-1][i[0]-1] = 1
def all_pairs_shortest_paths(W):
    n = len(W)
    res = [[0] * n for i in range(n)]
    for i in range(n):
        for j in range(i, n):
            if i == j:
                val = 0
            elif W[i][j]:
                val = W[i][j]
            else:
                val = inf
            res[i][j] = res[j][i] = val
    for k in range(n):
        for u in range(n):
            for v in range(n):
                res[u][v] = min(res[u][v], res[u][k] + res[k][v])
    return res
lis = all_pairs_shortest_paths(lin)
liv = [i+1 for i in range(n-1)]
liv = list(permutations(liv))
count = 0
for i in liv:
    keiro = list(i)
    flag = 0
    now = 0
    for j in keiro:
        if lis[now][j] == inf or lis[now][j] != 1:
            flag = 1
        now = j
    if flag == 0:
        count += 1
print(count)

Submission status: Accepted

Solution code:
import itertools

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

path = [[False] * n for i in range(n)]

# 頂点AからBにいく道はあるか？ vice versa 頂点BからAにいく道はあるか
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):
    if i[0] == 0:
        for j in range(n):
            if j == n - 1:
                ans += 1
                break

            if not path[i[j]][i[j + 1]]:
                break

print(ans)

Submission status: Accepted

Solution code:
import itertools as it

N, M = map(int, input().split())
graph = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    graph[a].append(b)
    graph[b].append(a)
ans = 0
for path in it.permutations(range(N)):
    if path[0] != 0:
        break
    is_connected = True
    for ith_edge in range(len(path) - 1):
        if path[ith_edge + 1] not in graph[path[ith_edge]]:
            is_connected = False
            break
    if is_connected:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools as it

N, M = map(int, input().split())
graph = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    graph[a].append(b)
    graph[b].append(a)
ans = 0
for path in it.permutations(range(N)):
    if path[0] != 0:
        continue
    is_connected = True
    for ith_edge in range(len(path) - 1):
        if path[ith_edge + 1] not in graph[path[ith_edge]]:
            is_connected = False
            break
    if is_connected:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools

n,m = map(int, input().split())
edge_set = {tuple(map(int, input().split())) for _ in range(m)}
counter = 0

for i in itertools.permutations(range(2, n+1), n-1):
  path = [1] + list(i)
  path_set = {tuple(sorted(edge)) for edge in zip(path, path[1:])}
  
  if path_set <= edge_set:
    counter += 1
 
  
print(counter)

Submission status: Accepted

Solution code:
from itertools import permutations
n,m=map(int,input().split())
A=[list(map(int, input().split())) for i in range(m)]
N=list(permutations([i+2 for i in range(n-1)]))
count=0
for k in range(len(N)):
    flag=0
    for i in range(n-1):
        if i ==0:
            for j in range(m):
                if set([N[k][0],1])== set(A[j]):
                    flag+=1
            if flag==n-1:
                count+=1
        else:
            for j in range(m):
                if set([N[k][i],N[k][i-1]])== set(A[j]):
                    flag+=1
            if flag==n-1:
                count+=1
print(count)

Submission status: Accepted

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

ans = 0

def dfs(n, visited):
    global ans
    visited.append(n)
    if len(visited) == N:
        ans += 1
    else:
        for i in l[n-1]:
            if i not in visited:
                dfs(i, visited)
    visited.remove(n)

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

dfs(1, [])
print(ans)

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(10**5)

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

es = [[] for _ in range(N)]

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


def solve(visited, node):
    visited[node] = True
    if all(visited):
        return 1

    cnt = 0
    for b in es[node]:
        if not visited[b]:
            cnt += solve(visited[:], b)

    return cnt


vis = [False] * N
ans = solve(vis, 0)
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

for p in itertools.permutations(range(1, N + 1)):
    if p[0] == 1:
        ans += 1
        for i in range(N - 1):
            if not (min(p[i], p[i + 1]), max(p[i], p[i + 1])) in AB:
                ans -= 1
                break

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m = inpl()
g = [[] for i in range(n)]
for i in range(m):
    a,b = inpl()
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
res = 0
seen = [False] * n
seen[0] = True
def dfs(node,seen):
    global res
    if sum(seen) == n:
        res += 1
        return 0
    for now in g[node]:
        if not seen[now]:
            seen[now] = True
            dfs(now,seen)
            seen[now] = False
dfs(0,seen)
print(res)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m = inpl()
g = [[] for i in range(n)]
for i in range(m):
    a,b = inpl()
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
res = 0
seen = [False] * n
def dfs(node,seen):
    global res
    seen[node] = True
    if sum(seen) == n:
        res += 1
    for now in g[node]:
        if not seen[now]:
          dfs(now,seen)  
    seen[node] = False
dfs(0,seen)
print(res)

Submission status: Accepted

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

seen = [False] * N

def dfs(node, seen, ans):
    seen[node] = True
    #print(node)
    if seen.count(True) == N:
        ans += 1
        seen[node] = False
        return ans

    for todo in edge[node]:
        if not seen[todo]:
            ans = dfs(todo, seen, ans)

    seen[node] = False
    return ans

print(dfs(0, seen, 0))

Submission status: Accepted

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

from collections import defaultdict
graph = defaultdict(list)
for i in range(m):
    a = ab[i][0] - 1
    b = ab[i][1] - 1
    graph[a].append(b)
    graph[b].append(a)

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

    # check
    f = True
    for j in range(len(orders) - 1):
        if orders[j+1] not in graph[orders[j]]:
            f = False
    if f:
        ans += 1
        # print(orders)

print(ans)

Submission status: Accepted

Solution code:
N , M = map(int,input().split())
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] * N
visited[0] = True

def dfs(now):
    ans = 0
    visited[now] = True
    #print(visited)
    if all(visited):
        visited[now] = False
        return 1

    for next_node in graph[now]:
        if visited[next_node]:
            continue
        ans += dfs(next_node)
    visited[now] = False
    return ans


print(dfs(0))

Submission status: Accepted

Solution code:
import itertools

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

ab = []
ans = 0
for _ in range(m):
	ab.append(list(map(int,input().split())))

l = list(itertools.permutations(range(1,n+1)))

for i in range(len(l)):
	count = 0
	for j in range(len(l[i])-1):
		tmp = [l[i][j],l[i][j+1]]
		if j == 0:
			if tmp[0] != 1:
				break
		tmp.sort()
		if tmp not in ab:
			break
		count += 1
		if count == n-1:
			ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

n, m = map(int, input().split())
graph = [set(map(lambda n: int(n) - 1, input().split())) for _ in range(m)]

print(sum(all(({0, per[i]} if not i else {per[i - 1], per[i]}) in graph for i in range(n - 1)) for per in permutations(i for i in range(1, n))))

Submission status: Accepted

Solution code:
from itertools import permutations

n, m = map(int, input().split())
graph = [set(map(lambda n: int(n) - 1, input().split())) for _ in range(m)]

per_list = permutations(i for i in range(1, n))

ans = 0

for per in per_list:
    for i in range(n - 1):
        target = {0, per[i]} if not i else {per[i - 1], per[i]}
        if target not in graph:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

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


for i in range(m):
    a,b = map(int,input().split())
    a -=1
    b-=1
    graph[a].append(b)
    graph[b].append(a)
def all_visited(l):
    a = 0
    for i in range(n):
        if l[i]:
            a+=1
    if a == n:
        return 1
    else: return 0
def dfs(now):

    ans = 0
    visited[now] = 1
  
    if all_visited(visited):
        
        return 1
    for next in graph[now]:
        if visited[next]:continue
        ans += dfs(next)
        visited[next] =0
    return ans
visited = [0]*n
print(dfs(0))

Submission status: Accepted

Solution code:

def search(N,adj):
    visited={1:[1]}
    S=[[1]]
    paths=[]
    while len(S)!=0:
        p=S.pop()
        if len(p)==N:
            paths.append(p)
        else:
            for w in adj[p[-1]]:
                if w not in p:
                    S.append(p+[w])
    return paths


if __name__ == '__main__':
    N,M=list(map(int,input().split()))
    ad={x:[] for x in range(1,N+1)}
    for i in range(M):
        a,b=list(map(int,input().split()))
        ad[a].append(b)
        ad[b].append(a)
    print(len(search(N,ad)))

Submission status: Accepted

Solution code:
import sys
n, m = [int(i) for i in sys.stdin.readline().split()]
graph = {i : [] for i in range(n)}
INF = 10 ** 18
for i in range(m):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

# memo_ls[i][j] 状態iでjにいる時の通り数
memo_ls = [[-1 for j in range(n)] for i in range(1 << n)]
# 状態sでvにいる通り数
def bit_dp(s, v):
    if memo_ls[s][v] >= 0:
        return memo_ls[s][v]
    if s == (1 << n) - 1:
        return 1
    res = 0
    for i in graph[v]:
        already = s >> i
        if not (already & 1):
            res += bit_dp((s | (1 << i)), i)
    memo_ls[s][v] = res
    return res

res = bit_dp(1, 0)
print(res)

Submission status: Accepted

Solution code:
N, M=map(int, input().split())
net=[[0 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
  net[a][b]=1
  net[b][a]=1
  
def f(N):
  nums=[i for i in range(1, N)]
  out=g([0], nums)
  return out

def g(order, nums):
  k=len(nums)
  if k==1:
    return [order+nums]
  else:
    out=[]
    for i in range(k-1):
      temp=g(order+[nums[i]], nums[:i]+nums[i+1:])
      out+=temp
    temp=g(order+[nums[-1]], nums[:-1])
    out+=temp
    return out
  
orderlists=f(N)
counter=0
for orderlist in orderlists:
  k=0
  for i in range(N-1):
    k+=net[orderlist[i]][orderlist[i+1]]
  if k==N-1:
    counter+=1
    
print(counter)

Submission status: Accepted

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

st = []
ap = [{1: True}]
heapq.heappush(st, (1, 0))
c = 0
while len(st) > 0:
    (node, log) = heapq.heappop(st)
    for b in Bs[node]:
        if b in ap[log]:
            continue
        elif len(ap[log]) == N - 1:
            c += 1
        else:
            heapq.heappush(st, (b, len(ap)))
            newlog = copy.copy(ap[log])
            newlog[b] = True
            ap.append(newlog)
print(c)

Submission status: Accepted

Solution code:
import copy
n, m = map(int, input().split())
adjacent_list = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
ans = 0

def dfs(node, finished):
    #print("node {}  finished {}".format(node, finished))
    finished.add(node)
    global ans
    if len(finished) == n:
        ans += 1
    else:
        for i in adjacent_list[node]:
            if i not in finished: 
                passed = copy.deepcopy(finished)
                dfs(i, passed)
dfs(1,set([1]))
print(ans)

Submission status: Accepted

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

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


def dfs(node, track):
    if len(track) == N:
        global res
        res += 1
    else:
        for dst in [x for x in edges[node] if x not in track]:
            dfs(dst, track + tuple([dst]))


res = 0
dfs(0, tuple([0]))
print(res)

Submission status: Accepted

Solution code:
from copy import deepcopy

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

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

path = [0]*n
path[0] = 1
# print(graph)
# print(path)

def func(i,path,ans):
    # print(i,path)
    if path.count(1) == n:
        return ans+1
    flag = 1
    for g in graph[i]:
        if path[g] == 0:
            flag = 0
            next_path = deepcopy(path)
            next_path[g] = 1
            ans = func(g,next_path,ans)
    return ans
ans = func(0,path,0)
print(ans)

Submission status: Accepted

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

web = [set() for _ in range(N)]
for _ in range(M):
	a, b = map(int, input().split())
	web[a-1].add(b-1)
	web[b-1].add(a-1)
way = list(P(range(1, N), N-1))
res = 0
for i in range(len(way)):
	if way[i][0] in web[0]:
		flag = True
		for j in range(1, N-1):
			if way[i][j] not in web[way[i][j-1]]:
				flag = False
				break
		if flag: res += 1

print(res)

Submission status: Accepted

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

graph = [[0] * N for _ in range(N)]

for _ in range(M):
    i, j = map(int, input().split())
    graph[i - 1][j - 1] = 1
    graph[j - 1][i - 1] = 1

count = 0
i = 0
memo = []
def DepthFirstSearch(i):
    global count
    memo.append(i + 1)
    if len(memo) == N:
        count += 1
        return
    for j in range(N):
        if graph[i][j] == 1:
            if j+1 in memo:
                continue
            DepthFirstSearch(j)
            memo.pop()
    return count

print(DepthFirstSearch(i))

Submission status: Accepted

Solution code:
from itertools import permutations
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

P = list(permutations([i for i in range(2, N + 1)]))
ans = 0
for p in P:
    flag = True
    for j in range(len(p) - 1):
        if j == 0:
            a = 1
            b = p[j]
            if [a, b] not in ab:
                flag = False
        a = min(p[j], p[j + 1])
        b = max(p[j], p[j + 1])
        if [a, b] not in ab:
            flag = False
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product, permutations,combinations

N, M = map(int, input().split())
rel = [tuple(map(int, input().split())) for i in range(M)]
memo = [[0]*N for i in range(N)]
for r in rel:
        memo[r[0]-1][r[1]-1] = 1
        memo[r[1]-1][r[0]-1] = 1

V = [i+1 for i in range(N)]

cnt = 0
for i in permutations(V, N):
    if i[0] > 1:
        break
        
    for j in range(N-1):
        if memo[i[j]-1][i[j+1]-1] == 0:
            break
    else:
        cnt+=1

print(cnt)

Submission status: Accepted

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

for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    p[a][b]=True
    p[b][a]=True
ans=0
for i in itertools.permutations(range(1,n),n-1):
    list=[0]+[k for k in i]
    if all(p[list[j]][list[j+1]]==True for j in range(n-1)):
        ans+=1
print(ans)

Submission status: Accepted

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

for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    p[a][b]=True
    p[b][a]=True
ans=0
for i in itertools.permutations(range(n),n):
    if i[0]==0:
        for j in range(n):
            if j==n-1:
                ans+=1
                break
            if not p[i[j]][i[j+1]]:
                break
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m = inpl()
g = [[False for j in range(n)] for i in range(n)]
for i in range(m):
    a,b = inpl()
    a -= 1
    b -= 1
    g[a][b] = True
    g[b][a] = True
# print(g)
res = 0
for flag in itertools.permutations(range(1,n)):
    # print(flag)
    for i in range(n-1):
        if i == 0:
            if not g[0][flag[0]]:
                break
            continue
        if not g[flag[i]][flag[i-1]]:
            break
    else:
        res += 1
print(res)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
g=[[] for _ in range(n)]
cnt=[0]
for _ in range(m):
    a,b=map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
def dfs(z,s):
    if sum(z)==n:
        cnt[0]+=1
    else:
        for i in g[s]:    
            if z[i]==0:
                dfs(z[:i]+[1]+z[i+1:],i)

dfs([1]+[0]*(n-1),0)
print(*cnt)

Submission status: Accepted

Solution code:
# ABC054C
# 方針：階乗の全探索

import itertools
N, M = map(int, input().split())
# Graph の作成
graph = [[] * N for _ in range(N)]
for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph[u].append(v)
    graph[v].append(u)

# パターンの全列挙
num_lst = [_ for _ in range(0, N)]
search_list = itertools.permutations(num_lst)

ans = 0
for lst in search_list:
    flag = True
    if lst[0] != 0:    # 1度でも先頭が0以外ならそれ以降は全てダメ
        break
    for i in range(N-1):
        if lst[i+1] in graph[lst[i]]:   # 今の数字が次の数字と繋がっているかどうか
            pass
        else:
            flag = False
            break
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
if sys.platform =='win32':
	sys.stdin=open('input.txt')
input = sys.stdin.readline
def MAP(): return [int(x) for x in input().split()]


N, M = MAP()
G = [[] for _ in range(N)]
for i in range(M):
	a,b = MAP()
	G[a-1].append(b-1)
	G[b-1].append(a-1)

permutations = (list(itertools.permutations(range(len(G)))))

paths = [p for p in permutations if p[0]==0]

count = 0
for path in paths:
	#print(path)
	for idx,v in enumerate(path):
		if idx == len(path)-1:
			count+=1
			break
		if path[idx+1] in G[v]: continue
		else: break

print(count)

Submission status: Accepted

Solution code:
import collections
def main():

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

    # print(graph)

    cur = [[1, 1 << 1]]
    for _ in range(N-1):
        temp = []
        for a, h in cur:
            for b in graph[a]:
                if (h >> b) % 2 == 0:
                    temp.append([b, h | (1 << b)])
        cur = temp
        # print(cur)
    return len(cur)

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(M)]
visited = [0]*N
ans = 0
def move(vert):
    global ans
    visited[vert-1] = 1
    if sum(visited) == N:
        ans += 1
        visited[vert-1] = 0
        return 0 
    for i in range(M):
        if ab[i][0] == vert and visited[ab[i][1]-1] == 0:
            move(ab[i][1])
        elif ab[i][1] == vert and visited[ab[i][0]-1] == 0:
            move(ab[i][0])
    visited[vert - 1] = 0
    return ans
print(move(1))

Submission status: Accepted

Solution code:
import itertools
N,M = map(int,input().split())
sides = []
for m in range(M):
    x,y = map(int,input().split())
    sides.append((x,y))
vertex = (i for i in range(2,N+1))
ans = 0
for v in itertools.permutations(vertex, N-1):
    T = 1
    if (1,v[0]) not in sides:
        T = 0
    for i in range(N-2):
        if (v[i],v[i+1]) not in sides and (v[i+1],v[i]) not in sides:
            T = 0
            break
    if T == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

p = list(itertools.permutations(range(N)))

Sum = 0

for i in range(len(p)):
    if p[i][0] != 0:
        break
    for j in range(N - 1):
        if graph[p[i][j]][p[i][j + 1]] != 1:
            break
        elif j == N - 2:
            Sum += 1

print(Sum)

Submission status: Accepted

Solution code:
import itertools

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

Submission status: Accepted

Solution code:
from itertools import permutations
N,M=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(M)]
g=[[False]*N for i in range(N)]
for a,b in ab:
  g[a-1][b-1]=True
  g[b-1][a-1]=True
nodes=[i for i in range(1,N)]
ans=0
for route in permutations(nodes):
  if g[0][route[0]]== False:
    continue
  for i in range(N-1):
    if i == N-2:
      ans+=1
      
      break
    elif g[route[i]][route[i+1]]:
      continue
    else:
      break
print(ans)