Problem:


Score : 300 points

Problem Statement

You are given an undirected unweighted graph with N vertices and M edges that contains neither self-loops nor double edges.

Here, a self-loop is an edge where a_i = b_i (1≤i≤M), and double edges are two edges where (a_i,b_i)=(a_j,b_j) or (a_i,b_i)=(b_j,a_j) (1≤i<j≤M).

How many different paths start from vertex 1 and visit all the vertices exactly once?

Here, the endpoints of a path are considered visited.  

For example, let us assume that the following undirected graph shown in Figure 1 is given.

Figure 1: an example of an undirected graph

The following path shown in Figure 2 satisfies the condition.

Figure 2: an example of a path that satisfies the condition

However, the following path shown in Figure 3 does not satisfy the condition, because it does not visit all the vertices.

Figure 3: an example of a path that does not satisfy the condition

Neither the following path shown in Figure 4, because it does not start from vertex 1.

Figure 4: another example of a path that does not satisfy the condition

Constraints

2≦N≦8 

0≦M≦N(N-1)/2 

1≦a_i<b_i≦N 

The given graph contains neither self-loops nor double edges.

Input

The input is given from Standard Input in the following format:

N M  
a_1 b_1  
a_2 b_2
:  
a_M b_M  

Output

Print the number of the different paths that start from vertex 1 and visit all the vertices exactly once.

Sample Input 1

3 3
1 2
1 3
2 3

Sample Output 1

2

The given graph is shown in the following figure:

The following two paths satisfy the condition:

Sample Input 2

7 7
1 3
2 7
3 4
4 5
4 6
5 6
6 7

Sample Output 2

1

This test case is the same as the one described in the problem statement.



Sample input:
3 3
1 2
1 3
2 3


Sample output:
2

Submission status: Accepted

Solution code:
import sys
import itertools

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

