Problem:


Score : 300 points

Problem Statement

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

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

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

Here, the endpoints of a path are considered visited.  

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

Figure 1: an example of an undirected graph

The following path shown in Figure 2 satisfies the condition.

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

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

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

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

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

Constraints

2≦N≦8 

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

1≦a_i<b_i≦N 

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

Input

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

N M  
a_1 b_1  
a_2 b_2
:  
a_M b_M  

Output

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

Sample Input 1

3 3
1 2
1 3
2 3

Sample Output 1

2

The given graph is shown in the following figure:

The following two paths satisfy the condition:

Sample Input 2

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

Sample Output 2

1

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



Sample input:
3 3
1 2
1 3
2 3


Sample output:
2

Submission status: Accepted

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

check = [False] * N
check[0] = True
def dfs(v):
    if sum(check) == N:
        return 1
    ans = 0
    for u in E[v]:
        if check[u]:
            continue
        check[u] = True
        ans += dfs(u)
        check[u] = False
    return ans
print(dfs(0))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
d = {i+1 : [] for i in range(n)}
for _ in range(m):
  a, b = map(int, input().split())
  d[a].append(b)
  d[b].append(a)
ans = 0
def go(c, rem):
  global ans
  if not len(rem):
    ans += 1
    return
  for cand in d[c]:
    if cand in rem:
      i = rem.index(cand)
      go(cand, rem[:i] + rem[i+1:])
go(1, list(range(2, n+1)))
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

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

A = [[0]*N for i in range(N)]

for i in range(M) :
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    
    A[u][v] = 1
    A[v][u] = 1

ran = list(range(1,N))

P = list(permutations(ran))

ans = 0

for perm in P :
    perm = list(perm)
    
    for u,v in zip([0]+perm, perm) :
        if not A[u][v] :
            break
        
    else :
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N, M = LI()
ab = LIR(M)

for i in range(M):
    ab[i] = [ab[i][0]-1, ab[i][1]-1]

edge = [[0]*N for i in range(N)]

for e in ab:
    edge[e[0]][e[1]] = edge[e[1]][e[0]] = 1

ans = 0

def make_permutation(li, r):
    if (r <= 0) or (r > len(li)):
        return []
    
    result = []
    _make_permutation(li, r, [], result)
    return result

def _make_permutation(li, r, out, result):
    if (r == 0):
        result.append(out)
        return

    for i, num in enumerate(li):
        _make_permutation(li[:i]+li[i+1:], r-1, out+[li[i]], result)

vs = list(range(1,N))
perm = make_permutation(vs, N-1)

for pe in perm:
    before = 0
    for num in pe:
        if (edge[before][num]):
            before = num
            continue
        else:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

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

to = [[] for _ in range(N)]
visited = [False] * N

def dfs(v):
    if sum(visited) == N:
        return 1 
    
    ret = 0
    for u in to[v]:
        if not visited[u]:
            visited[u] = True
            ret += dfs(u)
            visited[u] = False  # 最も深い点から帰ってくる道中に、始点を除く全ての点を未訪問にする => 他のパスを辿ることが可能になる

    return ret


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

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

Submission status: Accepted

Solution code:
import numpy as np
import copy


def visit(next_node, visited_nodes, adj_mat):
    assert next_node not in visited_nodes

    if len(visited_nodes) + 1 == len(adj_mat):
        # Visited all nodes
        return 1
    else:
        adj_nodes = np.argwhere(adj_mat[next_node].flatten() == 1)
        if len(adj_nodes) == 0:
            # Failed
            return 0
        else:
            n_paths = 0
            for adj_node in adj_nodes:
                if adj_node not in visited_nodes:
                    n_paths += visit(adj_node, visited_nodes +
                                     [next_node, ], adj_mat)
                else:
                    continue
            return n_paths


def main():
    N, M = map(int, input().split())
    adj_mat = np.zeros((N, N), dtype=np.int32)
    for _ in range(M):
        a, b = map(int, input().split())
        adj_mat[a-1][b-1] = 1
        adj_mat[b-1][a-1] = 1
    assert np.sum(adj_mat) == M * 2

    next_nodes = np.argwhere(adj_mat[0].flatten() == 1)
    n_paths = np.sum([visit(next_node, [0, ], adj_mat)
                      for next_node in next_nodes])

    print(n_paths)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import*
