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

#動くことのできる経路とその逆向きの移動をリストにし、それをリストにしたもの
lst = []
for i in range(M):
    a = list(map(int, input().split()))
    lst += [a] + [a[::-1]]

def next_permutation(L): #リストを順列で並び替える部分
    i = N - 2
    while i >= 0 and L[i] > L[i+1]:
        i -= 1

    if i == -1:
        return False

    j = i + 1
    while j < N and L[i] < L[j]:
        j += 1
    j -= 1

    L[i], L[j] = L[j], L[i]

    left = i + 1
    right = N - 1

    while left < right:
        L[left], L[right] = L[right], L[left]
        left += 1
        right -= 1

    return True

#1-->Nまでの整数が順に並んでいるリスト、このリストの順番にたどるとする
L = [i+1 for i in range(N)]
#print ('作成したL', L)

def judge(L): #ある経路Lが与えられたときに、その移動がリスト内の移動法で可能かどうかを判定、可能-->True 不可-->Falseを返す
    for i in range(N-1):
        if not L[i:i+2] in lst:
#            print ('L[i:i+2]=', L[i:i+2])
            return False
    return True


def roop(L): #全判定する部分
    count = 0
    while True:
        #順路が条件を満たすか判定する部分
#        print ('ループ内L', L)
#        time.sleep(3)
        if L[0] != 1: #並び替えた後に最初が1ではない-->パスが1から始まらず条件を満たさない
            print (count)
            break
        if judge(L):
            count += 1
        if not next_permutation(L):
            print (count)
            break
    return 'error'
#print ('lst = ',lst)
roop(L)

Submission status: Accepted

Solution code:
import itertools

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

v = list(range(1,n+1))

edge = []
for i in range(m):
    a,b = map(int,input().split())
    edge.append((a,b))
    edge.append((b,a))
res = 0
for s in itertools.permutations(v):
    if s[0]!=1:
        continue
    flag = True
    for i in range(1,len(s)):
        if (s[i-1],s[i]) not in edge:
            flag =False
    if flag:
        res+=1   
print(res)

Submission status: Accepted

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


def search(cr_node, cr_depth, is_visited, edges, max_depth):
    if cr_node in is_visited:
        return 0
    elif cr_depth == max_depth:
        return 1
    else:
        count = 0

        if edges[cr_node]:
            is_visited.add(cr_node)
            for edge in edges[cr_node]:
                count += search(edge, cr_depth + 1,
                                is_visited, edges, max_depth)
            is_visited.remove(cr_node)

        return count


def main():
    N, M = map(int, input().split())
    edges = dict()
    for i in range(N):
        edges[i] = []

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

    print(search(0, 1, set(), edges, N))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

input_int = lambda:int(input())
input_ints = lambda:map(int,input().split())
input_ints_list = lambda:list(input_ints())
input_str = lambda:input()
input_strs = lambda:input().split()
input_lines = lambda n,f:[f() for _ in range(n)]

import functools,fractions
gcd = lambda a:functools.reduce(fractions.gcd,a) # 最大公約数（リスト）
lcm_base = lambda a,b:(a*b)//fractions.gcd(a,b) # 最小公倍数(2値)
lcm = lambda a:functools.reduce(lcm_base,a,1) # 最小公倍数(リスト)

import itertools
permutations = lambda a,n:itertools.permutations(a,n) # 順列
combinations = lambda a,n:itertools.combinations(a,n) # 組み合わせ
product = lambda a,b:itertools.product(a,b) # 二つのリストの直積

init_array_1dim = lambda v,n:[v for _ in range(n)]
init_array_2dim = lambda v,n,m:[[v for _ in range(n)] for _ in range(m)]

import math
# 四捨五入はround
ceil = lambda a:math.ceil(a) # 切り上げ
floor = lambda a:math.floor(a) # 切り捨て

def dfs_graph(v,n,graph,visited):
	if all(visited):return 1
	ans = 0
	for i in range(n):
		if graph[v][i] == False:continue
		if visited[i]:continue
		visited[i] = True
		ans += dfs_graph(i,n,graph,visited)
		visited[i] = False
	return ans

