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 bisect
import copy
import heapq
import sys
import itertools
import math
import queue
from functools import lru_cache
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N, M = read_values()
    L = [set() for _ in range(N)]
    for _ in range(M):
        a, b = read_index()
        L[a].add(b)
        L[b].add(a)

    res = 0
    for T in itertools.permutations(range(1, N)):
        pre = 0
        for t in T:
            if t not in L[pre]:
                break
            pre = t
        else:
            res += 1

    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def dfs(n):
    global P
    seen[n] = 1
    for g in G[n]:
        if seen[g] == 0:
            dfs(g)
            seen[g] = 0
    if not 0 in seen:
        P += 1
P = 0
seen = [0] * N
dfs(0)
print(P)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import permutations

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

graph = defaultdict(list)

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

pattern = [x for x in permutations(range(1, n + 1)) if x[0] == 1]

ans = []
for p in pattern:
    tmp = []
    for i in range(n - 1):
        if p[i + 1] in graph[p[i]]:
            tmp.append(True)
        else:
            tmp.append(False)
    ans.append(all(tmp))

print(sum(ans))

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

ans = 0


def main():
    def dfs(u, visited):
        visited[u] = True
        cnt = 0

        for v in edge[u]:
            if not visited[v]:
                cnt += dfs(v, visited)
                visited[v] = False

        if visited.count(True) == n:
            return 1

        return cnt

    from collections import defaultdict
    n, m = map(int, readline().split())
    edge = defaultdict(list)

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

    ans = dfs(1, [False] * (n + 1))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
from collections import deque

n, m = map(int,input().split())
edge = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
    
ans = 0
for p in itertools.permutations([i+1 for i in range(n-1)]):
    pp = [0]+list(p)
    #print('pp',pp)
    now = pp[0]
    for i in range(1,n):
        if pp[i] in edge[now]:
            now = pp[i]
        else:
            break
    else:
        ans += 1
    
print(ans)

Submission status: Accepted

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

from itertools import permutations

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

edges = set()
for _ in range(M):
    a, b = map(int, input().split())
    edges.add((a,b))
    edges.add((b,a))



res = 0
for a in permutations(range(2,N+1),N-1):
    j = 1
    k = 0
    for i in a:
        if (j,i) in edges:
            k += 1
        if k == N-1:
            res += 1
        j = i

print(res)

Submission status: Accepted

Solution code:
import sys
import copy

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')

sys.setrecursionlimit(1000000)


ans = 0


def bfs(N, edge, v, search):

    search |= {v}

    global ans
    if len(search) == N:
        ans += 1
        return

    for e in edge[v]:
        if e not in search:
            bfs(N, edge, e, copy.copy(search))


def main():

    N, M = in_nn()

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

    for i in range(M):
        a, b = in_nn()
        a, b = a - 1, b - 1
        edge[a].append(b)
        edge[b].append(a)

    bfs(N, edge, 0, set())

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import copy

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')

sys.setrecursionlimit(1000000)


ans = 0


def bfs(N, edge, v, search):

    search |= {v}

    global ans
    if len(search) == N:
        ans += 1
        return

    for e in edge[v]:
        if e not in search:
            #print('test:{},{},{}'.format(e, v, search))
            bfs(N, edge, e, copy.copy(search))


def main():

    N, M = in_nn()

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

    for i in range(M):
        a, b = in_nn()
        a, b = a - 1, b - 1
        edge[a].append(b)
        edge[b].append(a)

    bfs(N, edge, 0, set())

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from networkx import*
(n,_),*t=map(str.split,open(0))
n=int(n)
print(sum(n==len(p)for i in range(n)for p in all_simple_paths(Graph(t),'1',str(i+1))))

Submission status: Accepted

Solution code:
from networkx import*
(n,_),*t=[[*map(int,t.split())]for t in open(0)]
print(sum(n==len(p)for i in range(n)for p in all_simple_paths(Graph(t),1,i+1)))

Submission status: Accepted

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

def check(l, edge):
    for i in range(1,len(l)):
        u = l[i-1]
        v = l[i]
        if v not in edges[u]:
            return False
    return True

