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:
#!/usr/bin/env python3
import sys
from collections import defaultdict
INF = float("inf")

count = 0


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    A = [[0]*N for _ in range(N)]

    def dfs(curr, visited):
        global count
        visited[curr] = True
        if all(visited):
            count += 1
            return

        for t in edges[curr]:
            if visited[t] == False:
                dfs(t, visited[:])
        return

    edges = defaultdict(list)
    for aa, bb in zip(a, b):
        edges[aa-1].append(bb-1)
        edges[bb-1].append(aa-1)
    dfs(0, [False]*N)
    print(count)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]"
    b = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, M, a, b)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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):
            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
N,M = map(int,input().split())
r = []
for _ in range(M):
    add = list(map(int,input().split()))
    r.append(add)
    r.append(add[::-1])
A = [i for i in range(2,N + 1)]
A = list(itertools.permutations(A,N - 1))
ans = 0
for check in A:
    q = 0
    p = [1] + list(check)
    for c in range(N - 1):
        if p[c:c + 2] in r:
            q += 1
    if q == N - 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

d = dict()
for i in range(1, N+1):
    d[i] = list()
for m in range(M):
    a, b = map(int, input().split())
    d[a].append(b)
    d[b].append(a)

ans = 0
for p in itertools.permutations(range(2, N+1)):
    nodes = {1}
    prev_node = 1
    for i, n in enumerate(p):
        if n not in d[prev_node]:
            break

        else:
            prev_node = n
            nodes.add(n)

        if len(nodes) == N:
            ans += 1
            break

print(ans)

Submission status: Accepted

Solution code:
import copy


N, M = list(map(int,input().split()))
graph = [dict() for i in range(N)]
for i in range(N):
	graph[i]["edge"] = []
for i in range(M):
	a, b = list(map(int, input().split()))
	graph[a - 1]["edge"].append(b - 1)
	graph[b - 1]["edge"].append(a - 1)

def pow(N):
	ans = 1
	for i in range(N):
		ans *= i + 1
	return  ans

total = 0
for i in range(pow(N - 1)):
	node = [a+1 for a in range(N - 1)]
	num = i
	zyun = [0]
	for j in range(N - 1, 0 , -1):
		mod = num % j
		num -= num % j
		num = num//j
		zyun.append(copy.deepcopy(node[mod]))
		del node[mod]
	judge = 1
	for loc in range(N - 1):
		if not zyun[loc + 1] in graph[zyun[loc]]["edge"]:
			judge = 0
	total += judge

print(total)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

from functools import reduce

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

