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:
def solve(N, M, Es):
    al = {}
    for e in Es:
        al.setdefault(e[0], []).append(e[1])
        al.setdefault(e[1], []).append(e[0])

    ans = 0
    q = [(1, [1])]
    while len(q) > 0:
        current, history = q.pop()
        nexts = al[current] if current in al else []
        if len(history) == N:
            ans += 1
        for n in nexts:
            if n not in history:
                nhist = history[:]
                nhist.append(n)
                q.append((n, nhist))
    return ans


if __name__ == "__main__":
    N, M = map(int, input().split(" "))
    Es = []
    for _ in range(M):
        Es.append(tuple(map(int, input().split(" "))))
    print(solve(N, M, Es))

Submission status: Accepted

Solution code:
#こんなんでいいのかな
import sys
def 解():
    iN,iM = [int(_) for _ in input().split()]
    aData = [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]
    def addPath(d,a,b):
        if a in d:
            d[a].add(b)
        else:
            d[a]={b}
    dT = {}
    for a,b in aData:
        addPath(dT,a,b)
        addPath(dT,b,a)

    def dfs(dT,iStart,iC):
        if len(dsVisited) == iN:
            iC += 1
            return iC
        for i in dT[iStart] - dsVisited:
            dsVisited.add(i)
            iC = dfs(dT,i,iC)
            dsVisited.remove(i)
        return iC

    dsVisited = {1}
    print(dfs(dT,1,0))
解()

Submission status: Accepted

Solution code:
from itertools import permutations
def inpl(): return [int(i) for i in input().split()]

N, M = inpl()
path = [[False]*N for _ in range(N)]


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

ans = 0
for i in permutations(range(1,N)):
    visited = 0
    for j in i:
        if not path[visited][j]:
            break
        visited = j
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
N, M = map(int, input().split())
A = []
for i in range(M):
    a, b = map(int, input().split())
    A += [[a, b]]
L = list(range(2, N+1))
count = 0
for v in itertools.permutations(L):
    v = list(v)
    v.insert(0, 1)
    BOOL = 'T'
    i = 0
    while BOOL == 'T' and i < N-1:
        if sorted(v[i:i+2]) in A:
            i += 1
        else:
            BOOL = 'F'
    if BOOL == 'T':
        count += 1
print(count)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(250010)

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

def dfs(v):
    global ans
    if all(x==1 for x in node):
        ans+=1
        return

    adj=[]
    for i in ab:
        if i[0]==v+1 and node[i[1]-1]==0:
            adj.append(i[1])
        if i[1]==v+1 and node[i[0]-1]==0:
            adj.append(i[0])
    for i in adj:
        node[i-1]=1
        dfs(i-1)
        node[i-1]=0
    return

dfs(0)
print(ans)

Submission status: Accepted

Solution code:
import itertools

n, m = [int(_) for _ in input().split(' ')]
edges = set()
for _ in range(m):
    a, b = [int(_) for _ in input().split(' ')]
    edges.add((a, b))
    edges.add((b, a))

answer = 0
for vertices in itertools.permutations(range(2, n + 1)):
    steps = [1] + list(vertices)
    if all([(steps[i], steps[i + 1]) in edges for i in range(n - 1)]):
        answer += 1
print(answer)

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = map(int, raw_input().split())
edge = [[False] * N for i in range(N)]

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

def func(num, used):
    if not True in used:
        return 1
    ret = 0
    for i in range(N):
        if used[i] and edge[num][i]:
            used[i] = False
            ret += func(i, used)
            used[i] = True
    return ret

print func(0, [False] + [True] * (N - 1))

Submission status: Accepted

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

result = []
stack = []

def path(start, visited):
    if len(visited) >= N:
        result.append(visited[:])
        exit
    stack.append(start)
    if len(stack) > 0:
        nextpoint = stack.pop()
        if nextpoint not in visited:
            visited.append(nextpoint)
            for i in range(M):
                if A[i][0] == start:
                    path(A[i][1], visited)
                if A[i][1] == start:
                    path(A[i][0], visited)
            visited.pop()

path(1, [])
result = list(map(list, set(map(tuple, result))))
print(len(result))

Submission status: Accepted

Solution code:
import itertools

N,M=map(int,input().split())
link = [set() for _ in range(N+1)]
for _ in range(M):
    a,b = map(int,input().split())
    link[a].add(b)
    link[b].add(a)