n,*t=map(int,open(0).read().split())
e={0}
for a in zip(t[1::2],t[2::2]):e|={a,a[::-1]}
print(sum(all(u in e for u in zip(t,t[1:]))for t in permutations(range(1,n+1))if t[0]<2))

Submission status: Accepted

Solution code:

from collections import defaultdict
import itertools

def main():
    node_num, edge_num = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(edge_num)]
    edge_dic = defaultdict(set)
    for i in range(edge_num):
        a, b = data[i]
        edge_dic[a].add(b)
        edge_dic[b].add(a)

    ori_list = [i for i in range(2, node_num + 1)]
    ans = 0
    for root in list(itertools.permutations(ori_list, node_num - 1)):
        root = [1] + list(root)
        for i in range(node_num - 1):
            if root[i + 1] not in edge_dic[root[i]]:
                break
        else:
            ans += 1

    print(ans)




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import permutations

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

L = [[False for j in range(N)] for i in range(N)]

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

P = list(permutations(range(1,N)))

ans = 0

for perm in P :
    perm = list(perm)
    
    for s,g in zip([0] + perm, perm) :
        if not L[s][g] :
            break
    else :
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools
n, m = map(int, input().split())
e = set([tuple(sorted(map(int, input().split()))) for x in range(m)])
cnt = 0
for i in itertools.permutations(range(2, n+1), n-1):
    l = [1]+list(i)
    if sum(1 for x in range(n-1) if tuple(sorted(l[x: x+2])) in e) == n-1:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
inpl = lambda: list(map(int,input().split()))

def routes(start, tovisit):
	if len(tovisit) == 0:
		return 1
	else:
		ret = sum(routes(nextnode, tovisit - {nextnode}) for nextnode in neigh[start] & tovisit)
		if ret is None:
			return 0
		else:
			return ret

N, M = inpl()
neigh = [ set() for _ in range(N) ]
for _ in range(M):
	a, b = inpl()
	neigh[a-1].add(b-1)
	neigh[b-1].add(a-1)

print(routes(0,set(range(1,N))))

Submission status: Accepted

Solution code:
from itertools import permutations

N, M = map(int, input().split())
ab = [[int(_) for _ in input().split()] for _ in range(M)]
Graph = [[] for _ in range(N+1)]
cand = list(permutations(range(1, N+1), N))
ans = 0

for i in ab:
    Graph[i[0]].append(i[1])
    Graph[i[1]].append(i[0])

for i in cand:
    if i[0] != 1:
        break
    flag = True
    for j in range(len(i)-1):
        if not (i[j+1] in Graph[i[j]]):
            flag = False
            break
    
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations, permutations
def inpl(): return list(map(int, input().split()))

N, M = inpl()
G = [[0]*(N+1) for _ in range(N+1)]

for _ in range(M):
    a, b = inpl()
    G[a][b] = 1
    G[b][a] = 1

ans = 0
for X in permutations(range(2, N+1)):
    a = 1
    for i in range(N-1):
        b = X[i]
        if G[a][b] == 0:
            break
        a = b
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
input = sys.stdin.readline

N, M, = map(int, input().split())
L = [[int(v) for v in input().split()] for _ in range(M)]
t = [set() for _ in range(N)]

for i in range(M):
    x, y = L[i]
    
    t[x - 1].add(y - 1)
    t[y - 1].add(x - 1)

ans = 0
def dfs(now, visited):
    global ans
    
    if len(visited) == N:
        ans += 1
        return
    
    for v in t[now]:
        if v not in visited:
            dfs(v, visited + [v])

    return

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

Submission status: Accepted

Solution code:
# 全域木？っていうんだっけ？でもコストは関係ないか
# 適当に隣接リストでもってしてDFSする
N, M = map(int, input().split())
Neighbor_list = [[] for _ in range(N)]
for _ in range(M):
    s, t = map(int, input().split())
    Neighbor_list[s-1].append(t-1)
    Neighbor_list[t-1].append(s-1)


def dfs(cur, path):
    if len(path) == N:
        return 1
    else:
        ret = 0
        for neighbor in Neighbor_list[cur]:
            if neighbor not in path:
                next_list = path[:]
                next_list.append(neighbor)
                ret += dfs(neighbor, next_list)
        return ret


print(dfs(0, [0]))

Submission status: Accepted

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