# 隣接行列
edges = [[False for j in range(N)] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    edges[a-1][b-1] = True
    edges[b-1][a-1] = True
# print(edges)

def DFS(v, N, 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 edges[v][i]:
            continue
        if visited[i]:
            continue

        visited[i] = True
        ret += DFS(i, N, visited)
        visited[i] = False

    return ret

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

Submission status: Accepted

Solution code:
#隣接行列を書く
n,m = map(int,input().split())
ll = [[0]*n for _ in [0]*n]
for i in range(m):
  a,b = map(int,input().split())
  ll[a-1][b-1] = 1
  ll[b-1][a-1] = 1
#初期は1番目の点のみ訪問済み。かつ現在地は0番目
visit = [1]+[0]*(n-1)
place = 0
ans=0
#探索用関数
def search(visit,place):
  ans = 0
  if visit == [1]*n:
    return 1
  for i in range(n):
    if visit[i] == 0 and ll[place][i] == 1:
      tmpvisit = visit.copy()
      tmpvisit[i] = 1
      ans += search(tmpvisit,i)
  return ans
ans = search(visit,place)
print(ans)

Submission status: Accepted

Solution code:
import itertools
n, m = map(int, input().split())
ab = {}
for i in range(n+1):
    ab[i] = []
for i in range(m):
    a, b = map(int, input().split())
    ab[a].append(b)
    ab[b].append(a)

count = 0
 
for values in list(itertools.permutations(range(2, n+1))):
    pre = 1
    for i, v in enumerate(values):
        if(v not in ab[pre]):
            break
        if i == n-2:
            count += 1
        pre = v

print(count)

Submission status: Accepted

Solution code:
# One-stroke Path
import itertools
n, m = map(int, input().split())
ab = {}
for i in range(n+1):
    ab[i] = []
for i in range(m):
    a, b = map(int, input().split())
    ab[a].append(b)
    ab[b].append(a)

count = 0

for values in list(itertools.permutations(range(2, n+1))):
    pre = 1
    for i, v in enumerate(values):
        if(v not in ab[pre]):
            break
        if i == n-2:
            count += 1
        pre = v
print(count)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
path = list([False] * n for _ 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
import itertools
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:
#!/usr/bin/env python3
n, m = map(int, input().split())
g = [[] for i in range(n)]
for i in range(m):
    a, b = map(lambda x: int(x) - 1, input().split())
    g[a].append(b)
    g[b].append(a)


def dfs(used, s):
    global ans
    used[s] = True
    for t in g[s]:
        if not used[t]:
            dfs(used[:], t)
    if all(used):
        ans += 1


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

Submission status: Accepted

Solution code:
import itertools

n,m = map(int,input().split())
graph = {i+1:set() for i in range(n)}

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

count = 0
node = [i+2 for i in range(n-1)]

for i in itertools.permutations(node):
    route = [1] + list(i)
    flag = True
    for j in range(n-1):
        if route[j+1] not in graph[route[j]]:
            flag = False
            break
    if flag == True:
        count += 1
print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict

n, m = map(int, (input().split()))
dic = defaultdict(list)
seen = [False] * (n+1)
count = 0

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


def dfs(pos, pre_pos, depth, seen):
    if seen[pos]:
        return

    seen[pos] = True
    todo = dic[pos]

    for next_pos in todo:
        if next_pos == pre_pos:
            continue
        dfs(next_pos, pos, depth+1, seen)

    seen[pos] = False
    if depth == n:
        global count
        count += 1
    return


dfs(1, -1, 1, seen)
print(count)

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    mat = [[0]*n for i in range(n)]
    l = [list(map(int, input().split())) for _ in range(m)]
 
    for i in l:
        mat[i[0]-1][i[1]-1] = 1
        mat[i[1]-1][i[0]-1] = 1
 
    
    ver = [i for i in range(n)]
 
    cnt = 0
 
    def dfc(now, moved):
        
        nonlocal cnt
 
        moved.sort()
        if moved == ver:
            cnt += 1
        
        for i in range(n):
            if (mat[now][i] == 0) or (i in moved):
                continue
            
            dfc(i, moved + [i])
 
    dfc(0, [0])
    print(cnt)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():

    n, m = map(int, input().split())
    tree = [[]*n for i in range(n)]
    l = [list(map(int, input().split())) for _ in range(m)]
    
    for i in l:
        tree[i[0]-1].append(i[1]-1)
        tree[i[1]-1].append(i[0]-1)

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

    cnt = 0

    def dfc(now, moved):
        
        nonlocal cnt
     
        moved.sort()
        if moved == ver:
            cnt += 1

        for i in tree[now]:
            if i in moved:
                continue
            dfc(i, moved + [i])

    dfc(0, [0])
    print(cnt)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,M=list(map(int,input().split()))
a = [list(map(int,input().split())) for i in range(M)]
seen = [-1 for i in range(N)]
count = 0
def dfs(x):
    global count
    if sum(seen) == N:
        count += 1
        return
    
    for i in range(M):
        if a[i][0] == x and seen[a[i][1]-1] == -1:
            seen[a[i][1]-1] = 1
            dfs(a[i][1])
            seen[a[i][1]-1] = -1
        if a[i][1] == x and seen[a[i][0]-1] == -1:
            seen[a[i][0]-1] = 1
            dfs(a[i][0])
            seen[a[i][0]-1] = -1
seen[0] = 1
dfs(1)
print(count)

Submission status: Accepted

Solution code:
from copy import copy
n, m = map(int,input().split())
ab = [[0 for i in range(n)] for j in range(n)]
for i in range(m):
    ai,bi = map(int,input().split())
    ab[ai-1][bi-1] = 1
    ab[bi-1][ai-1] = 1

count = 0

def dfs(x,v):
    l = copy(v)
    l.append(x)
    if len(l)==n:
        global count
        count += 1
    for i in range(n):
        if ab[x][i] == 1 and not i in l:
            dfs(i,l)
    
dfs(0,[])
print(count)

Submission status: Accepted

Solution code:
import os,re,sys,operator
from collections import Counter,deque
from operator import itemgetter
from itertools import accumulate,combinations,groupby
from sys import stdin,setrecursionlimit
from copy import deepcopy
import heapq

setrecursionlimit(10**6)

def dfs(now,depth):
    global used
    global gragh
    global n
    ans=0

    if used[now]:
        return 0
    if depth==n:
        return 1
    used[now]=1
    for i in range(n):
        if gragh[now][i]:
            ans+=dfs(i,depth+1)
    used[now]=0
    return ans

n,m=map(int,stdin.readline().rstrip().split())
gragh=[[0]*n for _ in range(n)]

for i in range(m):
    a,b=map(int,stdin.readline().rstrip().split())
    gragh[a-1][b-1]=gragh[b-1][a-1]=1

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(m)]
tree = [[] for _ in range(n)]
for i in l:
  tree[i[0]-1].append(i[1]-1)
  tree[i[1]-1].append(i[0]-1)
l = [i for i in range(n)]
global ans
ans = 0
def search(now, moved):
  moved.sort()
  if moved == l:
    global ans
    ans += 1
  for i in tree[now]:
    if i in moved:
      continue
    search(i, moved + [i])
  
search(0, [0])
print(ans)

Submission status: Accepted

Solution code:

import collections
import itertools
import sys

def getint(): return int(input())
def getints(): return list(map(int, input().split()))


class Graph:
    def __init__(self, node_count, edge_count):
        self.lst = [-1 for _ in range(node_count)]
        self.nxt = [0  for _ in range(edge_count)]
        self.to  = [0  for _ in range(edge_count)]
        self.m   =  0

    def add_edge(self, u, v, w):  # bidirection weight
        m = self.m
        self.nxt[m], self.lst[u], self.to[m]= self.lst[u], m, (v, w)
        self.m += 1

    def traverse(self,u):
        m = self.lst[u]
        while m != -1:
            yield self.to[m]
            m = self.nxt[m]

n,m=getints()
graph = Graph(n,2*m)
for i in range(m):
    a,b=getints()
    graph.add_edge(a-1,b-1,1)
    graph.add_edge(b-1,a-1,1)

visited = [False] * n

def solve(u, visited):
    if visited[u]:
        return 0
    visited[u]=True
    if all(visited):
        visited[u]=False
        return 1
    res = 0
    for v,_ in graph.traverse(u):
        res += solve(v, visited)
    visited[u]=False
    return res

print(solve(0, visited))

Submission status: Accepted

Solution code:
import itertools


n, m = map(int, input().split())
edges = {tuple(sorted(map(int, input().split()))) for _ in range(m)}
ans = 0
for i in itertools.permutations(range(2, n+1), n-1):
    l = [1] + list(i)
    ans += sum([1 for edge in zip(l, l[1:]) if tuple(sorted(edge)) in edges]) == n-1
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
raw = [[] for _ in range(n)]
for _ in range(m):
  a,b = map(int,input().split())
  raw[a-1].append(b-1)
  raw[b-1].append(a-1)
#print(raw)
already = [0]
goal = [i for i in range(n)]
ans = 0
now = 0
last = 0
while True:
  try:
    if raw[now][last] not in already:
      now = raw[now][last]
      already.append(now)
      last = 0
    else:
      last += 1
  except:
    try:
      now = already[-2]
      last = raw[now].index(already[-1])+1
      already = already[:-1]
    except:
      print(ans)
      break
  if sorted(already) == goal:
    ans += 1
    now = already[-2]
    last = raw[now].index(already[-1])+1
    already = already[:-1]
  #print(now,already,last)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
tbl=[[0]*(N+1) for _ in range(N+1)]
for i in range(M):
  a,b=map(int,input().split())
  tbl[a][b]=1
  tbl[b][a]=1            # グラフの行列を用いた表現
def dfs(s,visited):
  if len(visited)==N:
    return 1
  
  ans=0
  for i in range(1,N+1):
    if i==s: continue     # 自己閉路は関係ない
    if tbl[s][i]==1 and (i not in visited):
      visited.append(i)
      ans+=dfs(i,visited)
      visited.pop() #深さ優先探索を考えているから
  return ans 

answer=dfs(1,[1,])
print(answer)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
tbl=[[0]*(N+1) for _ in range(N+1)]
for i in range(M):
  a,b=map(int,input().split())
  tbl[a][b]=1
  tbl[b][a]=1            # グラフの行列を用いた表現
def dfs(s,visited):
  if len(visited)==N:
    return 1
  
  ans=0
  for i in range(1,N+1):
    if i==s: continue
    if tbl[s][i]==1 and (i not in visited):
      visited.append(i)
      ans+=dfs(i,visited)
      visited.pop()
  return ans 

answer=dfs(1,[1,])
print(answer)

Submission status: Accepted

Solution code:
N, M = [int(v) for v in input().split()]
tbl = [[0] * (N + 1) for _ in range(N + 1)]


def dfs(v, visited):
    if len(visited) == N:
        return 1

    ans = 0
    for i in range(1, N + 1):
        if i == v: continue
        if tbl[i][v] == 1 and i not in visited:
            visited.append(i)
            ans += dfs(i, visited)
            visited.pop()
    return ans


for _ in range(M):
    a, b = [int(v) for v in input().split()]
    tbl[a][b] = 1
    tbl[b][a] = 1

paths = [1, ]
print(dfs(1, paths))

Submission status: Accepted

Solution code:
N, M = [int(v) for v in input().split()]
tbl = [[0] * (N + 1) for _ in range(N+1)]
for _ in range(M):
    a, b = [int(v) for v in input().split()]
    tbl[a][b] = 1
    tbl[b][a] = 1

ans = 0
paths = [[1, ]]
while paths:
    p = paths.pop()

    for i in range(1, N + 1):
        if p[-1] == i: continue
        if tbl[p[-1]][i] and i not in p:
            np = p + [i]
            if len(np) == N:
                ans += 1
            paths.append(np)
print(ans)

Submission status: Accepted

Solution code:
graph=[[False for i in range(8)]for j in range(8)]
def dfs(x,N,visted):
 all=True
 for i in range(N):
  if(visted[i]==False):
    all=False
 if all==True:
  return 1

 ret=0
 for i in range(N):
   if graph[x][i]==False:
    continue
   if visted[i]==True:
    continue
   visted[i]=True
   ret=ret+dfs(i,N,visted)
   visted[i]=False
  
 return ret

N,M=map(int,input().split())
for i in range(M):   
  x,y=map(int,input().split())
  graph[x-1][y-1]=True
  graph[y-1][x-1]=True
visted=[False for i in range(N)]
visted[0]=True
print(dfs(0,N,visted))

Submission status: Accepted

Solution code:
from itertools import permutations

n,m = map(int,input().split(' '))
choices = permutations(range(1,n))
nords = [[]for _ in range(n)]
for i in range(m):
    a, b = map(lambda x : int(x)-1,input().split(" "))
    nords[a].append(b)
    nords[b].append(a)


ans = 0
for choice in choices:
    row = list(choice)
    row.insert(0,0)
    for i,nownord in enumerate(row):
        if i== n - 1 :
            ans += 1
            break
        nextnord = row[i+1]
        if not nextnord in nords[nownord]:
            break
            
            
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
N, M = map(int, input().split())
table = [[] for i in range(N)]
for i in range(M):
  a,b = map(int, input().split())
  a -= 1
  b -= 1
  table[a].append(b)
  table[b].append(a)
  
numbers = [i for i in range(1,N)]
P = list(permutations(numbers,N-1))
ans = 0

for p in P:
  if p[0] in table[0]:
    for i in range(N-2):
      if p[i+1] not in table[p[i]]:
        break
    else:
      ans += 1  
print(ans)

Submission status: Accepted

Solution code:
def find(n, N, E, visited):
    visited = visited | {n}
    if len(visited) == N:
        return 1
    cnt = 0
    for e in E[n]:
        if e not in visited:
            cnt += find(e, N, E, visited)
    return cnt

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

for i in range(M):
    x, y = [int(x) for x in input().split()]
    E[x] = E.get(x, set()) | {y}
    E[y] = E.get(y, set()) | {x}

print(find(1, N, E, {1}))

Submission status: Accepted

Solution code:
import itertools
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
cnt = 0
for each in itertools.permutations(range(N)):
    if each[0] != 0:
        break
    factor = 1
    for i in range(N-1):
        factor *= adj_matrix[each[i]][each[i+1]]
    cnt += factor
print(cnt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, fractions, itertools


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):

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

    def dfs(v):
        if all(visited):
            return 1
        else:
            counter = 0
            for g in G[v]:
                if visited[g]:
                    continue
                visited[g] = 1
                counter += dfs(g)
                visited[g] = 0
            return counter
    print(dfs(0))
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]" 
    b = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, M, a, b)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def main():
    from itertools import permutations

    n, m = map(int, input().split())
    graph = [[0 for __ in range(n)] for _ in range(n)]
    ans = 0

    for i in range(m):
        ai, bi = map(lambda x: int(x) - 1, input().split())
        graph[ai][bi] = 1
        graph[bi][ai] = 1

    for j in list(permutations(range(n))):
        count = 0

        if j[0] == 0:
            for k in range(n - 1):
                _from = j[k]
                _to = j[k + 1]

                if graph[_from][_to] == 1:
                    count += 1

            if count == n - 1:
                ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M = map(int, input().strip().split(' '))