ans = 0
for l in perm([i for i in range(n)]):
    if l[0] != 0: continue
    if check(l,edges):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools
from sys import stdin
input = stdin.readline


def main():
  N, M = list(map(int, input().split()))
  map_ = [[0]*(N+1) for _ in range(N+1)]
  for i in range(M):
    a, b = list(map(int, input().split()))
    map_[a][b] = 1
    map_[b][a] = 1

  def is_one_stroke(path):
    now = 1
    for i in range(len(path)):
      next_ = path[i]
      if not map_[now][next_]:
        return False
      now = next_
    return True

  perms = itertools.permutations(list(range(2, N+1)))
  num_path = 0
  for path in perms:
    if (is_one_stroke(path)):
      num_path += 1
  print(num_path)


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

Submission status: Accepted

Solution code:
from itertools import permutations

n, m = map(int, input().split())
L = [set() for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    L[a-1].add(b-1)
    L[b-1].add(a-1)
lst = [i for i in range(1, n)]
ans = 0
for v in permutations(lst, n-1):
    case = [0] + list(v)
    for i in range(n-1):
        next = case[i+1]
        if next not in L[case[i]]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

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

path = [[] for i in range(N)]

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

def dfs(now,depth):
	global cnt
	if depth == N: cnt+=1
	for new in path[now]:
		if vis[new] == 0:
			vis[new] = 1
			dfs(new,depth+1)
			vis[new] = 0

vis[0] = 1
dfs(0,1)
print(cnt)

Submission status: Accepted

Solution code:
import itertools as it

n,m=map(int,input().split())
path=[]
for i in range(m): path.append(list(map(int,input().split())))
ls=list(it.permutations(range(1,n+1)))
cnt=0
for l in ls:
    if l[0]!=1: break
    flag=1
    for i in range(n-1):
        if ([l[i],l[i+1]] not in path) and ([l[i+1],l[i]] not in path):
            flag=0
            break
    if flag: cnt+=1
print(cnt)

Submission status: Accepted

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

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

count = 0

def dfs(i, now, done):
    global count
    if i == N-1:
        count += 1
        return

    for j in ab[now]:
        if j not in done:
            dfs(i+1, j, done + [j])
    return

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

Submission status: Accepted

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

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

#print(a)

c = list(itertools.permutations(range(1, n)))
len_c = len(c)

#print(c)
ans = 0
for i in range(len_c):
    now = 0
    check = True
    for j in range(n - 1):
        if not c[i][j] in a[now]:
            check = False
        now = c[i][j]
    if check:
        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):#N!
    if i[0] == 0:
        for j in range(n):
            if j == n - 1:
                ans += 1
                break
            if not path[i[j]][i[j + 1]]:
                break

print(ans)

Submission status: Accepted

Solution code:
import itertools
(n,_),*a= [[*map(int,i.split())] for i in open(0)]
p=[[1] + list(i) for i in itertools.permutations(range(2,n+1),n-1)]
c = 0
for i in p:
    for j in range(n-1):
        if sorted([i[j],i[j+1]]) not in a:
            break
    else:
        c+=1
print(c)

Submission status: Accepted

Solution code:
from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    """
    https://qiita.com/drken/items/4a7869c5e304883f539b#3-3-dfs-%E3%81%AE%E5%86%8D%E5%B8%B0%E9%96%A2%E6%95%B0%E3%82%92%E7%94%A8%E3%81%84%E3%81%9F%E5%AE%9F%E8%A3%85
    cf. https://atcoder.jp/contests/abc138/submissions/13273052
    """

    N, M = map(int, input().split())  # 頂点数，辺数
    # グラフ入力受取 (ここでは無向グラフを想定)
    G = [[] for _ in range(N)]
    for i in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)
    ans = 0

    for i in permutations(range(N)):
        flag = True
        if i[0] != 0:
            continue
        nn=0
        for j in range(N-1):
            if i[j+1] not in G[nn]:
                flag = False
            nn=i[j+1]
        if flag:
            ans += 1
    print(ans)


resolve()

Submission status: Accepted

Solution code:
import itertools

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)

lst = [i + 1 for i in range(n - 1)]
ans = 0
for step in itertools.permutations(lst):
    flag = True
    now = 0
    for i in range(n - 1):
        if step[i] in edge[now]:
            now = step[i]
        else:
            flag = False
            break
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

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