def checkpath(nodes,E,current):
    next = []
    newnodes = nodes.copy()
    newnodes[current] = 0

    for e in E[current]:
        if newnodes[e]:
            next.append(e)

    if len(next) == 0:
        if sum(newnodes) == 0:
            return 1
        else:
            return 0
    else:
        return sum([checkpath(newnodes,E,e) for e in next])

nodes = [1]*(n+1)
nodes[0] = 0
print(checkpath(nodes,edge,1))

Submission status: Accepted

Solution code:
ans=0
def DFS(v,visited):
    global ans
    if visited == [1]*N:
        ans += 1
        return
    for next in edge[v]:
        if visited[next] != 1:
            visited[next] = 1
            DFS(next,visited)
            visited[next] = 0 
    return

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)
visited = [0 for _ in range(N)]
visited[0]=1
DFS(0,visited)
print(ans)

Submission status: Accepted

Solution code:
import itertools
n, m = map(int, input().split())
d = [[0 for i in range(n)] for j in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a-=1
    b-=1
    d[a][b] = 1
    d[b][a] = 1
ans = 0

nums = [i for i in range(n)]
for num in itertools.permutations(nums):
    if(num[0] != 0):
        continue
    flag = True
    for i in range(n - 1):
        if(d[num[i]][num[i+1]] != 1):
            flag = False
            break
    if(flag):
        ans += 1

print(ans)

Submission status: Accepted

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

def dfs(x, t):
  if t==n:
    return 1

  visited[x] = 1
  cur = 0
  for nx in edge[x]:
    if not visited[nx]:
      cur += dfs(nx, t+1)
  visited[x] = 0
  return cur

print(dfs(0, 1))

Submission status: Accepted

Solution code:
from collections import deque
from itertools import permutations as perm

N,M = map(int, input().split())
A = {}
for i in range(M):
    a,b = map(int, input().split())
    if a not in A:
        A[a] = {}
    if b not in A:
        A[b] = {}
    A[a][b] = A[b][a] = 1

ans = 0
for lst in perm([i for i in range(2,N+1)]):
    tmp = 1
    for i in range(N-1):
        if lst[i] not in A[tmp]:
            break
        tmp = lst[i]
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

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

for i in range(M):
    a, b = map(int, input().split())
    gr |= {(a-1,b-1),(b-1,a-1)}

ans = 0
for p in permutations(range(N)):
    if p[0]==0:
        cnt = 0
        cntp = 0
        for i in range(N-1):
            cnt += 1
            if (p[i],p[i+1]) in gr:
                cntp += 1
            else:
                break
        if cnt == cntp:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
ab = [LIST() for _ in range(M)]

graph = [[0]*N for _ in range(N)]
for a, b in ab:
	graph[a-1][b-1] = 1
	graph[b-1][a-1] = 1

ans = 0
for i in permutations(range(1, N)):
	i = list(i)
	i.insert(0, 0)
	# print(i)
	for j in range(N-1):
		if graph[i[j]][i[j+1]] != 1:
			break
	else:
		ans += 1
print(ans)

Submission status: Accepted

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

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

link = []

for i in range(n):
    num = i + 1
    link.append([])
    for a_i, b_i in zip(a, b):
        if a_i == num:
            link[i].append(b_i)
        if b_i == num:
            link[i].append(a_i)
pass_count = 0

hie_ind = [0 for i in range(n)]
pass_his = [1]
finish = False
while True:
    if len(pass_his) == n:
        pass_count += 1
        pass_his.pop()

    hierarchy = len(pass_his) - 1
    now_n = pass_his[-1]-1
    now_ind = hie_ind[hierarchy]

    while True:
        if now_ind > (len(link[now_n]) - 1):
            if now_n == 0:
                finish = True
                break
            pass_his.pop()
            hie_ind[hierarchy] = 0

            hierarchy = len(pass_his) - 1
            now_n = pass_his[-1]-1
            now_ind = hie_ind[hierarchy]
        else:
            break
    if finish:
        break

    cand_n = link[now_n][now_ind]

    if not(cand_n in pass_his):
        pass_his.append(cand_n)
    hie_ind[hierarchy] += 1

print(pass_count)

Submission status: Accepted

Solution code:
from itertools import permutations

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

perm = permutations(list(range(2, n+1)), n - 1)

ans = 0
for p in perm:
    flag = True
    for i in range(n-1):
        if i == 0:
            if not [1, p[i]] in ab:
                flag = False
                break
        else:
            if not ([p[i-1], p[i]] in ab or [p[i], p[i-1]] in ab):
                flag = False
                break
    if flag: ans += 1
print(ans)

Submission status: Accepted

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

answer = 0

for p in itertools.permutations(range(1,N+1)):
  if p[0] != 1:
    continue
  bl = True
  for i in range(N-1):
    if (p[i], p[i+1]) not in edges:
      bl = False
      break
  if bl:
    answer += 1

print(answer)

Submission status: Accepted

Solution code:
from collections import defaultdict

n, m = map(int, input().split())
p = defaultdict(set)
for _ in range(m):
  ai, bi = map(int, input().split())
  p[ai].add(bi)
  p[bi].add(ai)

cnt = 0
cand_list = [(1, set(range(2, n + 1)))]

while(len(cand_list) != 0):
  c = cand_list.pop(0)

  if len(c[1]) == 0:
    cnt += 1
  for x in c[1] & p[c[0]]:
    remain = c[1].copy()
    remain.remove(x)
    cand_list.append((x, remain))

print(cnt)

Submission status: Accepted

Solution code:
import copy
n, m = [ int(v) for v in input().split() ]
connect_matrix = [[ 0 for i in range(n)] for j in range(n)]

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


one_path_list = [[0]]
for i in range(n-1):
    next_path_list = []

    for j in range(len(one_path_list)):

        next_point_list = [ k for k in range(n) if connect_matrix[one_path_list[j][-1]][k] == 1 and k not in one_path_list[j]]

        for k in range(len(next_point_list)):
            next_path_list.append(copy.deepcopy(one_path_list[j])+[next_point_list[k]])

    one_path_list = next_path_list 

print(len(one_path_list))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(m)]
p=[list() for i in range(n+1)]
for a,b in l:
	p[a].append(b)
	p[b].append(a)