graph_dict = {}
for _ in range(M):
  a,b = map(int, input().strip().split(' '))
  if a in graph_dict:
    graph_dict[a].add(b)
  else:
    graph_dict[a] = {b}
  if b in graph_dict:
    graph_dict[b].add(a)
  else:
    graph_dict[b] = {a}

def search(now, visited):
  #print(now, visited)
  if len(visited)+1 == N:
    return 1
  if len(graph_dict[now]-visited) == 0:
    return 0
  return sum(search(n, visited|{now}) for n in graph_dict[now]-visited)
  

print(search(1, set()))

Submission status: Accepted

Solution code:
import itertools

n, m = map(int, input().split())
edge = zeros = [ [0]*n for _ in range(n) ]

for i in range(m):
    s, e = map(int, input().split())
    s -= 1
    e -= 1
    edge[s][e] = 1
    edge[e][s] = 1
    
result = 0

cands= list(itertools.permutations(range(1, n)))

def search(cand):
    cand = [0].extend(cand)
    for i in range(1, n):
        if edge[i-1][i] == 0:
            return False
    return True
for cand in cands:
    result += search(cand)
    
result = 0

cands= list(itertools.permutations(range(1, n)))

def search(cand):
    cand = list(cand)
    cand.insert(0, 0)
    for i in range(1, n):
        if edge[cand[i-1]][cand[i]] == 0:
            return False
    return True