import itertools
def permutation_all(seq, choice):
    return list(itertools.permutations(seq, choice))

cond = [i for i in range(2,n+1)]
cond = permutation_all(cond, n-1)
for i in range(len(cond)):
    here = 1
    tar = cond[i]
    flag = True
    for j in range(n-1):
        if tar[j] not in edge[here]:
            flag= False
            break
        else:
            here = tar[j]
    if flag:
        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:
n,m=map(int,input().split())
ab = []
for _ in range(m):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  ab.append({a,b})
import itertools

cnt = 0
for v in itertools.permutations(range(1,n)):
  l = 0
  ok = True
  for v2 in v:
    if {l,v2} not in ab:
      ok = False
      break
    l = v2
  if ok:
    #print(v)
    cnt += 1
  
print(cnt)

Submission status: Accepted

Solution code:
import sys
import collections
INF = 10**18
ans = 0

def dfs2(now,edge,l,cnt):
    global ans
    if len(l) == n:
        ans+=1
        return
    visited[now] = True
    for v in edge[now]:
        if visited[v] == False:
            l.append(v)
            dfs2(v,edge,l,cnt)
            l.pop()
            visited[v] = False

if __name__ == "__main__":
    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)
    l = [0]
    visited = [False]*(n)
    dfs2(0,edge,l,0)
    print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

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

ans = 0
for p in permutations(range(1, N)):
    v = 0
    flag = True
    for nv in p:
        if nv not in G[v]:
            flag = False
            break
        v = nv
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
def main():
    N, M = map(int, input().split())
    l = [[0] * N for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        l[a][b] = 1
        l[b][a] = 1
    r = 0
    for x in permutations(range(1, N)):
        if l[0][x[0]] == 0:
            continue
        for i in range(N-2):
            if l[x[i]][x[i+1]] == 0:
                break
        else:
            r += 1
    return r
print(main())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

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)

visited = [False] * (n+1)
visited[0] = True
visited[1] = True
cnt = 0

def dfs(list):
    global cnt
    if not False in visited:
        cnt += 1
        return
    for i in list:
        if visited[i] == False:
            visited[i] = True
            dfs(g[i])
            visited[i] = False

dfs(g[1])
print(cnt)

Submission status: Accepted

Solution code:
from itertools import permutations

def main():
    N, M = map(int, input().split())
    G = [set() for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        G[a - 1].add(b - 1)
        G[b - 1].add(a - 1)
    r = 0
    for p in permutations(range(1, N)):
        f = 0
        for i in p:
            if i not in G[f]:
                break
            f = i
        else:
            r += 1
    return r

print(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):
    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:
def ser(visited,now):
  visited.append(now)
  if len(visited)==n:
    return 1
  cnt=0
  for i in bri[now]:
    if i not in visited:
      cnt+= ser(visited[:],i)
  return cnt

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

Submission status: Accepted

Solution code:
import copy
import sys
sys.setrecursionlimit(10**7)
N, M = map(int, input().split())
edges = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)
ans = 0
def dfs(start,path):
    next_path = copy.copy(path)
    global ans
    next_path.append(start)
    if len(next_path) == N:
        ans += 1
        return
    for i in edges[start]:
        if i not in next_path:
            dfs(i,next_path)
dfs(0,[])
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations


def main():
    n, m = map(int, input().split())

    path = [[False for _ in range(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

    res = 0
    perms = list(permutations(list(range(1, n)), n - 1))
    for p in perms:
        visited = 1
        prev = 0
        for now in p:
            if path[prev][now]:
                visited += 1
                prev = now
            else:
                break
        if visited == n:
            res += 1

    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import permutations
n , m = map(int,input().split())
route = [set() for i in range(n+1)]
for i in range(m):
    a , b = map(int,input().split())
    route[a].add(b)
    route[b].add(a)
ans = 0
p=[i + 2 for i in range(n-1)]
kouho = list(permutations(p))

for i in range(len(kouho)):
    now = 1
    flag = True
    for j in kouho[i]:
        if j in route[now]:
            now = j
        else:
            flag = False
            break
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

def solve():
    ret = 0
    stack = deque()
    stack.append([1, {1}])
    while stack:
        node, used = stack.popleft()
        if len(used) == N:
            ret += 1
            continue

        for n in neighbors[node]:
            if n in used:
                continue
            stack.append([n, used | {n}])

    print(ret)

if __name__ == "__main__":
    N, M = map(int, input().split())
    neighbors = [[] for _ in range(N + 1)]
    for _ in range(M):
        a, b = map(int, input().split())
        neighbors[a].append(b)
        neighbors[b].append(a)
    solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from itertools import permutations
n, m = map(int, input().split())
G = [[] for _ in [0] * -~n]
for _ in [0] * m:
    a, b = map(int, input().split())
    G[a] += b,
    G[b] += a,
ans = 0
for i in permutations(range(2, n + 1), n - 1):
    i = (1,) + i
    if all(i[j] in G[i[j + 1]] for j in range(n - 1)):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy
n, m, *AB = map(int, open(0).read().split())
graph = [[] for _ in range(n)]
for a, b in zip(AB[::2], AB[1::2]):
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

complete_paths = []
stack = [0]
paths = [[]]
c = 0
while stack:
    current_node = stack.pop()
    path = paths.pop()
    path.append(current_node)
    next_nodes = [n for n in graph[current_node] if n not in path]
    if next_nodes:
        for next_node in next_nodes:
            stack.append(next_node)
            paths.append(deepcopy(path))
    else:
        if len(path) == n:
            complete_paths.append(path)
print(len(complete_paths))

Submission status: Accepted

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

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

counter = 0
def dfs(pointer, already_visited):
    global counter
    if len(already_visited) == n - 1:
        counter += 1
    for el in graph[pointer]:
        if el in already_visited:
            continue
        dfs(el, already_visited + [pointer])

dfs(1, [])
print(counter)

Submission status: Accepted

Solution code:
import math
import sys
from collections import deque
import copy
import itertools
from itertools import permutations
def mi() : return map(int,input().split())
def i() : return int(input())
a,b=mi()
ans=0
l=[[] for _ in range(a)]
for i in range(b):
  u,v=mi()
  l[u-1].append(v-1)
  l[v-1].append(u-1)
S=[]
for i in range(1,a):
  S.append(i)
lst=list(permutations(S))
for i in lst:
  x=0
  t=True
  for w in range(len(i)):
    if not i[w] in l[x]:
      t=False
      break
    x=i[w]
  if t:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

def readinput():
    n,m=list(map(int,input().split()))
    nList=[]
    for _ in range(n+1):
        nList.append([])
    for _ in range(m):
        a,b=list(map(int,input().split()))
        nList[a].append(b)
        nList[b].append(a)
    
    return n,m,nList

def main(n,m,nList):
    permlist = permutations(range(2,n+1))
    count=0
    for perm in permlist:
        current=1
        for i in range(n-1):
            next=perm[i]
            if not next in nList[current]:
                break
            current=next
        else:
            count+=1
    return count

if __name__=='__main__':
    n,m,nList=readinput()
    ans=main(n,m,nList)
    print(ans)

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 sys 
from copy import deepcopy
from collections import deque
sys.setrecursionlimit(10**6)
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))

def solve(table,ava,now):
    if not 1 in ava:
        global ans
        ans += 1
        return
    global N
    for i in range(N):
        if table[now][i] and ava[i]:
            bt,ba = deepcopy(table),deepcopy(ava)
            bt[now][i] = bt[i][now] = ba[i] = 0
            solve(bt,ba,i)
    return

if __name__=='__main__':
    tmp = deque(LI())
    N,M = tmp.popleft(),tmp.popleft()
    table = [[0]*N for _ in range(N)]
    for i in range(M):
        tmp = deque(LI())
        a,b = tmp.popleft()-1,tmp.popleft()-1
        table[a][b] = table[b][a] = 1
    ans = 0
    ava = [1]*N
    ava[0] = 0
    solve(table,ava,0)
    print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
def DFS(node, seen):
    if len(seen)==n-1:
        return 1
    tmp = 0
    for i in graph[node]:
        if i in seen:
            continue
        tmp += DFS(i, seen|{node})
    return tmp
print(DFS(0, set()))

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10**9)