q=[(1,[1])]
ans=0
while len(q)!=0:
	x,v=q.pop(0)
	if len(v)==n:
		ans+=1
		continue
	for i in p[x]:
		if i in v:continue
		q.append((i,v+[i]))
print(ans)

Submission status: Accepted

Solution code:
nmax=8
#深さ優先探索
def dfs(v,n,visited):
    all_visited=True
    for i in range(n):
        #ある経路においてvisitedすべてTrueか
        if visited[i]==False:
            all_visited=False
    if all_visited:
        return 1
    
    ans=0
    for i in range(n):
        #パスがないならcontinue
        if graph[v][i]==False:
            continue
        #すでに通ったならcontinue
        if visited[i]:
            continue
        #通った頂点をTrueにする
        visited[i]=True
        #次の深さを探索
        ans += dfs(i,n,visited)
        #深いところから戻るのでvisitedをFalseに
        visited[i]=False
    return ans

n,m = map(int,input().split())
#graph[n][n]をFalseで初期化
graph=[]
for i in range(n):
    graph.append([False]*n)
#graph上でパスの通っているものをTrueとする
for _ in range(m):
    a,b = map(int,input().split())
    graph[a-1][b-1]=True
    graph[b-1][a-1]=True
#visited[n]をFalseで初期化
visited=[]
for _ in range(n):
    visited.append(False)
#頂点1を始点とする(visited[(頂点)-1])
visited[0]=True
print(dfs(0,n,visited))

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(N, M, inputs):
    relations = {}
    visited_all = (2 ** N) - 1
    for i in range(1, N + 1):
        relations[i] = []

    for i in inputs:
        [parent, child] = string_to_int(i)
        relations[parent].append(child)
        relations[child].append(parent)

    routes = 0
    queue = deque([[1, 0]])
    while len(queue) > 0:
        [node, visited] = queue.popleft()

        if visited & (1 << (node - 1)) != 0:
            continue

        visited = visited + (1 << (node - 1))

        if visited == visited_all:
            routes += 1
            continue

        for next in relations[node]:
            queue.append([next, visited])
    return routes


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    [N, M] = string_to_int(input())
    ret = solve(N, M, inputs(M))
    print(ret)

Submission status: Accepted

Solution code:
from collections import defaultdict
N, M = map(int, input().split())

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

V = [0] * N
V[0] = 1
def dfs(n, V):
    if all([v == 1 for v in V]):
        return 1

    ans = 0
    for e in G[n]:
        if V[e] == 1:
            continue
        V[e] = 1
        ans += dfs(e, V)
        V[e] = 0
    
    return ans