for cand in cands:
    result += search(cand)
    
print(result)

Submission status: Accepted

Solution code:
def num_paths(trail, num_all_nodes, edges):
    if len(trail) == num_all_nodes:
        return 1

    count = 0
    for dest in edges[trail[len(trail)-1]]:
        if dest in trail:
            continue
        count += num_paths(trail + [dest], num_all_nodes, edges)
    return count


def main():
    n, m = [int(x) for x in input().split()]
    edges = [set() for i in range(n)]
    for i in range(m):
        a, b = [int(x) - 1 for x in input().split()]
        edges[a].add(b)
        edges[b].add(a)
    print(num_paths([0], n, edges))


main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
distinations = [[] for _ in range(N+1)]
for _ in range(M):
  _to, _from = map(int, input().split())
  distinations[_to].append(_from)
  distinations[_from].append(_to)
firsts = distinations[1]
stack = []
for _first in firsts:
  stack.append((_first, 1))
cnt = 1
ans = 0
path = [1]
while len(stack) > 0:
  dist = stack.pop()
  path = path[:dist[1]]
  if dist[0] in path:
    continue
  path += [dist[0]]
  cnt = dist[1] + 1
  if cnt == N:
    ans += 1
    continue
  for node in distinations[dist[0]]:
    stack.append((node, cnt))