from sys import stdin
#入力
readline=stdin.readline
n,m=map(int,readline().split())
G=[[] for _ in range(n)]
for i in range(m):
    a,b=map(lambda x:int(x)-1,readline().split())
    G[a].append(b)
    G[b].append(a)

flags=[False]*n
ans=0
def dfs(now,cnt):
    global ans
    cnt+=1
    flags[now]=True
    if cnt==n:
        ans+=1
    else:
        for nex in G[now]:
            if flags[nex]==False:
                dfs(nex,cnt)
    flags[now]=False

dfs(0,0)
print(ans)

Submission status: Accepted

Solution code:
def dfs(a,count,seen):
    nseen=seen[:]
    ans=0
    nseen[a] = 1;
    if count==n-1:
        return 1
    else:
        for i in g[a]:
            if not seen[i]:
                ans+=dfs(i,count+1,nseen)
        return ans
n,m=map(int,input().split())
g=[[]*n for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
seen=[0]*n
print(dfs(0,0,seen))

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:
#!python3

LI = lambda: list(map(int, input().split()))

# input
N, M = LI()
AB = [LI() for _ in range(M)]

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


def create_link():
    for a, b in AB:
        link[a - 1].append(b - 1)
        link[b - 1].append(a - 1)


def dfs(v=0, s=set()):
    s = s | {v}
    if len(s) == N:
        return 1
    ans = 0
    for u in link[v]:
        if u in s:
            continue
        ans += dfs(u, s)
    return ans


def main():
    create_link()
    ans = dfs()
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

D = [0]*N
C = 0
D[0] = 1

def dfs(x):
    global C
    
    if not 0 in D:
        C += 1
        return
    
    for i in A[x]:
        if D[i] == 1:
            continue
        D[i] = 1
        dfs(i)
        D[i] = 0

dfs(0)
print(C)

Submission status: Accepted

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

def DFS(p):
  count = 0
  if all(visit):
    return 1
  for n in adj[p]:
    if visit[n] == 0:
      visit[n] = 1
      count += DFS(n)
      visit[n] = 0
  return count

def main():
  for n in range(N):
    adj.append([])
    visit.append(0)
  for m in range(M):
    i, j = list(map(int,input().split()))
    adj[i-1].append(j-1)
    adj[j-1].append(i-1)
  visit[0] = 1
  return DFS(0)

print(main())

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
g=[[]for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  g[a-1].append(b-1)
  g[b-1].append(a-1)
import sys
sys.setrecursionlimit(10**7)

def dfs(t,seen):
  if all(seen):
    return 1
  ret=0
  l=g[t]
  for li in l:
    if seen[li]==0:
      seenli=seen.copy()
      seenli[li]=1
      ret+=dfs(li,seenli)
  return ret
seen=[0]*n
seen[0]=1
print(dfs(0,seen))

Submission status: Accepted

Solution code:
import itertools

n, m = list(map(int, input().split()))
v = []
for i in range(m):
  tpl = tuple(map(int, input().split()))
  v.append(tpl)
  v.append((tpl[1], tpl[0]))

perms = list(itertools.permutations(range(1, n+1)))
c = 0
for i in perms:
  if i[0] != 1:
    continue
  for j in range(len(i)-1):
    if (i[j], i[j+1]) not in v:
      break
  else:
    c += 1
print(c)

Submission status: Accepted

Solution code:
import sys
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue
from decimal import Decimal

# import fractions

sys.setrecursionlimit(10000000)

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

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

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def dfs(graph, start, visited):
    visited[start] = True
    ret = 0
    if all(visited):
        visited[start] = False
        return 1

    for next in graph[start]:
        if not visited[next]:
            ret += dfs(graph, next, visited)
    visited[start] = False
    return ret


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

    N, M = il()
    graph = {n: [] for n in range(N)}
    visited = [False] * N
    for _ in range(M):
        a, b = il()
        graph[a - 1].append(b - 1)
        graph[b - 1].append(a - 1)

    print(dfs(graph, 0, visited))


if __name__ == '__main__':
    main()