def init_graph(n,a,directed=False):
    visited = init_array_1dim(False,n)
    graph = init_array_2dim(False,n,n)
    for e in a:
        graph[e[0]-1][e[1]-1] = True
        if not directed:graph[e[1]-1][e[0]-1] = True # 無向グラフの場合
    return visited,graph

def solution():
    N,M = input_ints()
    ab = input_lines(M,input_ints_list)
    visited,graph = init_graph(N,ab)
    visited[0] = True
    print(dfs_graph(0,N,graph,visited))

if __name__ == '__main__':
    solution()

Submission status: Accepted

Solution code:
import sys

input_int = lambda:int(input())
input_ints = lambda:map(int,input().split())
input_ints_list = lambda:list(input_ints())
input_str = lambda:input()
input_strs = lambda:input().split()
input_lines = lambda n,f:[f() for _ in range(n)]

import functools,fractions
gcd = lambda a:functools.reduce(fractions.gcd,a) # 最大公約数（リスト）
lcm_base = lambda a,b:(a*b)//fractions.gcd(a,b) # 最小公倍数(2値)
lcm = lambda a:functools.reduce(lcm_base,a,1) # 最小公倍数(リスト)

import itertools
permutations = lambda a,n:itertools.permutations(a,n) # 順列
combinations = lambda a,n:itertools.combinations(a,n) # 組み合わせ
product = lambda a,b:itertools.product(a,b) # 二つのリストの直積

init_array_1dim = lambda v,n:[v for _ in range(n)]
init_array_2dim = lambda v,n,m:[[v for _ in range(n)] for _ in range(m)]

import math
# 四捨五入はround
ceil = lambda a:math.ceil(a) # 切り上げ
floor = lambda a:math.floor(a) # 切り捨て

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

def init_graph(n,a,directed=False):
    visited = init_array_1dim(False,n)
    graph = init_array_2dim(False,n,n)
    for e in a:
        graph[e[0]-1][e[1]-1] = True
        if not directed:graph[e[1]-1][e[0]-1] = True # 無向グラフの場合
    return visited,graph

def solution():
    N,M = input_ints()
    ab = input_lines(M,input_ints_list)
    visited,graph = init_graph(N,ab)
    visited[0] = True
    print(dfs(0,N,graph,visited))

if __name__ == '__main__':
    solution()

Submission status: Accepted

Solution code:
ans = 0
def dfs(v, visitedNode, graph):
    visitedNode[v] = 1
    # print(visitedNode)
    if all(visitedNode):
        global ans
        ans += 1
        return
    for node in graph[v]:
        if visitedNode[node]:
            # 探索済みならば、ほかの隣接候補へ。
            continue
        else:
            # 未探索ならば、次の階層を調べる。
            dfs(node, visitedNode[:], graph)


N, M = map(int, input().split())
v = 0
visitedNode = [0] * N


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


dfs(v, visitedNode, graph)
print(ans)

Submission status: Accepted

Solution code:
ans = 0
def dfs(v, visitedNode, graph):
    visitedNode[v] = 1
    if all(visitedNode):
        global ans
        ans += 1
        return
    for node in graph[v]:
        if visitedNode[node]:
            continue
        else:
            dfs(node, visitedNode[:], graph)


N, M = map(int, input().split())
v = 0
visitedNode = [0] * N


# 隣接リストを作成する
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)


# 深さ優先探索で経路数を数える
dfs(v, visitedNode, graph)
print(ans)

Submission status: Accepted

Solution code:


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

    edges = []
    nodes = list(range(1, n + 1))

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


    edges_dic = {}
    for i in range(n):
        edges_dic[i + 1] = []

    for edge in edges:
        edges_dic[edge[0]].append(edge[1])
        edges_dic[edge[1]].append(edge[0])

    return n, m, nodes, edges_dic


# throughを通過済みとして、curr_nodeから残りのnodesにたどり着けるかチェックする
def check_path(curr_node, rest_nodes, edges_dic, through):
    # 終点
    if not rest_nodes:
        return 1

    # rest_nodesのうち、curr_nodeからいけるnodeがあるか確認する
    next_nodes = edges_dic[curr_node]
    targets = []
    for n in next_nodes:
        if n in rest_nodes:
            targets.append(n)

    # restがあるにもかかわらず、次にいけるnodeがない
    if not targets:
        return 0

    # いけるnodeがあれば、その先をチェックする
    count = 0
    for t in targets:
        new_rest = [r for r in rest_nodes if r != t]
        new_through = through + [curr_node]
        count += check_path(t, new_rest, edges_dic, new_through)

    return count