print(ans)

Submission status: Accepted

Solution code:
import sys
from sys import stdin
sys.setrecursionlimit(10**7)

def dfs(v, cnt):
    if cnt >= N-1:
        return 1
    seen[v] = True

    ret = 0
    for next_v in graph[v]:
        if seen[next_v]:
            continue
        ret += dfs(next_v, cnt+1)
    seen[v] = False
    return ret

if __name__ == "__main__":
    N, M = [int(_) for _ in stdin.readline().rstrip().split()]
    graph = [[] for _ in range(N)]
    seen = [False]*N
    for i in range(M):
        a, b = [int(_) for _ in stdin.readline().rstrip().split()]
        a, b = a-1, b-1
        graph[a].append(b)
        graph[b].append(a)
    print(dfs(0, 0))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(6000)

n_node, n_path = [int(x) for x in input().split()]

A = [[0]*2 for x in range(n_path)]

for i in range(n_path):
	A[i][0], A[i][1] = [int(x) for x in input().split()]



def serch(A, cur_node, old, n_node):
	
	ans = 0
		
	if len(old) == (n_node-1):
		return 1
	
	for i in range(len(A)):
		
		if cur_node == A[i][0] and not(A[i][1] in old):
			A_copy = A.copy()
			A_copy.pop(i)
			old_copy = old.copy()
			old_copy.append(cur_node)
			ans += serch(A_copy, A[i][1], old_copy, n_node)
		
		elif cur_node == A[i][1] and not(A[i][0] in old):
			A_copy = A.copy()
			A_copy.pop(i)
			old_copy = old.copy()
			old_copy.append(cur_node)
			ans += serch(A_copy, A[i][0], old_copy, n_node)
	return ans