print(dfs(0, V))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)
n,m=map(int,input().split())
bra=[set() for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    bra[a-1].add(b-1)
    bra[b-1].add(a-1)

visit=[1]+[0]*(n-1)
#print(bra)
cnt=[]
def dfs(a,visit):
    if visit==[1]*n:
        cnt.append(1)
        return 
    for e in bra[a]:
        if visit[e]==0:
            visit[e]=1
#            print(visit)
            dfs(e,visit)
            visit[e]=0  
    return 
dfs(0,visit)
print(len(cnt))

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int,input().split())
edge = [[] for i in range(N)]
visited = [0]
count = 0

for i in range(M):
  a, b = map(int,input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)
  
def DFS(n):
  global count
  if len(visited) == N:
    count += 1
    return
  else:
    for i in edge[n]:
      if not(i in visited):
        visited.append(i)
        DFS(i)
        visited.remove(i)
    return

DFS(0)

print(count)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=list(range(2,n+1))
v=[[] for i in range(1+n)]
for i in range(m):
    a,b=map(int,input().split())
    v[a].append(b)
    v[b].append(a)

def check(ls):
    fr=1
    for to in ls:
        if int(to) not in v[fr]:
            return 0
        fr=int(to)
    return 1

def gen(ls):
    if not ls:
        return [[]]
    return [[a]+b for i,a in enumerate(ls) for b in gen(ls[:i]+ls[i+1:])]
    
print(sum([check(i) for i in gen(l)]))

Submission status: Accepted

Solution code:
import itertools
n,m=map(int,input().split())
lst=[]
for i in range(m):
    lst+=[list(map(int,input().split()))]



pair=[[0]*n for i in range(n)]
for i,j in lst:
    pair[i-1][j-1]=1
    pair[j-1][i-1]=1


def keiro(a):
    count=0
    for i in range(n-1):
        if pair[a[i]-1][a[i+1]-1]==0:
            break
    else:
        count+=1
    return count
cn=0
b=[i for i in range(2,n+1)]
for i in list(itertools.permutations(b)):
    a=[1]+list(i)
    if keiro(a)==1:
        cn+=1

print(cn)

Submission status: Accepted

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

edges = [set() for _ in range(N + 1)]
for a, b in AB:
	edges[a] |= {b}
	edges[b] |= {a}

count = 0
def dfs(current, visited):
	global count
	if N == len(visited):
		count += 1
		return
	for _next in edges[current]:
		if _next not in visited:
			dfs(_next, visited | {_next})

dfs(1, {1})

print(count)

Submission status: Accepted

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

import copy

n,m = list(map(int,input().split()))
rinset = [[0]*(n+1) for _ in range(n+1)]
for _ in range(m):
    a,b = list(map(int,input().split()))
    rinset[a][b]=b
    rinset[b][a]=a
cnt = 0
def solve(start,visitted):
    global cnt
    visitted = copy.deepcopy(visitted)
    visitted.append(start)
    if len(visitted) == n:
        cnt+=1
        return
    next_start=[i for i in rinset[start] if (i>1 and i not in visitted)]
    for i in next_start:
        solve(i,visitted)

solve(1,[])
print(cnt)

Submission status: Accepted

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

visited = [False] * N

def dfs(v, count):
    if visited.count(True) == N:
        return 1
    else:
        ans = 0
        for i in g[v]:
            if not visited[i]:
                visited[i] = True
                ans += dfs(i, count+1)
                visited[i] = False
        return ans

visited[0] = True
print(dfs(0,1))

Submission status: Accepted

Solution code:
def dfs(num,s):
    cnt = 0
    s.add(num)
    if(len(s)==N):
        s.discard(num)
        return 1
    for x in li[num]:
        if(x not in s):
            cnt += dfs(x,s)
    s.discard(num)
    return cnt
#%%
N,M = [int(x) for x in input().split()]
li = [[]for _ in range(N+1)]
for _ in range(M):
    a,b = [int(x) for x in input().split()]
    li[a].append(b)
    li[b].append(a)
#%%
sets = set()
ans = dfs(1,sets)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

N, M = map(int, input().split())
E = []
for _ in range(M):
    a, b = map(int, input().split())
    E.append((a, b))
    E.append((b, a))