def submit():
    n, m, nodes, edges_dic = read_input()

    rest_nodes = [r for r in nodes if r != 1]
    paths = check_path(1, rest_nodes, edges_dic, [])
    print(paths)


if __name__ == '__main__':
    submit()

Submission status: Accepted

Solution code:
def find_path(x, v, e):
    if len(v) == len(e):
        return 1
    ans = 0
    for xi in e[x - 1]:
        if xi in v:
            continue
        vi = v + [xi]
        ans += find_path(xi, vi, e)
    return ans

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

Submission status: Accepted

Solution code:
import copy
n,m = map(int,input().split(' '))
route = [[]for i in range(n+1)]
already = [0 for i in range(n+1)]
already[0:2]=[1,1]
cnt=0

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

def trace(index,already):
    global cnt
    # print(index,already)
    if not(0 in already):
        cnt += 1
    else:
        for new_point in route[index]:
            if already[new_point]!=1:
                new_already = copy.copy(already)
                new_already[new_point] = 1
                trace(new_point,new_already)

trace(1,already)

print(cnt)

Submission status: Accepted

Solution code:
from itertools import permutations

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

nodes = list(range(N))
paths = [[0] * N for i in range(N)]

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

ans = 0

for p in permutations(nodes[1:],len(nodes)-1):
	cnt = 0
	for j in range(len(p)):
		if(j == 0):
			nb = 0
			nn = p[j]
		else:
			nb = p[j-1]
			nn = p[j]
		if(paths[nb][nn] == 1):
			cnt = cnt + 1
		else:
			break
		if(cnt == len(p)):
			ans = ans + 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations


def calcpath(nodes, edges):
    start = nodes[0]
    pattern = permutations(nodes[1:])

    count = 0
    for p in pattern:
        path = [start] + list(p)
        for i in range(len(path) - 1):
            if edges[path[i]][path[i+1]] != 1:
                break
            if i + 1 == len(path) - 1:
                count += 1

    return count


def main():
    n, m = list(map(int, input().split()))
    nodes = [i for i in range(n)]
    edges = [[0 for i in range(n)] for _ in range(n)]
    for _ in range(m):
        a, b = list(map(int, input().split()))
        edges[a - 1][b - 1] = 1
        edges[b - 1][a - 1] = 1
    print(calcpath(nodes, edges))


main()

Submission status: Accepted

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

dict_path = {}
path = []

for i in range(M):
    a, b = input().split()
    path.append((a, b))
    path.append((b, a))

for i in range(1, N+1):
    tmp = []
    for j in path:
        a, b = j
        if a == str(i):
            tmp.append(b)
    dict_path[str(i)] = tmp

stack = ['1']
root = ['1']

ans = 0
while stack:
    path = stack.pop(-1)
    now = path[-1]
    for i in dict_path[now]:
        tmp = path
        if i not in path:
            tmp += i
            if tmp not in root:
                stack.append(tmp)
                root.append(tmp)
                if len(tmp) == N:
                    ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools

N, M = map(int, input().split(" "))
edge = [[False]*N for _ in range(N)]

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

ans = 0

for i in itertools.permutations(range(1,N)):
    P = (0,) + i
    flag = True
    for j in range(len(P)-1):
        if edge[P[j]][P[j+1]] == False:
            flag = False
            break
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

ans=0
for i in itertools.permutations(list(range(n))):
  if i[0]!=0:
    continue
  flg=True
  for j in range(len(i)-1):
    if path[min(i[j],i[j+1])][max(i[j],i[j+1])]==False:
      flg=False
      break
  if flg:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
g = [[] for i 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)

def dfs(s, path):
    if len(path) == n:
        return 1
    cnt = 0
    for next in g[s]:
        if next in path:
            continue
        cnt += dfs(next, path + [next])
    return cnt

print(dfs(0, [0]))

Submission status: Accepted