print(serch(A, 1, [], n_node))

Submission status: Accepted

Solution code:
def dfs(i, P):
    if len(P) == N:
        return 1
    c = 0
    for j, v in enumerate(G[i]):
        if j in P or v != 1:
            continue
        c += dfs(j, P + [j])
    return c


N, M = map(int, input().split())
G = [[0] * N for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a][b] = 1
    G[b][a] = 1
ans = 0
for i, v in enumerate(G[0]):
    if v == 1:
        ans += dfs(i, [0, i])
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

ab_list = []

for _ in range(0, m):
    a, b = list(map(int, input().split()))
    ab_list.append((a, b))
    ab_list.append((b, a))

# 全探索で解く場合
l = range(1, n+1)
count = 0
roots = [v for v in itertools.permutations(l, n) if v[0] == 1]

for v in roots:
    is_ok = True
    for i, _ in enumerate(list(v)[:-1]):
        # 探索対象となるエッジ
        target_edge = (list(v)[i], list(v)[i+1])
        if (target_edge not in ab_list):
            is_ok = False

    if is_ok:
        count += 1

print(count)

Submission status: Accepted

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

al_vis = [False for _ in range(N)]
al_vis[0] = True
def dfs(v, visited, cnt):
  if cnt == N-1:
    return 1
  ret = 0
  for i in range(N):
    if graph_ex[v][i] == 1 and visited[i] == False:
      visited[i] = True
      ret += dfs(i, visited, cnt+1)
      visited[i] = False
  return ret