ans = 0
for p in permutations(range(2, N+1)):
    perm = [1] + list(p)
    for i in range(N-1):
        if (perm[i], perm[i+1]) not in E:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import pdb

N, M = map(int, input().split())
a, b = [], []
mat = [[0 for _ in range(N)] for _ in range(N)]

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

visited = set()
ans = 0

def dfs(num):
    global ans
    #pdb.set_trace()
    visited.add(num)
    if len(visited) == N:
        ans += 1
        return 
    
    for next_num, connected in enumerate(mat[num]):
        if not connected:
            continue
        if next_num in visited:
            continue
        visited.add(next_num)
        dfs(next_num)
        visited.remove(next_num)
    return

def main():
    dfs(0)
    print(ans)

main()

Submission status: Accepted

Solution code:
import itertools

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

a = [list(sorted(map(int, input().split()))) for i in range(m)]
a.sort()

cnt = 0

for i in itertools.permutations(range(2, n +1), (n-1)):
    li = [1] + list(i)
    if sum(list(sorted(edge)) in a for edge in zip(li, li[1:])) == n-1:
        cnt += 1
    
print(cnt)

Submission status: Accepted

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

graph = [[0] * N for _ in range(N)]
for u, v in edges:
    graph[u - 1][v - 1] = 1
    graph[v - 1][u - 1] = 1

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

def dfs(s):    
    if all(visited):
        return 1

    cnt = 0
    for i in range(N):
        if visited[i] or graph[s][i] != 1:
            continue
            
        visited[i] = True
        cnt += dfs(i)
        visited[i] = False
        
    return cnt

print(dfs(0))

Submission status: Accepted

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

graph = [[None] * N for _ in range(N)]
for u, v in edges:
    graph[u - 1][v - 1] = True
    graph[v - 1][u - 1] = True

def dfs(s):    
    if all(visited):
        return 1

    cnt = 0
    for i in range(N):
        if graph[s][i] is None:
            continue

        if visited[i]:
            continue
            
        visited[i] = True
        cnt += dfs(i)
        visited[i] = False
        
    return cnt

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

Submission status: Accepted

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

graph = [[False] * N for _ in range(N)]
for u, v in edges:
    graph[u - 1][v - 1] = True
    graph[v - 1][u - 1] = True

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

def dfs(s):    
    if all(visited):
        return 1

    cnt = 0
    for i in range(N):
        if not graph[s][i]:
            continue
        
        if visited[i]:
            continue
            
        visited[i] = True
        cnt += dfs(i)
        visited[i] = False
        
    return cnt

print(dfs(0))

Submission status: Accepted

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

graph = [[False] * N for _ in range(N)]
for u, v in edges:
    graph[u - 1][v - 1] = True
    graph[v - 1][u - 1] = True

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

def dfs(s):    
    if all(visited):
        return 1

    cnt = 0
    for i in range(N):
        if visited[i]:
            continue
            
        if not graph[s][i]:
            continue
            
        visited[i] = True
        cnt += dfs(i)
        visited[i] = False
        
    return cnt

print(dfs(0))

Submission status: Accepted

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

graph = [[0] * N for _ in range(N)]
for u, v in edges:
    graph[u - 1][v - 1] = 1
    graph[v - 1][u - 1] = 1

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

def dfs(s):    
    if all(visited):
        return 1

    cnt = 0
    for i in range(N):
        if visited[i] or graph[s][i] != 1:
            continue
            
        visited[i] = True
        cnt += dfs(i)
        visited[i] = False
        
    return cnt

print(dfs(0))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)

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

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

for i in range(M):
	A, B = [int(x) for x in input().split()]
	graph[A-1][B-1] = graph[B-1][A-1] = True

visited = [False] * N

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

Submission status: Accepted

Solution code:
import itertools

n, m=map(int, input().split())
branch=[]
for i in range(m):
    a, b=map(int, input().split())
    branch.append((a, b))
seq=[]
for i in range(2, n+1):
    seq.append(i)
ans=0
permutation=list(itertools.permutations(seq))
for i in range(len(permutation)):
    number_list=list(map(int, permutation[i]))
    start=1
    flag=1
    for j in range(n-1):
        if not ((start, number_list[j]) in branch or (number_list[j], start) in branch):
            flag=0
            break
        start=number_list[j]
    if flag:
        ans=ans+1
print(ans)