sqs = itertools.permutations(range(2,N+1))
ans = 0
for sq in sqs:
    v = 1
    success = 1
    for w in sq:
        if w in link[v]:
            v = w
        else:
            success = 0
            break
    ans += success
print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m = map(int,input().split())
a = []
c = 0
for _ in [0]*m:
  a += [list(map(int,input().split()))]
for x in list(itertools.permutations(range(2,n+1))):
  y = [1] + list(x)
  f = True
  for i in range(1,n):
    if (not [y[i-1],y[i]] in a) and (not [y[i],y[i-1]] in a):
      f = False
      break
  if f:
    c += 1
print(c)

Submission status: Accepted

Solution code:
from itertools import permutations

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

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

# 頂点を訪れる順番を全通り試す
ans = 0
for vs in permutations(range(1, N)):
    vs = [0] + list(vs)
    for i in range(N - 1):
        if adjM[vs[i]][vs[i + 1]] == 0:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def dfs(v, n, visited, g):
    if False not in visited:
        return 1

    result = 0

    for i in range(n):
        if not g[v][i]:
            continue
        if visited[i]:
            continue
        visited[i] = True
        result += dfs(i, n, visited, g)
        visited[i] = False

    return result


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

visited = [False] * n
visited[0] = True
print(dfs(0, n, visited, g))

Submission status: Accepted

Solution code:
def getN():
    return int(input())


def getNM():
    return map(int, input().split())


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

def tansaku(already, paths, cur, n):
    global ans
    aim = [i for i in paths[cur] if i not in already]
    #print(cur,aim,already,ans)
    if aim == []:
        if len(already) == n-1:
            #print("here")
            ans += 1
        return

    for a in aim:
        tansaku(already+[cur], paths, a, n)

N, M = getNM()
paths = [[] for i in range(N)]
ans = 0
for i in range(M):
    a, b = getNM()
    paths[a-1].append(b-1)
    paths[b-1].append(a-1)

tansaku([], paths, 0, N)
print(ans)

Submission status: Accepted

Solution code:

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

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

for i in range(m):
  s,t = map(int,input().split())
  edges[s-1].append(t-1)
  edges[t-1].append(s-1)

cnt =[0]

def dfs(V,s):
  V[s]=1
  if sum(V)==n:
    cnt[0]+=1
  else:
    for adj in edges[s]:
      if V[adj] == 0:
        dfs(V[:adj] + [1] + V[adj + 1:], adj)
dfs([0] * n, 0)
print(cnt[0])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = []
b = []
ans = 0
for i in range(M):
    x, y = map(int, input().split())
    a.append(x)
    b.append(y)

current_num = 1
fin_li = [1]
s_li = [[current_num,fin_li]]
while len(s_li) > 0:
    if len(s_li[0][1]) == N:
        ans += 1
    else:
        next_li = [b[i] for i, x in enumerate(a) if x == s_li[0][0]]
        next_li += [a[i] for i, x in enumerate(b) if x == s_li[0][0]]
        next_li = [[x, s_li[0][1]+[x]] for x in next_li if not x in s_li[0][1]]
        s_li += next_li
    s_li.pop(0)

print(ans)

Submission status: Accepted

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

def dfs(v, cnt):
    if vis[v]:
        return 0
    vis[v] = True
    cnt += 1
    ka = 0
    for x in adjs[v]:
        ka += dfs(x, cnt)
    if cnt == N:
        ka = 1
    vis[v] = False
    return ka

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

Submission status: Accepted

Solution code:
import itertools

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

t = [i for i in range(1,n+1)]
testcase = list(itertools.permutations(t))
counter = 0
for i in range(len(testcase)):
    if testcase[i][0] != 1:
        break
    else:
        temp = True
    now = 1
    for k in range(1,n):
        if testcase[i][k] not in graph[now]:
            temp = False
            break
        else:
            now = testcase[i][k]
    if temp:
        counter += 1

print(counter)

Submission status: Accepted

Solution code:
ans=0

def dfs(pos, open):
    if open.count(False)==len(arr):
        global ans
        ans+=1

    for i in range(2,N+1):
        if c[pos][i] and open[i]:
            open_next=open.copy()
            open_next[i]=False
            dfs(i, open_next)