Solution code:
import itertools
N, M = map(int, input().split())
A = [set(map(int, input().split())) for _ in range(M)]
ans = 0
for p in itertools.permutations(range(2, N+1)):
    q = list(p) + [1]
    for i in range(N-1):
        if not {q[i], q[i+1]} in A:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import copy

N,M = list(map(int,input().rstrip().split()))
sides = []
for i in range(M):
    ab = list(map(int,input().rstrip().split()))
    sides.append(ab)
    ba = [ab[1],ab[0]]
    sides.append(ba)

explored = [False for i in range(N+1)]
explored[0] = True
explored[1] = True

def explore(currentposition,flg):
    count = 0
    if all(flg):
        return 1
    for p in sides:
        if p[0] == currentposition and flg[p[1]]==False:
            tmp_flg = copy.deepcopy(flg)
            tmp_flg[p[1]] = True
            count += explore(p[1],tmp_flg)
    return count

print(explore(1,explored))

Submission status: Accepted

Solution code:
import numpy as np
N, M = map(int, input().split())

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

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

# print(Node)
Check = [0]*N
Check[0] = 1
ans = 0

def TreeSearch(x):
    # print('x={}:  '.format(x), end='')
    for i in Node[x]:
        # print('i={} '.format(i), end='')
        if Check[i] == 0:
            Check[i] = 1
            # print('  Check =', Check)
            if np.prod(Check) == 1:
                global ans
                ans += 1
                # print('ans=', ans)
                # print()
            TreeSearch(i)
            Check[i] = 0
            # print('modori from {}:  Check = {}'.format(i, Check))
           
TreeSearch(0)
print(ans)

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def 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 pf(s): return print(s, flush=True)

N,M=LI()
AB=[LI() for i in range(M)]
ans=0
L = list(itertools.permutations(range(2,N+1)))
#print(L)
for l in L:
	for lidx in range(len(l)):
		if lidx == 0:
			if [1,l[lidx]] not in AB:
				break
			continue
		
		if [l[lidx-1],l[lidx]] not in AB and [l[lidx],l[lidx-1]] not in AB:
			break
	else:
		ans+=1
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

n, m = list(map(int, input().split()))
mat = [[False] * n for i in range(n)]
for i in range(m):
    a, b = list(map(int, input().split()))
    mat[a - 1][b - 1] = mat[b - 1][a - 1] = True
ans = 0
for pat in permutations(range(n)):
    if pat[0] != 0:
        continue
    f = True
    for i in range(n - 1):
        if not mat[pat[i]][pat[i + 1]]:
            f = False
    if f:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
A = list(map(int,input().split()))
N = A[0]
M = A[1]

L = [[] for i in range(N)]
for i in range(M):
    X,Y = map(int,input().split()) 
    L[X-1].append(Y-1)
    L[Y-1].append(X-1)

#print(L)

def hitohudegaki(i,done):
    pattern = 0
    
    if i in done:
        return 0
    
    elif len(done) == N-1:
        return 1
    
    for j in range(len(L[i])):
        pattern += hitohudegaki(L[i][j],done+[i])
            
    return pattern



print(hitohudegaki(0,[]))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
l = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    l[a-1].append(b-1)
    l[b-1].append(a-1)
def dfs(i,done):
    ret = 0
    if i in done:
        return 0
    if len(done)==n-1:
        return 1
    for j in range(len(l[i])):
        ret += dfs(l[i][j],done+[i])
    return ret
print(dfs(0,[]))

Submission status: Accepted

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

ans = 0
def dfs(visited, v):
    global ans
    nvisited = visited[:]
    nvisited.append(v)
    if len(nvisited) == n:
        ans += 1
    for item in edge[v]:
        if item not in nvisited:
            dfs(nvisited, item) 

dfs([], 0)
print(ans)

Submission status: Accepted

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

flag = [False] * n
flag[0] = True
ans = 0

def dfs(x):
    global ans
    if all(flag):
        ans += 1
    for j in edge[x]:
        if not flag[j]:
            flag[j] = True
            dfs(j)
            flag[j] = False

dfs(0)
print(ans)

Submission status: Accepted

Solution code:
def search(i, bit):
  global ans
  if i<0 or i>=N:
    return;
  else:
    bit |= (1<<i)
  if bit == (1<<N)-1:
    ans += 1
    return
  else:
    for j in A[i]:
      if bit&(1<<j) == 0:
        search(j, bit)
    return
        

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

