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:
N,M = map(int,input().split())

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

check = [False] * N

def dfs(now):
    global cnt
    global ans
    if cnt == N:
        ans += 1
    else:
        for i in line[now]:
            if check[i] == False:
                check[i] = True
                cnt += 1
                dfs(i)
                check[i] = False
                cnt -= 1

check[0] = True
cnt = 1
ans = 0
dfs(0)
print(ans)

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

N,M=LI()
graph=[[False]*8 for _ in range(8)]

for _ in range(M):
  a,b=LI()
  a-=1
  b-=1
  graph[a][b]=True
  graph[b][a]=True

def dfs(v,visited):
  all_visited=True
  for i in range(N):
    if not visited[i]:
      all_visited=False
  if all_visited:
    return 1

  ret=0
  for i in range(N):
    if not graph[v][i]:
      continue
    if visited[i]:
      continue
    visited[i]=True
    ret+=dfs(i,visited)
    visited[i]=False

  return ret

visited=[False]*N
visited[0]=True
print(dfs(0,visited))

Submission status: Accepted

Solution code:
from itertools import permutations
from collections import deque

def main():
    N, M = map(int, input().split())
    edge = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        edge[a].append(b)
        edge[b].append(a)
    cnt = 0
    for patterns in permutations(range(1,N)):
        pattern = [0] + list(patterns)
        Q = deque(pattern)
        while Q:
            s = Q.popleft()
            if Q[0] in edge[s]:
                if len(Q) == 1:
                    Q.popleft()
                    break
                else:
                    continue
            else:
                break
        if not Q:
            cnt += 1
    
    print(cnt)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
n_ver, n_edge = map(int,input().split())
ad_ls = [[] for _ in range(n_ver)]
for i in range(n_edge):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    ad_ls[a].append(b)
    ad_ls[b].append(a)
done_ls = [0] * n_ver
def dfs(ver):
    done_ls[ver] = 1
    num = 0
    if done_ls == [1] * n_ver:
        done_ls[ver] = 0
        return 1
    for nex in ad_ls[ver]:
        if done_ls[nex]:
            continue
        num += dfs(nex)
    done_ls[ver] = 0
    return num
print(dfs(0))

Submission status: Accepted

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

li = [[0]*n for _ in range(n)]


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

def dfs(v,used):
    if not False in used:
        return 1


    ans=0
    for i in range(n):
        if not li[v][i]:
            continue
        elif used[i]:
            continue

        else:
            used[i]=True
            ans+=dfs(i,used)
            used[i]=False

    return ans

used=[False]*n
used[0]=True
print(dfs(0,used))

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N, M = LI()
    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b = LI_()
        G[a].append(b)
        G[b].append(a)

    ans = [0]
    visited = [False] * N
    def dfs(c, depth):
        visited[c] = True
        if depth == N - 1:
            ans[0] += 1
        else:
            for n in G[c]:
                if not visited[n]:
                    dfs(n, depth + 1)
                    visited[n] = False

    dfs(0, 0)

    print(ans[0])

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from networkx import *
n, m = map(int, input().split())
a = [list(map(int, input().split())) for i in range(m)]
g = Graph(a)
ans = 0
for i in range(2, n + 1):
  for p in all_simple_paths(g, 1, i):
    if len(p) == n:
      ans += 1
print(ans)

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)
#print(edge)

import itertools
l = []
for i in range(1,n):
    l.append(i)
llist = list(itertools.permutations(l))
#print(llist)

ans = 0
for i in range(len(llist)):
    x = [0] + list(llist[i])
    tnp = 0
    for j in range(n-1):
        if not x[j+1] in edge[x[j]]:
            tnp += 1
            break
    if (tnp==0):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

ans = 0
x = list(itertools.permutations(range(1, n+1)))
for i in range(len(x)):
    if x[i][0] == 1:
        for j in range(n-1):
            if h[x[i][j]-1][x[i][j+1]-1] == 0:
                break
        else:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