N,M=map(int,input().split())
c=[[False for j in range(N+1)] for i in range(N+1)]
for i in range(M):
    a,b=map(int,input().split())
    c[a][b]=c[b][a]=True

arr=[True for i in range(N+1)]
arr[0]=arr[1]=False
dfs(1, arr)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
N, M = map(int, input().split())
E = [[False]*N for _ in range(N)]
for _ in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    E[a][b] = E[b][a] = True
ans = 0
for t in permutations(range(1, N)):
    pv = 0
    for v in t:
        if not E[pv][v]:
            break
        pv = v
    else:
        ans += 1
print(ans)

Submission status: Accepted

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

#print(s) #[[1, 2], [1, 3], [2, 3]]

t=list(permutations(list(range(1,N+1))))

##print(t) [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

for i in range(len(t)):
    flag=True
    if t[i][0]!=1: continue #1スタートのみ。continue文はfor文やwhile文などループ内の処理をスキップ
    for j in range(N-1):
        a=sorted([t[i][j],t[i][j+1]]) #(1,2,3)なら[(1,2)]や[(2,3)]
        #print(i)# 0 0 1 1
        #print(j)# 0 1 0 1
        #print(a)# [1, 2] [2, 3] [1,3] [2,3]
        if a not in s: flag=False
    if flag == True:
        ans = ans + 1

print(ans)

Submission status: Accepted

Solution code:
def DFS(Current_Node,Visited_Node):
    if len(Visited_Node) == N - 1:
        return 1
    ans = 0

    for a,b in AB:
        if a == Current_Node and b not in Visited_Node:
            vns = Visited_Node.copy()
            vns.add(a)
            ans += DFS(b, vns)

        if b == Current_Node and a not in Visited_Node:
            vns = Visited_Node.copy()
            vns.add(b)
            ans += DFS(a,vns)
    return ans



N,M = map(int,input().split())
AB = []

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

ans = DFS(1,set())
print(ans)

Submission status: Accepted

Solution code:
def f(currentNode, visitedNodeSet):
    if len(visitedNodeSet) == N - 1:
        return 1
    sum = 0
    for a, b in AB:
        if (a == currentNode) and (b not in visitedNodeSet):
            vns = visitedNodeSet.copy()
            vns.add(a)
            sum += f(b, vns)
        if (b == currentNode) and (a not in visitedNodeSet):
            vns = visitedNodeSet.copy()
            vns.add(b)
            sum += f(a, vns)
    return sum


N, M = [int(x) for x in input().split()]
AB = []

for i in range(M):
    a, b = [int(x) for x in input().split()]
    AB.append((a, b))

# print(AB)

print(f(1, set()))

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())
  G[a - 1].append(b - 1)
  G[b - 1].append(a - 1)
cnt = [0]
def dfs(V, s):
  V[s] = 1
  if sum(V) == N:
    cnt[0] += 1
  else:
    for adj in G[s]:
      if V[adj] == 0:
        dfs(V[:adj] + [1] + V[adj + 1:], adj)
dfs([0] * N, 0)
print(cnt[0])

Submission status: Accepted

Solution code:
import itertools

n_m_input = list(map(int, input().split()))
n = n_m_input[0]
m = n_m_input[1]

all_point_string = ''.join([str(i+1) for i in range(n-1)])
path_string_list = list(itertools.permutations(all_point_string))

edge_list = [[0]*n for _ in range(n)]
counter = 0
answer = 0

for _ in range(m):
	edge = list(map(int, input().split()))
	edge_list[edge[0]-1][edge[1]-1] = 1
	edge_list[edge[1]-1][edge[0]-1] = 1

for path in path_string_list:
	counter = 0
	path_str = '0'+''.join(path)
	for i in range(n-1):
		if edge_list[int(path_str[i])][int(path_str[i+1])] == 1:
			counter += 1
	if counter == n-1:
		answer += 1

print(answer)

Submission status: Accepted

Solution code:
cnt = 0

def dfs(v, n, used, linked_list):
    global cnt
    if len(used) == n:
        cnt += 1
        return
    else:
        for next_v in linked_list[v]:
            if next_v not in used:
                used.append(next_v)
                dfs(next_v, n, used, linked_list)
                used.remove(next_v)
        return