search(0, 0)

print(ans)

Submission status: Accepted

Solution code:
def dfs(now,depth):
    if use[now]:
        return 0

    if depth==n:
        return 1

    use[now]=1
    ans=0

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

    use[now]=0
    return ans

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

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

use=[0]*n

print(dfs(0,1))

Submission status: Accepted

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

ans = 0

def dfs(v=0,visited=[0]*N):
    visited[v] = 1
    if all(visited):
        global ans
        ans += 1
        return
    for nv in ad[v]:
        if visited[nv] == 1: continue
        dfs(nv,visited[:])

dfs()
print(ans)

Submission status: Accepted

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

ans = 0

def dfs(v=0,visited=[0]*N):
    visited[v] = 1
    if all(visited):
        global ans
        ans += 1
        return
    for nv, bit in enumerate(ad[v]):
        if bit == 0 or visited[nv] == 1: continue
        dfs(nv,visited[:])

dfs()
print(ans)

Submission status: Accepted

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

ans = 0

def dfs(v=0,d=0,visited=[1]+[0]*(N-1)):
    if d == N-1:
        global ans
        ans += 1
        return
    for nv, bit in enumerate(ad[v]):
        if bit == 0: continue
        if visited[nv] == 1: continue
        visited[nv] = 1
        dfs(nv,d+1)
        visited[nv] = 0

dfs()
print(ans)

Submission status: Accepted

Solution code:
import itertools
import collections

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:
# coding: utf-8
# Your code here!
import itertools
N,M=map(int,input().split())
path=[[False]*N for _ in range(N)]
for i in range(M):
    a,b=[int(j) for j in input().split()]
    path[a-1][b-1]=True
    path[b-1][a-1]=True
ans=0
for junjo in itertools.permutations(range(1,N)):
    nexts=list(junjo)
    if path[0][nexts[0]]==False:continue
    if all([path[nexts[i]][nexts[i+1]] for i in range(N-2)]):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, raw_input().split())
graph = []
for i in range(0, N):
	lst = []
	for j in range(0, N):
		lst.append(False)
	graph.append(lst)
for i in range(0, M):
	a, b = map(int, raw_input().split())
	graph[a-1][b-1] = True
	graph[b-1][a-1] = True
memo = []
for i in range(0, N):
	memo.append(True)
queue = [[0, memo]]
cnt = 0
while queue != []:
	now = queue.pop(0)
	newmemo = []
	for i in range(0, N):
		if i == now[0]: newmemo.append(False)
		else: newmemo.append(now[1][i])
	if True not in newmemo: cnt += 1
	else:
		for i in range(0, N):
			if graph[now[0]][i] and newmemo[i]:
				queue.append([i, newmemo])
print cnt

Submission status: Accepted

Solution code:
import sys

def f(G, start, visited):
    cnt = 0
    n = len(G)
    visited_ = visited + [start]

    if len(visited_) == n:
        return 1

    next_node = set(G[start]) - set(visited_)
    if len(next_node) == 0:
        return 0

    for nn in next_node:
        cnt += f(G, nn, visited_)

    return cnt


def main():
    input = sys.stdin.readline
    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)

    cnt = f(G, 0, [])

    return cnt


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

Submission status: Accepted

Solution code:
import itertools

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

line = [[0 for i in range(n)] for j in range(n)]

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

ans = 0

p = [i for i in range(1, n)]

for x in itertools.permutations(p):
    x = list(x)
    x.insert(0,0)
    for i in range(n-1):
        if not line[x[i]][x[i+1]]:
            break
        if i == n-2:
            ans += 1

print(ans)

Submission status: Accepted

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

line = [[0 for i in range(n)] for j in range(n)]


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

stack = [0]
visited = [[0]]
ans = 0

while stack:
    p = stack.pop()
    v = visited.pop()
    for i in range(n):
        if line[p][i]:
            if i not in v:
                if len(v) == n-1:
                    ans += 1
                else:
                    stack.append(i)
                    v.append(i)
                    visited.append([x for x in v])
                    v.pop()

print(ans)

Submission status: Accepted

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