ret = dfs(0, al_vis, 0)
print(ret)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
 
if M == 0:
    print(0)
    exit()
    
es = [[] for i in range(M+1)]
for i in range(M):
    a, b = map(int, input().split())
    a,b = a-1, b-1
    es[a].append(b)
    es[b].append(a)

def dfs(v, visited, es, cnt):
 
    #print("--------------")
    #print((v, visited, cnt))
 
    if cnt == N-1:
        return 1
    ret = 0
    for i in es[v]:
        if visited[i] == True:
            continue
 
        visited[i] = True
        ret += dfs(i, visited, es, cnt+1)
        visited[i] = False
 
    return ret
 
visited = [False] * N
visited[0] = True
 
ans = dfs(0,visited,es,0)
print(ans)

Submission status: Accepted

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

if M == 0:
    print(0)
    exit()

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

def dfs(v, visited, es, cnt):

    #print("--------------")
    #print((v, visited, cnt))

    if cnt == N-1:
        return 1
    ret = 0
    for i in es[v]:
        if visited[i] == True:
            continue

        visited[i] = True
        ret += dfs(i, visited, es, cnt+1)
        visited[i] = False

    return ret

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

ans = dfs(0,visited,es,0)
print(ans)

Submission status: Accepted

Solution code:
def dfs(s, n, 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[s][i]: continue
        if visited[i]: continue
        visited[i] = True
        ret += dfs(i, n, visited)
        visited[i] = False

    return ret


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

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

print(dfs(0, n, visited))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
# N-1辺表示をグラフ表示に
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)

def dfs(p, now, ans):
    now.append(p)
    if len(now) == N:
        ans += 1
        return ans
    allchecked = True
    for q in graph[p]:
        new = now[:]
        if not q in new:
            allchecked = False
            ans = dfs(q, new, ans)
    if allchecked:
        now.pop()
    return ans

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

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
s = [[]for i in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    s[a-1].append(b-1)
    s[b-1].append(a-1)
def func(x,n):
    if n == []:
        return 1
    r = 0
    for i in range(len(n)):
        if n[i] in s[x]:
            hoge = n.copy()
            a = hoge.pop(i)
            r += func(a,hoge)
    return r

print(func(0,list(range(1,N))))

Submission status: Accepted

Solution code:
import sys
import copy
from collections import deque

count = 0
n, m = (int(x) for x in sys.stdin.readline().split())
a_b_list = [[int(x) for x in sys.stdin.readline().split()] for y in range(m)]
# 始点が1のパスをキューに入れる
q = deque([])
for i in a_b_list:
    if i[0] != 1 and i[1] != 1:
        continue
    if i[0] == 1:
        q.append([1, i[1]])
    if i[1] == 1:
        q.append([1, i[0]])
#  幅優先探索(?)
while len(q) > 0:
    path = q.popleft()
    if len(path) == n:
        count += 1
        continue
    q_q = deque([i for i in range(2, n + 1) if i not in path])
    while len(q_q) > 0:
        destination = q_q.popleft()
        if [path[-1], destination] in a_b_list or [destination, path[-1]] in a_b_list:
            new_path = copy.copy(path)
            new_path.append(destination)
            q.append(new_path)
print(count)