ans = 0
x = list(itertools.permutations(range(1, n+1)))
for i in range(len(x)):
    flag = False
    if x[i][0] == 1:
        flag = True
        for j in range(n-1):
            if h[x[i][j]-1][x[i][j+1]-1] == 0:
                flag = False
                break
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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

dp = [[0]*N for _ in range(1<<N)]
dp[1][0] = 1
for i in range(1<<N):
    for j in range(N):
        # 今jにいて、いったことのない場所に行く
        for nx in query[j]:
            if not (i>>nx)&1:
                dp[i+(1<<nx)][nx] += dp[i][j]

print(sum(dp[-1]))

Submission status: Accepted

Solution code:
import itertools

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

c = list(itertools.permutations(range(n)))
cnt = 0
for i in range(len(c)):
    if c[i][0] == 0:
        for j in range(n-1):
            if p[c[i][j]][c[i][j+1]] != 1:
                break
        else:
            cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
from itertools import permutations
n_ver,n_edge = map(int,input().split())
path_mat = [[0]*n_ver for _ in range(n_ver)]
for i in range(n_edge):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    path_mat[a][b] = 1
    path_mat[b][a] = 1
ans = 0
vers = [i for i in range(n_ver)]
for path in permutations(vers):
    if path[0] != 0:
        continue
    can = True
    for i in range(n_ver-1):
        from_ = path[i]
        to = path[i+1]
        if not path_mat[from_][to]:
            can = False
            break
    if can:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

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

edges = {tuple(sorted(map(int, input().split()))) for _ in range(m)}
ans = 0

for i in permutations(range(2,n+1), n-1):
    l = [1] + list(i)
    tmp = sum(1 for edge in zip(l, l[1:]) if tuple(sorted(edge)) in edges) == n-1
    ans += tmp
print(ans)

Submission status: Accepted

Solution code:
def dfs(parent, connect, passed, N): #深さ優先探索
    cnt = 0
    passed.append(parent) #通った点をメモ
    if len(passed) == N: #全ての点を通過したかの判定
        cnt = 1
    for next_ in connect[parent]:
        if next_ in passed:
            continue
        cnt += dfs(next_, connect, passed, N) #全ての点を通るまで再帰. 戻り値の和で何通りかカウント
    passed.pop() #分岐点に戻る前にメモを1段だけ破棄
    return cnt    

N, M = map(int, input().split())
connect = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    connect[a-1].append(b-1)
    connect[b-1].append(a-1)
ans = dfs(0, connect, [], N) #点0からのdfs
print(ans)

Submission status: Accepted

Solution code:
def dfs(parent, connect, passed, N):
    cnt = 0
    passed.append(parent)
    if len(passed) == N:
        cnt = 1
    for next_ in connect[parent]:
        if next_ in passed:
            continue
        cnt += dfs(next_, connect, passed, N)
    passed.pop()
    return cnt    

N, M = map(int, input().split())
connect = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    connect[a-1].append(b-1)
    connect[b-1].append(a-1)
ans = dfs(0, connect, [], N)
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import permutations

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    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))

    res = 0
    for pattern in permutations(range(n)):
        if pattern[0] == 0:
            for i in range(1, n):
                prev = pattern[i - 1]
                now = pattern[i]
                if (prev, now) not in edge:
                    break
            else:
                res += 1
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

import itertools
import numpy as np
import collections


Dist = np.array([[0]*N]*N)

for i in range (0, M):
	B, C = map(int, input().split())
	Dist[B-1][C-1] = 1
	Dist[C-1][B-1] = 1

V = collections.deque(itertools.permutations(range(0, N), N))

count = 0

while V:
	P = V.popleft()
	if P[0] == 0:
		d = 0
		for i in range (1, N):
			if Dist[P[i]][P[i-1]] == 1:
				d+=1
			else:
				break
		if d == N-1:
			count+=1
	else:
		continue        

print(count)

Submission status: Accepted

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

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