import itertools
ans = 0
for p in itertools.permutations(range(n)):
    if p[0] == 0:
        flag = True
        for i in range(n-1):
            if not p[i+1] in l[p[i]]:
                flag = False
        if flag:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
L = [[] for i in range(N)]
for i in range(M):
    a,b = map(int, input().split())
    L[a-1].append(b-1)
    L[b-1].append(a-1)
    
import itertools
count = 0
for p in itertools.permutations(range(N)):
    if p[0] == 0:
#         print("p",p)
        flag = True
        for i in range(N-1):
#             print(p[i+1], L[p[i]])
            if not p[i+1] in L[p[i]]:
                flag = False
#             print(flag)
        if flag:
            count += 1
print(count)

Submission status: Accepted

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

visited = [False]*N

ans = 0
import copy

def dfs(node, visited):
    global ans
    v = copy.copy(visited)
    if v[node]:
        return
    v[node] = True
    if all(v):
        ans += 1
    else:
        cands = graph[node]
        for cand in cands:
            dfs(cand, v)

dfs(0, visited)
print(ans)

Submission status: Accepted

Solution code:
import sys
import collections
ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
nsl = lambda: map(str, sys.stdin.readline().split())

n, m = nm()
lis = [[] for i in range(n)]
for i in range(m):
    a, b = nm()
    lis[a - 1].append(b)
    lis[b - 1].append(a)
visited = [0] * n


def dfs(v, n, visited):
    count = 1
    for i in range(n):
        if visited[i] == 0:
            count = 0
    if count == 1:
        return 1
    res = 0
    for i in lis[v]:
        if visited[i - 1] == 1:
            continue
        visited[i - 1] = 1
        res += dfs(i - 1, n, visited)
        visited[i - 1] = 0
    return res


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

Submission status: Accepted

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

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

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


path=[i for i in range(2,n+1)]

visited=[1]+[0]*(n-1)

def dfs(v):
    if visited==[1]*n:
        return 1
    res=0
    for x in X[v]:
        if visited[x]==0:
            visited[x]=1
            res+=dfs(x)
            visited[x]=0
    return res

print(dfs(0))

Submission status: Accepted

Solution code:
from functools import reduce
import math
import itertools

def main():
    # N! を求める
    # f = math.factorial(N)
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    # 1e10

    # 初期値用:十分小さい数(-100億)
    # -1e10
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N,M = (int(_) for _ in input().split())
    a = []
    b = []
    for i in range(M):
        c, d = (int(_) for _ in input().split())
        a.append(c)
        b.append(d)
    l = list(_ for _ in range(2,N+1))
    d = []
    for elem in itertools.permutations(l,len(l)):
        elem = list(elem)
        elem.insert(0,1)
        d.append(elem)
    ans = 0
    for l1 in d:
        flag = True
        for i in range(len(l1)-1):
            for j in range(M):
                if(a[j]==l1[i] and b[j] ==l1[i+1]) or (b[j]==l1[i] and a[j] ==l1[i+1]):
                    flag = True
                    break
                flag = False
            if flag == False:
                break
        if flag:
            ans += 1

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

Submission status: Accepted

Solution code:
import itertools

def is_edge_exists(node1, node2, edges):
	for edge in edges:
		if node1 in edge and node2 in edge:
			return True
	return False

def route_count(route, edges):
	if route[0]!=1:
		return 0
	for i in range(len(route)-1):
		if not is_edge_exists(route[i], route[i+1], edges):
			return 0
	return 1

N, M = map(int, input().split())
edges = [list(map(int, input().split())) for i in range(M)]
nodes = [i+1 for i in range(N)]
routes = list(itertools.permutations(nodes))

ans = 0
for route in routes:
	ans += route_count(route, edges)
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
L = [[] for i in range(N)]
for i in range(M):
    a,b = map(int, input().split())
    L[a-1].append(b-1)
    L[b-1].append(a-1)
    
import itertools
s = [int(i) for i in range(N)]
count = 0
for p in itertools.permutations(s, N):
#     print("p",p)
    if p[0] == 0:
#         print("Yes")
        flag = True
        for i in range(N-1):
#             print(p[i+1])
#             print(L[p[i]])
            if p[i+1] not in L[p[i]]:
                flag = False
        if flag:
#             print("flag!!")
            count += 1
print(count)