nextList = [set() for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    nextList[a].add(b)
    nextList[b].add(a)

count = 0

nodes = range(2, n+1)
for v in itertools.permutations(nodes, n-1):
    now = 1
    error = False
    for i in v:
        if not i in nextList[now]:
            error = True
            break
        now = i
    if error != True:
        count += 1

print(count)

Submission status: Accepted

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

visited = [0] * n
def dfs(v, p):
    if sum(visited) == n:
        return 1
    res = 0
    for u in edge[v]:
        if u != p and visited[u] == 0:
            visited[u] = 1
            res += dfs(u, v)
            visited[u] = 0
    return res

visited[0] = 1
ans = dfs(0, -1)

print(ans)

Submission status: Accepted

Solution code:
N, M = [int(x) for x in input().split()]
P = [[False] * N for m in range(N)]
dict={}
for m in range(M):
  a, b = [int(x) for x in input().split()]
  P[a-1][b-1] = True
  P[b-1][a-1] = True

def dp(x, past):
  past[x] = True
  if (x, tuple(past)) in dict:
    return dict[(x, tuple(past))]
  if False not in past:
    return 1
  ret = 0
  for i,p in enumerate(P[x]):
    if not p or x == i or past[i]:
      continue
    else:
      ret += dp(i, past[:])
  dict[(x, tuple(past))] = ret
  return ret

if M < N - 1:
  print(0)
else:
  print(dp(0, [False] * N))

Submission status: Accepted

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

def dfs(v, visited):
    if len(visited) == N:
        return 1
    ret = 0
    for i in range(1,N+1):
        if graph[v][i] and not i in visited:
            visited[i] = True
            ret += dfs(i, visited)
            visited.pop(i)
    return ret

print(dfs(1, {1: True}))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
def main():
  n, m = map(int, input().split())
  ab = [list(map(lambda x:int(x)-1, input().split())) for _ in range(m)]
  ad_list = make_ad_list(n, ab)
  global searched
  global ans
  searched = [0 for _ in range(n)]
  searched[0] = 1
  ans = 0
  dfs(0, n, ad_list)
  print(ans)

def make_ad_list(n, l):
  ad_list = [[] for _ in range(n)]
  for a, b in l:
    ad_list[a] += [b]
    ad_list[b] += [a]

  return ad_list

def dfs(v, n, ad_list):
  global searched
  global ans
  if sum(searched) == n:
    ans += 1
    return
  for u in ad_list[v]:
    if searched[u] == 0:
      searched[u] = 1
      dfs(u, n, ad_list)
      searched[u] = 0
  return 

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import numpy as np

def bfs(s,reached):
    ret = 0
    for i in grid[s]:
        if all(reached)==True:
            return 1
        if reached[i]==True:
            continue
        else:
            reached[i]=True
            ret += bfs(i,reached)
            reached[i]=False
    return ret

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

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

#リーチドを示す
reached = []
for _ in range(N):
    reached.append(False)

#視点
reached[0]=True
s=0
ret = bfs(s,reached)
print(ret)

Submission status: Accepted

Solution code:
"""
# 標準入力取得
## 文字列
 = sys.stdin.readline().rstrip()
 = list(sys.stdin.readline().rstrip())

## 数値
 = int(sys.stdin.readline())
 = map(int, sys.stdin.readline().split())
 = list(map(int, sys.stdin.readline().split()))
 = [list(map(int,list(sys.stdin.readline().split()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# 0埋め, 小数点出力桁指定時のときの出力
a = 100
b = 0.987654321
print("{0:06d}-{1:6f}".format(a,b))
000100-0.987654

# 文字列をリストに格納
char_list = list("abcd") # ["a","b","c","d"]
"""

import math
import sys
import itertools
import queue
from fractions import gcd

def lcm(a, b):
    return a * b // gcd(a, b)

mod = 1000000007

if __name__ == "__main__":
    n,m = map(int, sys.stdin.readline().split())
    mat = [[0 for i in range(n)]for j in range(n)]

    #隣接行列
    for i in range(n):
        mat[i][i] = 0
    #辺に１を入れる
    for i in range(m):
        a,b = map(int, input().split())
        mat[a-1][b-1] = mat[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 *= mat[each[i]][each[i+1]]
        cnt += factor
    print(cnt)

    #dfs（深さ優先探索）

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
check=[[False]*n for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    check[a-1][b-1]=True
    check[b-1][a-1]=True
l=[i for i in range(1,n)]
import itertools
count=0
for order in itertools.permutations(l,n-1):
    order=[0]+list(order)
    for i in range(n-1):
        if check[order[i]][order[i+1]]:
            pass
        else:
            break
    else:
        count+=1
print(count)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[None]*m
b=[None]*m
edge=[[] for _ in range(n)]
for i in range(m):
  a0,b0=map(int,input().split())
  a[i]=a0-1
  b[i]=b0-1
  edge[a0-1]+=[b0-1]
  edge[b0-1]+=[a0-1]

def dfs(v,nodes):
  u_nodes=nodes[:]
  if v not in u_nodes:
    return 0
  u_nodes.remove(v)
  if len(set(u_nodes) & set(edge[v]))==0:
    return 0
  if len(u_nodes)==1:
    return 1
  ret=0
  for i in set(u_nodes) & set(edge[v]):
    ret+=dfs(i,u_nodes)
  return ret

nodes=[i for i in range(n)]
print(dfs(0,nodes))

Submission status: Accepted

Solution code:
import itertools
N,M=map(int,input().split())
edges = {tuple(map(int,input().split())) for _ in range(M)}
paths = itertools.permutations(range(2,N+1))
ans = 0
for path in paths:
    count = 0
    path = [1]+list(path)
    for edge in zip(path[:-1],path[1:]):
        count += tuple(sorted(edge)) in edges
    ans += count==N-1
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from copy import deepcopy
from collections import deque, defaultdict
from operator import mul
from functools import reduce
sys.setrecursionlimit(20000000)

count = 0


def main():
    N, M = map(int, input().split())
    info = [list(map(int, input().split())) for _ in range(M)]
    g = deque(list())

    def visit(n, memo):
        n_memo = deepcopy(memo)
        n_memo.append(n)
        children = g[n]

        if len(n_memo) == N:
            global count
            count += 1

        for child in children:
            if child not in n_memo:
                visit(child, n_memo)

    for _ in range(N):
        g.append([])

    for p, c in info:
        g[p-1].append(c-1)
        g[c-1].append(p-1)

    visit(0, [])

    print(count)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(m)]
visited = [False]*n
counter =0

def v_list(value, vector):
    result = []
    for i in range(len(vector)):
        if value in vector[i]:
            result.append(vector[i][0])
            result.append(vector[i][1])
    while value in result:
        result.remove(value)
    return result


def DFS(x):
    next_x = v_list(x, c)
    all_visited = True
    for i in range(n):
        if not visited[i]:
            all_visited = False

    if all_visited:
        global counter
        counter +=1
        return

    for i in next_x:
        if not visited[i-1]:
            visited[i-1] = True
            DFS(i)
            visited[i-1] = False

visited[0] = True
DFS(1)
print(counter)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

ans = 0

def f(now, v):
    global ans
    v |= (1 << now)
    for to in edge[now]:
        if not (v & (1<<to)):
            f(to, v)
    if bin(v).count("1") == N:
        ans += 1

f(0, 0)

print(ans)

Submission status: Accepted

Solution code:
n , m = map(int , input().split())
edge = [[] for _ in range(n) ]
#print(edge)
for _ in range(m):
    a , b = map(int , input().split())
    a -= 1 ; b -= 1
    edge[a].append(b)
    edge[b].append(a)
#print(edge)

def DFS(s):
    global visited
    #ret=1 if all(visited) else 0
    if all(visited):
        ret = 1
    else:
        ret = 0
    for e in edge[s]:
        #print("e",e)
        if visited[e] == True:
            continue
        visited[e] = True
        ret += DFS(e)
        visited[e] = False
    return ret

ans = 0
visited = [False] * n
visited[0] = True
ans += DFS(0)
print(ans)

Submission status: Accepted

Solution code:
# 2019/08/27

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

def dfs(s):
    global visited
    ret=1 if all(visited) else 0
    for e in edge[s]:
        if visited[e]==True:continue
        visited[e]=True
        ret+=dfs(e)
        visited[e]=False
    return ret

ans=0
visited=[False]*n
visited[0]=True
ans+=dfs(0)

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

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

abs = [list(map(int,input().split())) for _ in range(1, M+1)]
          
p_paths = list(permutations(list(range(2,N+1)), N-1))


cnt=0

for p_path in p_paths:
    p_path = list(p_path)
    p_path.insert(0, 1)
    c=0
    for i in range(len(p_path)-1):
        for ab in abs:

            if ab == list([p_path[i], p_path[i+1]]) or ab == list([p_path[i+1], p_path[i]]):
                c+=1
                break
        if c==len(p_path)-1:
            cnt=cnt+1
print(cnt)

Submission status: Accepted

Solution code:
import numpy as np
n,m=map(int,input().split())
info=np.zeros((n,n),dtype=int)

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

  
def f(v,visit):
  cnt=0
  ff=1
  for i in range(n):
    if visit[i]==0:
      ff=0
  if ff==1:
    return 1
  
  for i in range(n):
    if info[v][i]==1 and visit[i]==0:
      visit[i]=1
      cnt+=f(i,visit)
      visit[i]=0
    
  return cnt
  
visit=np.zeros(n,dtype=int)
visit[0]=1

print(f(0,visit))

Submission status: Accepted

Solution code:
import itertools
n,m=map(int,input().split())
edges={tuple(sorted(map(int,input().split()))) for i 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:
import bisect
n,m = map(int,input().split())

g = [[ ] for i in range(n+1)]

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

    #print(bisect.bisect_left(g[a],b))
    #g[a][] = b
    #g[a].append(b)
    #g[b].append(a)

#g[4].sort()
    
ans = 0

def dfs(x,check):
    #print(check,x)
    ans = 0
    if not False in check:
        #print(ans)
        return 1
        #check[x] = 0
        #print(x)
    #print(check)
    for i in g[x]:
        if check[i] == True:
            continue
        #print(i,check)
        check[i] = True
        ans += dfs(i,check)
        check[i] = False
    
    return ans
    
check = [False] * (n+1)
check[0] = True
check[1] = True

print(dfs(1,check))

Submission status: Accepted

Solution code:
import itertools

N, M = map(int,input().split())
edges = {tuple(sorted(map(int,input().split()))) for i in range(M)}
ans = 0
for i in itertools.permutations(range(2,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:
import itertools
n, m = map(int, input().split())
adj_matrix = [[0] * n for _ in range(n)]

for _ 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
    flag = 1
    for i in range(n-1):
        flag *= adj_matrix[each[i]][each[i+1]]
    cnt += flag
print(cnt)

Submission status: Accepted

Solution code:
import itertools

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

path = [[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

for i in itertools.permutations(range(n), n):
    if i[0]==0:
        for j in range(n-1):
            if not path[i[j]][i[j+1]]:
                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())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

s = 0 
visited = [False]*(N)
visited[0] = True
def search(s,visited):
    if sum(visited) == N :
        return 1
    else :
        ret = 0 
        for i in graph[s]:
            if visited[i] :
                continue
            visited[i] = True 
            ret += search(i,visited)
            visited[i] = False
    return ret
print(search(s,visited))

Submission status: Accepted

Solution code:
n,m = list(map(int,input().split()))
from collections import defaultdict
 
dc = defaultdict(list)
for i in range(m):
    a,b = list(map(int,input().split()))
    dc[a].append(b)
    dc[b].append(a)

ans = 0
from itertools import permutations
comb = list(permutations(range(2,n+1),n-1))
for c in comb:
    flag = True
    targets = list(c)
    # print(c)
    if not 1 in dc[targets[0]]:
        flag = False
    for i in range(len(targets)-1):
        a,b = targets[i],targets[i+1]
        if not b in dc[a]:
            flag = False
            break
    if flag:
        # print(c," is ok")
        ans += 1

print(ans)

Submission status: Accepted

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

def rec(v, visited):
    if len(visited) == N:
        return 1
    ret = 0
    for nxt in edge_from[v]:
        if nxt not in visited:
            ret += rec(nxt, [x for x in visited]+[nxt])
    return ret
print(rec(0, [0]))

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

# https://atcoder.jp/contests/abc054/tasks/abc054_c

# N = 頂点の数(= 数字の数)
# M = 辺の数(= aの行数)

N, M = map(int, input().split())
graph = [ [0 for _ in range(N)] for _ in range(N) ]
visited = [False] * N

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

#print(graph)

# u は 0-index
def dfs(u):
    if False in visited:
        pass
    else:
        return 1

    count = 0
    for i in range(N):
        if graph[u][i] == False: continue
        if visited[i]: continue

        visited[i] = True
        count += dfs(i)
        visited[i] = False

    return count

visited[0] = True
count = dfs(0)
print(count)

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

# N = 頂点の数(= 数字の数)
# M = 辺の数(= aの行数)

N, M = map(int, input().split())
graph = [ [0 for _ in range(N)] for _ in range(N) ]
visited = [False] * N

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

#print(graph)

# u は 0-index
def dfs(u):
    visited[u] = True
    if False in visited:
        pass
    else:
        return 1

    count = 0
    for i in range(N):
        if graph[u][i] == False: continue
        if visited[i]: continue

        visited[i] = True
        count += dfs(i)
        visited[i] = False

    return count

count = dfs(0)
print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

dp = defaultdict(int)
dp[(1, 0)] = 1
for S in range(1 << N):
    for v in range(N):
        if S & (1 << v) == 0:
            continue
        sub = S ^ (1 << v)
        for u in adjacent[v]:
            if sub & (1 << u):
                dp[(S, v)] += dp[(sub, u)]
print(sum(dp[((1 << N) - 1, u)] for u in range(1, N)))

Submission status: Accepted

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


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

    ans = 0
    for u in adjacent[v]:
        if visited >> u & 1 == 1:
            continue
        visited += 1 << u
        ans += dfs(visited, u)
        visited -= 1 << u
    return ans


print(dfs(1, 0))

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)

    cur = [[1, set([1])]]
    for _ in range(N-1):
        temp = []
        for a, visited in cur:
            for b in graph[a]:
                if b not in visited:
                    temp.append([b, visited | {b}])
        cur = temp
    return len(cur)


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

Submission status: Accepted

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


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

used = [False for i in range(n)]
perm = [0 for i in range(n)]
count = 0
#print(to)
def permutation(pos, last):
    global count
    if pos == last:
        #処理
        if perm[0] == 0:
            connect = False
            count_check = True
            #print(perm)
            for i in range(1, n):
                for j in to[perm[i - 1]]:
                    if perm[i] == j:
                        connect = True
                if not connect:
                    count_check = False
                    break
                else:
                    connect = False
            if count_check:
                count += 1
        else:
            return
    for i in range(last):
        if not used[i]:
            perm[pos] = i
            used[i] = True
            permutation(pos + 1, last)
            used[i] = False
    return


permutation(0, n)
print(count)

Submission status: Accepted

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

for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    e[u].append(v)
    e[v].append(u)

for route in itertools.permutations(range(1, n), n - 1):

    visited = [False] * n
    visited[0] = True
    route = list(route)
    route.insert(0, 0)
    for i in range(1, n):
        now = route[i - 1]
        nxt = route[i]
        if str(nxt) in str(e[now]) and not(visited[nxt]):
            visited[nxt] = True
            if i == n - 1:
                ans += 1
        else:
            break

print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import permutations
INPUT = lambda: sys.stdin.readline().rstrip()
MAP = lambda: map(int, INPUT().split())
sys.setrecursionlimit(10 ** 9)


def main():
    N, M = MAP()
    edges = set()

    for _ in range(M):
        u, v = MAP()
        edges |= {(u-1, v-1), (v-1, u-1)}

    print(sum(all((u, v) in edges for u, v in zip(p, p[1:])) for p in permutations(range(N)) if p[0] == 0))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
N,M=map(int,input().split())
edges={tuple(sorted(map(int,input().split()))) for i 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:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
   
N, M = LI()
mat = [[0] * N for _ in range(N)]
for _ in range(M):
    a, b = LI_()
    mat[a][b] = 1
    mat[b][a] = 1 
seen = [0 for _ in range(N)]
ans = 0

def dfs(i, count):
    global ans
    import pdb
    # pdb.set_trace()
    if count == N:
        return True

    for j, reachable in enumerate(mat[i]):
        if reachable and not seen[j]:
            seen[j] = 1
            if dfs(j, count + 1):
                ans += 1
            seen[j] = 0

    return False

def main():
    seen[0] = 1
    dfs(0, 1)
    print(ans)
main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque

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

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

q = deque([])
q.append(0)

ans = 0
def dfs(n, q):
  global ans
  q.append(n)
  if len(q) == N:
    ans += 1
  else:
    for b in D[n]:
      if b not in q:
        dfs(b, q)
        q.pop()

dfs(0, [])
print (ans)

Submission status: Accepted

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

his=[False]*N

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

def search(now,his,A):
    
    if all(his):
        return 1
    
    else:
        cnt=0
        for a in A:
            if now in a:
                nex=a[(a.index(now)+1)%2]
                if not his[nex]:
                    his[nex]=True
                    cnt+=search(nex,his,A)
                    his[nex]=False
       
        return cnt

his[0]=True
print(search(0,his,A))

Submission status: Accepted

Solution code:
from collections import deque

N, M = list(map(int, input().split()))
G = [[] for _ in range(N)]
for _ in range(M):
  a, b = list(map(int, input().split()))
  G[a-1].append(b-1)
  G[b-1].append(a-1)
  
ans = 0
v = 0
s = 1
l = 1
q = deque()
q.append((v, s, l))

while q:
  v, s, l = q.popleft()
  if l == N:
    ans += 1
    continue
  for nv in G[v]:
    if s&(1<<nv) == 0:
      q.append((nv, s|(1<<nv), l+1))
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
E = [[] for i in range(N)]
for i in range(M):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  E[a].append(b)
  E[b].append(a)
r = 0
c = 0
s = 1
l = 1
q = [(c, s, l)]
while q:
  c, s, l = q.pop()
  if l == N:
    r += 1
    continue
  for n in E[c]:
    if s&(1<<n) == 0:
      q.append((n, s|(1<<n), l+1))
print(r)

Submission status: Accepted

Solution code:
from collections import defaultdict

def dfs(res, depth, path, adj_list, visited):
    if path in visited:
        return
    elif depth == 1:
        res[0]+=1
        return
    for node in adj_list[path]:
        dfs(res, depth-1, node, adj_list, visited+[path])  

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

res = [0]
for node in adj_list[1]:
    dfs(res, N-1, node, adj_list, [1])
print(res[0])

Submission status: Accepted

Solution code:
(n, m) = map(int, input().split())
graph = {}
for _ in range(m):
    (a, b) = map(int, input().split())
    if not a in graph:
        graph[a] = []
    graph[a].append(b)
    if not b in graph:
        graph[b] = []
    graph[b].append(a)
is_visited = [False for _ in range(len(graph.keys()))]


def dfs(count, graph, is_visited, v_id):
    if all(is_visited):
        return 1
    sum = 0
    for neighbor in graph[v_id]:
        if is_visited[neighbor - 1]:
            continue
        is_visited[neighbor - 1] = True
        sum += dfs(count, graph, is_visited, neighbor)
        is_visited[neighbor - 1] = False
    return count + sum


count = 0
is_visited[0] = True
print(dfs(count, graph, is_visited, 1))

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
paths = {}
for i in range(1, N+1):
  paths[i]=set()
for i in range(M):
  a, b = map(int, input().split())
  paths[a].add(b)
  paths[b].add(a)

count = 0

def dfs(v, visited):
  global count
  if len(visited) == N:
    count += 1
    return
  for i in paths[v]:
    if i not in visited:
      visited.add(i)
      dfs(i, visited)
      visited.remove(i)
  return

pq = deque()
for i in paths[1]:
  pq.append(i)
  dfs(i, {1, i})
print(count)

Submission status: Accepted

Solution code:
import collections
N,M = list(map(int,input().split()))
tree = [[] for _ in range(N)]
for _ in range(M):
    u, v = map(int, input().split())
    tree[u - 1].append(v - 1)  ##無効グラフであるので
    tree[v - 1].append(u - 1)




def dfs(now,prev,visited):
    
    if sum(visited) == 0:
        return 1
    
    ret = 0
    
    for nxt in tree[now]:
        if nxt != prev and visited[nxt] == 1:
            visited[nxt] = 0
            ret += dfs(nxt,now,visited)
            visited[nxt] = 1
    return ret
            
visited = [1 for _ in range(N)]
visited[0] = 0
print(dfs(0,-1,visited))

Submission status: Accepted

Solution code:
def dfs(v):
    if len(set(visited)) == 1 and visited[0]:
        return 1
    count = 0
    for p in points[v]:
        if not visited[p]:
            visited[p] = True
            count += dfs(p)
            visited[p] = False
    else:
        return count


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

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

print(dfs(0))

Submission status: Accepted

Solution code:
# ABC054C - One-stroke Path
# graph theory
# an undirected unweighted graph is given
# -> count up paths which visit all the vertices exactly once
import sys
input = sys.stdin.readline

from itertools import permutations as perm


def main():
    N, M = tuple(map(int, input().split()))
    A = set(tuple(map(int, input().split())) for _ in range(M))
    ans = 0
    for path in perm(range(2, N + 1), N - 1):  # check all possible paths (O(N!))
        path = (1,) + path
        if all((i, j) in A or (j, i) in A for i, j in zip(path, path[1:])):
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

def saiki(matrix, fin_l, pos, count):
    for i in range(N):
        move = int(matrix[i, pos])
        if move == 1 and i!=pos and fin_l[i]==0:
            next_pos = i
            fin_l[i] = 1
            if 0 not in fin_l:
                count += 1
                fin_l[i] = 0
                continue
            count = saiki(matrix, fin_l, next_pos, count)
            fin_l[i] = 0

    return count

if __name__ == '__main__':


    N, M = map(int, input().split(' '))
    matrix = np.zeros((N, N))

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

    for i in range(N):
        matrix[i, i] = 1

    # 訪問済み 配列
    fin_l = [1]
    fin_l.extend([0]*(N-1))
    count = 0
    count = saiki(matrix, fin_l, 0, count)

    print(count)

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:
#%%
N, M = map(int, input().split())
a = [0] * M
b = [0] * M
for i in range(M):
    a[i], b[i] = map(int, input().split())

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

import itertools

l = list(itertools.permutations(range(1, N)))

ans = 0

for i in range(len(l)):
    check = 0
    last = 0
    for j in range(len(l[i])):
        if l[i][j] in path[last]:
            last = l[i][j]
            pass
        else:
            check = 1
    if check == 0:
        ans += 1
            
print(ans)