l = []
for i in permutations(range(1, n), n-1):
    l.append([0] + list(i))


ans= 0
for i in range(len(l)):
    k = l[i]
    for j in range(n-1):
        if p[k[j]][k[j+1]] != 1:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import itertools
N, M = map(int, input().split())
edges = [input().replace(" ", "") for i in range(M)]
res = 0
for l in itertools.permutations(list(range(1,N+1,1))):
    if l[0]!=1:
        continue
    for i in range(len(l)-1):
        e = str(min(l[i], l[i+1])) + str(max(l[i], l[i+1]))
        if not e in edges:
            break
    else:
        res += 1
print(res)

Submission status: Accepted

Solution code:
from itertools import permutations as per
n,m = map(int,input().split())
g = [[] for _ in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
ans = 0

for l in per(range(n)):
    if l[0] != 0:
        continue
    flag = 1
    for i in range(n-1):
        if l[i+1] not in g[l[i]]:
            flag = 0
            break
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

N,M = map(int,input().split())
masu = [[0]*N for _ in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    masu[a][b] = 1
    masu[b][a] = 1
ans = 0
for i in permutations(range(N)):
    if i[0] != 0:continue
    for j in range(N):
        if j==N-1:
            ans += 1
            break
        if not masu[i[j]][i[j+1]]:
            break
print(ans)

Submission status: Accepted

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

paths = itertools.permutations([i for i in range(n)], n)
ok = 0
for path in paths:
    if path[0] != 0:
        continue
    flag = True
    for ei in range(len(path)-1):
        if edge[path[ei]][path[ei+1]] == 0:
            flag = False
        if flag is False:
            break
    if flag:
        ok += 1
print(ok)

Submission status: Accepted

Solution code:
import itertools

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

c = [i for i in range(2, n + 1)]
b = []
for x in itertools.permutations(c):
  b.append([1] + list(x))
  
cnt = 0
for x in b:
  exist = True
  for i in range(n-1):
    if not sorted(x[i:i+2]) in a:
      exist = False
      break
  if exist:
    cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import collections
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    N, M = NMI()
    ab = [NLI() for _ in range(M)]
    
    l = [n for n in range(2,N+1)]
    
    per_list = list(itertools.permutations(l))
    ans = 0
    for p in range(len(per_list)):
        ls_p = list(per_list[p])
        ls_p.insert(0,1)
        
        flg = True
        for n in range(N-1):
            if not [min(ls_p[n],ls_p[n+1]),max(ls_p[n],ls_p[n+1])] in ab:
                flg = False
                continue
        else:
            if flg == True:
                ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

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

count = 0
for perm in itertools.permutations(range(1, n)):
    if not perm[0] in edges[0]:
        continue
    can_visit_all = True
    for i in range(n - 2):
        if not perm[i + 1] in edges[perm[i]]:
            can_visit_all = False
            break
    if can_visit_all:
        count += 1
print(count)

Submission status: Accepted

Solution code:
from itertools import permutations

n,m = map(int, input().split())
gl = [ [False]*(n+1) for _ in range(n+1) ]
for _ in range(m):
    a,b = map(int, input().split())
    gl[a][b] = True
    gl[b][a] = True


ll = list(range(2,n+1))  # list of elements
perml = list(permutations(ll, n-1))
ans = 0

for perm in perml:
    curr = 1
    for v in perm:
        if gl[curr][v]:
            curr = v
        else:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools as it

n,m=map(int,input().split())
ans=[]
for i in range(m):
    a,b=map(int,input().split())
    ans.append([a,b])
    ans.append([b,a])
  
a=0
for e in it.permutations(range(n)):
    #print(e)
    count=1
    if e[0]!=0:
        break
    
    for i in range(n-1):
        if [e[i]+1,e[i+1]+1] in ans:
            count*=1
        else:
            count*=0
            break
            
    a+=count
    
print(a)

Submission status: Accepted

Solution code:
import itertools

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

link_flag = 1
cnt = 0

for k in itertools.permutations(range(n)): #順列を生成して、それらに対して処理
    if k[0] != 0:
        break
    link_flag = 1
    for i in range(len(k)-1):
        if link_flag == 0:
            break
        link_flag = 0
        for j in range(m):
            if k[i]+1 == a_list[j]:
                if k[i+1]+1 == b_list[j]:
                    link_flag = 1
                    #print(k,a_list[j],b_list[j])
                    break
            if k[i]+1 == b_list[j]:
                if k[i+1]+1 == a_list[j]:
                    link_flag = 1
                    #print(k,a_list[j],b_list[j])
                    break
        if i == len(k)-2 and link_flag ==1:
            cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
from itertools import permutations

n,m = map(int,input().split())
ans = 0
dp = list([ 0 for i in range(n)] for _ in range(n))

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

l = [i for i in range(1,n)]
for j in permutations(l):
    bit = 1
    if dp[0][j[0]]!=1:
        bit = 0
    for i in range(n-2):
        if dp[j[i]][j[i+1]]!= 1:
            bit = 0
    if bit==1:
        ans += 1
print(ans)

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):
  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 collections
import itertools

N, M = map(int, input().split())
a, b = list(zip(*[map(int, input().split()) for _ in range(M)]))

paths = collections.defaultdict(list)
for i in range(M):
    paths[a[i] - 1].append(b[i] - 1)
    paths[b[i] - 1].append(a[i] - 1)

ans = 0
for perm in itertools.permutations(range(N)):
    if perm[0] != 0:
        continue

    for i in range(1, N):
        if perm[i] not in paths[perm[i - 1]]:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools

P = []
counter = 0
if __name__ == '__main__':
    N, M = map(int, input().split())
    P = [[0]*N for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        P[a-1][b-1] = P[b-1][a-1] = 1
    for v in itertools.permutations(range(N)):
        if v[0] != 0:
            break
        flag = 0
        for i in range(N - 1):
            if P[v[i]][v[i + 1]] == 0:
                flag = 1
                break
        if flag == 0:
            counter += 1
        
    print(counter)

Submission status: Accepted

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

G=[[] for _ in range(N+1)]

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

def dfs(v,seen=None,h=[]):
    global ans
    if not seen:
      seen = [0]*(N+1)
    seen[v] = 1
    if len(h) == N:
        ans += 1
        return
    update=0
    for u in G[v]:
        if seen[u] == 0:
          seen[u] = 1
          h.append(u)
          update = 1
          dfs(u,seen,h)
          h.pop()
          seen[u] = 0
    if update==0:return

dfs(1,h=[1])
print(ans)

Submission status: Accepted

Solution code:
# ABC_054_C_One_Stroke_Path.py

from itertools import permutations
N, M = list(map(int, input().split()))
L=[]
for _ in range(M):
    L.append(list(map(int, input().split())))
# print(L)

P = list(permutations(range(1,N+1)))
# print(P)
ct = 0
for i in P:
    if i[0]==1 and \
    all((sorted([i[j], i[j+1]]) in L) for j in range(N-1)):
        ct += 1
print(ct)

Submission status: Accepted

Solution code:
import itertools
import numpy as np


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

count=0
for route in ls:
    if route[0]!=1:
        break

    flag = True
    for i in range(n-1):
        if ( ([route[i],route[i+1]] in ab) or ([route[i+1],route[i]] in ab) )  == False:
            flag = False
            continue
    if flag == False:
        continue
    count +=1

print(count)

Submission status: Accepted

Solution code:
import itertools

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

count = 0
for c in itertools.permutations(bag):
    if not c[0] == 1:
        continue
    flag = False
    for i in range(N-1):
        if not c[i+1] in V[c[i]-1]:
            flag = True
            break
    if not flag:
        count += 1
print(count)

Submission status: Accepted

Solution code:
from collections import deque
import copy
# https://atcoder.jp/contests/abc054/tasks/abc054_c
# n!の全探索が答えというのは知っているが、自分の開放の誤りを見つけるために自分のやり方でといてみる。

N, M = map(int, input().split())
V = [[] for _ in range(N)]
cont = [0 for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    V[a-1].append([b, copy.deepcopy(cont)])
    V[b-1].append([a, copy.deepcopy(cont)])

# solution
q = deque()
q.append([1, copy.deepcopy(cont)])
count = 0
while q:
    c_v = q.pop()
    c_v[1][c_v[0]-1] = 1
    next_vs = V[c_v[0]-1]
    ifComplete = 1
    for v in next_vs:
        if c_v[1][v[0]-1] == 1:
            continue
        else:
            ifComplete = 0
        # ここで続くvの探索が始まる時に全て訪問されていればcountを増やす。
        # その状態をどうやって管理すればいい？
        v[1] = copy.deepcopy(c_v[1])
        q.append(v)
    # 遷移先のノードが存在しない場合
    if ifComplete:
        flag = 1
        for x in c_v[1]:
            if x == 0:
                flag = 0
                break
        if flag:
            count += 1
print(count)

Submission status: Accepted

Solution code:
import itertools

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

ls = [[] for _ in range(n)]

for _ in range(m):
    s, t = map(int, input().split())
    ls[s-1].append(t-1)
    ls[t-1].append(s-1)

count = 0
for per in itertools.permutations(range(n)):

    if per[0] != 0:
        continue
    for i in range(1, n):
        if per[i] not in ls[per[i-1]]:
            break
        if i == n-1:
            count += 1

print(count)

Submission status: Accepted

Solution code:
import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
from collections import Counter
from math import ceil
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import Decimal #floatの高精度ver, 渡すのはstr型で
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########

from itertools import permutations as per
n,m=map(int,input().split())
A=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1 ;b-=1
    A[a].append(b)
    A[b].append(a)

ans=0
for bit in per([i for i in range(1,n)]):
    # print(bit)
    peanut=0
    bit=[0]+list(bit)
    for i in range(n-1):
        if not bit[i] in A[bit[i+1]]:
            peanut=1
            break
    else:
        ans+=1
    

print(ans)

Submission status: Accepted

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

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

def dfs(v, used):
    if not False in used:
        return 1
    
    ans = 0
    for i in range(N):
        if not adj_matrix[v][i]:
            continue
        if used[i]:
            continue
        
        used[i] = True
        ans += dfs(i, used)
        used[i] = False
    
    return ans

used = [False] * N
used[0] = True

print(dfs(0, used))

Submission status: Accepted

Solution code:
from itertools import permutations
n,m=map(int,input().split())
e=[[]for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  e[a-1]+=[b-1]
  e[b-1]+=[a-1]
num=list(permutations([0]+list(range(1,n))))
ans=0
for i in range(len(num)):
  if num[i][0]!=0:continue
  s=1
  now=0
  while s<n:
    if num[i][s] in e[now]:
      now=num[i][s]
      s+=1
    else:break
  if s==n:ans+=1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
e=[[]for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  e[a-1]+=[b-1]
  e[b-1]+=[a-1]
def dfs(now,vis):
  vis+=[now]
  if len(vis)==n:return 1
  res=0
  for to in e[now]:
    if to not in vis:
      res+=dfs(to,vis[:])
  return res
print(dfs(0,[]))

Submission status: Accepted

Solution code:
from itertools import permutations
n,m=map(int,input().split())
e=[[]for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  e[a-1]+=[b-1]
  e[b-1]+=[a-1]
def dfs(now,vis):
  vis+=[now]
  if len(vis)==n:return 1
  res=0
  for to in e[now]:
    if to not in vis:
      res+=dfs(to,vis[:])
  return res
print(dfs(0,[]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

class Graph():

    def __init__(self):
        self.adjacency_dict = {}
    
    def add_vertex(self, v):
        self.adjacency_dict[v] = []

    def add_edge(self, v1, v2):
        self.adjacency_dict[v1].append(v2)
        self.adjacency_dict[v2].append(v1)

    def remove_edge(self, v1, v2):
        self.adjacency_dict[v1].remove(v2)
        self.adjacency_dict[v2].remove(v1)

    def remove_vertex(self,v):
        while self.adjacency_dict[v] != []:
            adjacency_vertex = self.adjacency_dict[v][-1]
            self.remove_edge(v, adjacency_vertex)
        del adjacency_vertex[v]

    def get_vertexes(self):
        return self.adjacency_dict.keys()

    def get_edges(self, v):
        return self.adjacency_dict[v]

    def print_graph(self):
        print(self.adjacency_dict)

import itertools

g = Graph()
N, M = map(int, input().strip().split())
for i in range(N):
    g.add_vertex(i+1)
for _ in range(M):
    a, b = map(int, input().strip().split())
    g.add_edge(a, b)
res = 0
permutations_vertexes = itertools.permutations(g.get_vertexes())
for permutation in permutations_vertexes:
    prev_vertex = permutation[0]
    if prev_vertex != 1:
        continue
    can_all_vertex = True
    for vertex in permutation:
        if prev_vertex == vertex:
            continue
        if vertex not in g.get_edges(prev_vertex):
            can_all_vertex = False
            break
        prev_vertex = vertex
    if can_all_vertex:
        res += 1
print(res)

Submission status: Accepted

Solution code:
from collections import deque
import copy

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

waiting = deque()
flag_s = [0]*N
start_point = 0
waiting.append([start_point, flag_s])
cnt = 0
while len(waiting) != 0:
    cur_node, flag = waiting.pop()
    flag = copy.deepcopy(flag)
    flag[cur_node] = 1
    if sum(flag) == N: cnt += 1
    for e in e_list[cur_node]:
        if flag[e] != 1:
            waiting.append([e, flag])

print(cnt)

Submission status: Accepted

Solution code:
from collections import defaultdict

N, M = map(int, input().split())
adj_list = defaultdict(set)

for i in range(M):
    a, b = map(int, input().split())
    adj_list[a].add(b)
    adj_list[b].add(a)

visited = set() # 隣接ノードが1つだけになるノードを順々に追加

res = 0

def backtrack(visited, num):
    global res
    if num in visited:
        return
    if len(visited | {num}) == N:
        res = res + 1
        return

    for neighbor in adj_list[num]:
        backtrack(visited | {num}, neighbor)

backtrack(visited, 1)

print(res)

Submission status: Accepted

Solution code:
import itertools as it
import sys

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

a=[]

for i in range(M):
    x,y=map(int,input().split())
    a.append([x,y])
    a.append([y,x])

ans=0
for e in it.permutations(range(N)):
    if e[0]!=0:
        break
        
    count=1
    for j in range(N-1):
        if [e[j]+1,e[j+1]+1] in a:
            count*=1
        else:
            count*=0
            break
            
    ans+=count

print(ans)

Submission status: Accepted

Solution code:
import itertools as it
import sys

N, M = map(int, input().split())
if N==0 or M==0:
    print(0)
    sys.exit()
a=[]

for i in range(M):
    x,y=map(int,input().split())
    a.append([x,y])
    a.append([y,x])

ans=0
for e in it.permutations(range(N)):
    if e[0]!=0:
        break
        
    count=1
    for j in range(N-1):
        if [e[j]+1,e[j+1]+1] in a:
            count*=1
        else:
            count*=0
            break
            
    ans+=count

print(ans)

Submission status: Accepted

Solution code:
import itertools
N,M=map(int,input().split())
branch=[]
for _ in range(M):
    a,b=map(int,input().split())
    branch.append([a,b])
    branch.append([b,a])
ans=0
for perm in itertools.permutations(list(range(1,N+1))):
    f=True
    if perm[0]==1:
        for i in range(N-1):
            if not [perm[i],perm[i+1]] in branch:
                f=False
        if f:
            ans+=1
print(ans)