def main():
    global cnt
    n, m = map(int, input().split())
    linked_list = [[] for _ in range(n+1)]
    for i in range(m):
        a, b = map(int, input().split())
        linked_list[a].append(b)
        linked_list[b].append(a)
    used = [1]
    dfs(1, n, used, linked_list)
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Visited = [False for i in range(N)]
Visited[0] = True
ans = 0
def DFS(i):
    allvisited = True
    for j in range(N):
        if Visited[j] == False:
            allvisited = False
    if allvisited:
        return 1
    else:
        ret = 0
        for node in Edge[i]:
            if Visited[node] == False:
                Visited[node] = True
                ret += DFS(node)
                Visited[node] = False
        return ret

print(DFS(0))

Submission status: Accepted

Solution code:
import itertools

n, m = map(int, input().split())
graph = [[0 for i in range(n)] for j in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    graph[a - 1][b - 1] = 1
    graph[b - 1][a - 1] = 1
ans = 0
for i in itertools.permutations(range(2, n + 1)):
    if not graph[0][i[0] - 1]:
        continue
    for j in range(n - 1):
        if j == n - 2:
            ans += 1
            break
        if not graph[i[j] - 1][i[j + 1] - 1]:
            break
print(ans)

Submission status: Accepted

Solution code:
import itertools

def sonzai(path, start, goal):
    for i in path:
        if start in i:
            if start > goal:
                if i[0] == goal:
                    return True
            else:
                if i[1] == goal:
                    return True
    return False

n, m = map(int, input().split())
path = []
for i in range(m):
    a, b = map(int, input().split())
    path.append([a, b])
ans = 0
for i in itertools.permutations(range(2, n + 1)):
    if not sonzai(path, 1, i[0]):
        continue
    for j in range(n - 1):
        if j == n - 2:
            ans += 1
            break
        if not sonzai(path, i[j], i[j + 1]):
            break
print(ans)

Submission status: Accepted

Solution code:


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

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

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

def search(v,edge,cl,count):
    come_list = cl[:]
    come_list[v-1]=1
    if sum(come_list)==N:
         return count+1
    else:
        for e in edge[v-1]:
            if come_list[e-1]==0:
                count=search(e,edge,come_list,count)
    return count
            
cl = [0 for i in range(N)]
print search(1,edge,cl,0)

Submission status: Accepted

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

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

for i in range(M):
    graf[a[i] - 1].append(b[i] - 1)
    graf[b[i] - 1].append(a[i] - 1)

cnt = 0

def sarch(v, graf_check):
    global cnt
    check = list(graf_check)
    check[v] = 1
    #print(v, graf_check)
    if sum(check) == N:
        cnt += 1
    else:
        for i in graf[v]:
            if graf_check[i] == 0:
                sarch(i, check)
                
sarch(0, [0 for i in range(N)])
print(cnt)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def main():
    N, M = map(int, input().split())

    g = [[False] * N for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        g[a][b] = True
        g[b][a] = True

    ans = 0
    for p in permutations(range(1, N)):
        now = 0
        ok = True
        for n in p:
            ok &= g[now][n]
            now = n
        ans += ok

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#-*-coding:utf-8-*-
from collections import deque

ans = 0

def dfs(v, n, used, linked_list):
    global ans
    if len(used) == n:
        ans += 1
        return
    else:
        for next_v in linked_list[v]:
            if next_v not in used:
                used.append(next_v)
                dfs(next_v, n, used, linked_list)
                used.remove(next_v)
        return

def main():
    global ans
    n, m = map(int, input().split())
    linked_list = [[] for _ in range(n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        linked_list[a].append(b)
        linked_list[b].append(a)
    used = [1]
    dfs(1, n, used, linked_list)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

graph = [ [False] * 8 for _ in range(8) ]
visited = [False] * n

def dfs(a, N, visited):
    finish = True
    for i in range(N):
        if not visited[i]:
            finish = False
    if finish:
        return 1
    ans = 0
    for i in range(N):
        if not graph[a][i] or visited[i]:
            continue
        visited[i] = True
        ans += dfs(i,N,visited)
        visited[i] = False
    return ans

for i in range(m):
    graph[ab[i][0]-1][ab[i][1]-1], graph[ab[i][1]-1][ab[i][0]-1] = True, True

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

Submission status: Accepted

Solution code:
import copy

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

class Node:
    def __init__(self, id):
        self.id = id
        self.path = []
    def __str__(self):
        return "id: " + str(self.id) + " path: " + str(self.path)

nodes = []
for i in range(N):
    nodes.append(Node(i))

for i in range(M):
    from_id, to_id = [ int(x) - 1 for x in input().split() ]
    nodes[from_id].path.append(to_id)
    nodes[to_id].path.append(from_id)

def if_all_passed(passed_nodes):
    if len(passed_nodes) == N:
        return True
    else:
        return False

def go_child(id_new, passed_nodes):
    passed_nodes.append(id_new)
    if if_all_passed(passed_nodes):
        return 1

    count = 0
    for i in nodes[id_new].path:
        if not i in passed_nodes:
            count += go_child(i, copy.deepcopy(passed_nodes))
    return count

count = go_child(0, [])
print(count)

Submission status: Accepted

Solution code:
import sys
import numpy as np

N, M = [int(i) for i in sys.stdin.readline().split()]
edges = [[] for _ in range(N)]
for l in sys.stdin.readlines():
  a, b = [int(i)-1 for i in l.strip().split()]
  edges[a].append(b)
  edges[b].append(a)

def search(p, current_paths):
  #print(current_paths)
  finished_paths = [path for path in current_paths if p in path and len(path) == N]
  unfinished_paths = [tuple(list(path) + [p]) for path in current_paths if p not in path]
  if not unfinished_paths:
    return finished_paths

  paths = []
  for target in edges[p]:
    new_paths = search(target, unfinished_paths)
    paths += new_paths
  paths += finished_paths
  return set(paths + finished_paths)
  
res = search(0, [()])
print(len(res))

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy
import heapq
import math

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


count = 0

def dfs(N, adj_list, nd, visit_num, is_visit):
    global count
    is_visit[nd] = True
    if visit_num == N:
        count += 1
    for adj in adj_list[nd]:
        if is_visit[adj] == False:
            dfs(N, adj_list, adj, visit_num + 1, is_visit)
            is_visit[adj] = False


def main():
    global count
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [long(input_raw[0]), long(input_raw[1])]
    adj_list = {}
    for i in range(M):
        input_raw = read_func().strip().split()
        [a, b] = [long(input_raw[0]), long(input_raw[1])]
        if a not in adj_list:
            adj_list[a] = [b]
        else:
            adj_list[a].append(b)

        if b not in adj_list:
            adj_list[b] = [a]
        else:
            adj_list[b].append(a)
    is_visit = [False for i in range(N + 1)]

    dfs(N, adj_list, 1, 1, is_visit)

    print count






if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
import math

# K = int(input())
# A, B = map(int, input().split())
# A = list(map(int, input().split()))

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

edges = []
E = np.zeros((N, N), dtype=int)

for m in range(M):
    s, t = map(int, input().split())
    s = s - 1
    t = t - 1
    E[s][t] = 1
    E[t][s] = 1

# print('edge=', E)


def count(path, E):
    if len(path) == N:
        return 1
    else:
        edges = []
        cur = path[-1]
        ret = 0
        for n in range(N):
            if E[cur][n] == 1 and n not in path:
                npath = path + [n]
                ret += count(npath, E)
        return ret

ret = count([0], E)
print(ret)

Submission status: Accepted

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

E = [list(map(int, input().split())) for i in range(M)]

visited = [0] * N
visited[0] = 1

ans = 0

def DFS(v,cnt):
  #print("call",v,cnt,visited)
  if sum(visited) == N:
    cnt += 1
    return cnt
  for i in range(M):
    if E[i][0] == v + 1:
      v_next = E[i][1] - 1
    elif E[i][1] == v + 1:
      v_next = E[i][0] - 1
    else:
      continue
    
    if visited[v_next] == 1:
      continue
    
    #print("deppen",v, v_next,visited)
    visited[v_next] = 1
    cnt = DFS(v_next,cnt)
    visited[v_next] = 0
    
  return cnt

ans = DFS(0,0)

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
n, m = map(int, input().split())
pair = [tuple(map(int, input().split())) for i in range(m)]
num = [i for i in range(1,n+1)]
ans = 0
for p in permutations(num):
    if p[0] != 1:
        continue
    already = []
    state = True
    for i in range(n-1):
        if p[i] in already:
            state = False
            break
        if (min(p[i], p[i+1]), max(p[i], p[i+1])) not in pair:
            state = False
            break
        already.append(p[i])
    if state:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
n, m = map(int, input().split())
pair = [tuple(map(int, input().split())) for i in range(m)]
num = [i+1 for i in range(n)]
box = []
for p in permutations(num):
    if p[0] == 1:
        box.append(p)
ans = 0
for p in box:
    already = []
    state = True
    for i in range(n-1):
        if p[i] in already:
            state = False
            break
        if (min(p[i], p[i+1]), max(p[i], p[i+1])) not in pair:
            state = False
            break
        already.append(p[i])
    if state:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools


def f(j, adj):
    for i, node in enumerate(j):
        if i == 0:
            if node not in adj[1]:
                return False
        else:
            if j[i - 1] not in adj[node]:
                return False
    return True


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

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

count = 0
for j in itertools.permutations(range(2, n + 1)):
    count += f(j, adj)

print(count)

Submission status: Accepted

Solution code:
f = lambda: map(int, input().split())
n,m = f()
path = [[0 for _ in range(n)] for _ in range(n)]
for _ in range(m):
    a,b = f()
    path[a-1][b-1]=path[b-1][a-1]=1

ans = 0


def dfs(pStack):
    global ans
    if len(pStack) == n:
        ans += 1
        pStack.pop()
        return
    cNode = pStack[-1]
    for nNode in range(n):
        if path[cNode][nNode] and not nNode in pStack:
            pStack.append(nNode)
            dfs(pStack)
    pStack.pop()


dfs([0])
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
E = [[0 for i in range(N)] for j in range(N)] #頂点のつながり
for i in range(M):
    a, b = map(int, input().split())
    E[a-1][b-1] = 1
    E[b-1][a-1] = 1

V = [ 0 for i in range(N)] #訪問済みの頂点が1
V[0] = 1 #頂点1は訪問済み

def DPS(now, V):
    res = 0 #全て訪問できた回数
    if 0 not in V:
        return 1
    for i in range(N): 
        if (E[now][i] == 1) and (V[i] == 0): #現在の頂点と隣接してかつ未訪問の頂点
            V[i] = 1
            res = res + DPS(i, V)
            V[i] = 0
    return res

print(DPS(0, V))

Submission status: Accepted

Solution code:
# 入力
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

from itertools import permutations

# 全探索をするのです
n,m = li()
edges = set()
for _ in range(m):
    a,b = li()
    edges.add((a,b))
    edges.add((b,a))
    
paths = permutations([str(i) for i in range(2,n+1)],n-1)
cnt = 0
for path in paths:
    path = [1] + [int(i) for i in path]
    
    exist = True
    for i in range(n-1):
        if not (path[i], path[i+1]) in edges:
            exist = False

    if exist:
        cnt += 1
        
print(cnt)

Submission status: Accepted

Solution code:
import itertools
N,M = map(int,input().split())
src = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]

es = [set() for i in range(N)]
for a,b in src:
    es[a].add(b)
    es[b].add(a)

ans = 0
for ptn in itertools.permutations(range(1,N)):
    v = 0
    for to in ptn:
        if to not in es[v]:
            break
        else:
            v = to
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m= map(int,input().split())
a = [input().rstrip().split() for j in range(m)]
cnt = 0#現在の経路
# a
visited=[False]*n#もう訪問したか
graph = [[False for i in range(n)] for j in range(n)]#どこが連結されているか
# graph
for i in range(0,m):
    x = int(a[i][0])-1
    y = int(a[i][1])-1
    graph[x][y]=graph[y][x]=True
# graph
    
def DFS(v,n,visited):
    # print(visited)
    all_visited = True #bool
    for i in range(0,n):
        if(visited[i]==0):
            all_visited = False
    if(all_visited):
        return 1

    ret = 0

    for i in range(0,n):
        if(graph[v][i]==False):
            continue
        if(visited[i]):
            continue

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

    return ret
visited[0]=True
print(DFS(0,n,visited))

Submission status: Accepted

Solution code:
import itertools
na = lambda: list(map(int, input().split()))

n, m = na()
t = [[0] * 10 for _ in range(10)]
for _ in range(m):
    a, b = na()
    a -= 1
    b -= 1
    t[a][b] = t[b][a] = 1

ans = 0
for l in itertools.permutations(range(n)):
    if l[0]: continue
    flag = 1
    for i in range(1, n):
        if t[l[i]][l[i-1]] == 0:
            flag = 0
            break
    if flag:
        ans += 1

print(ans)