Problem:


Score : 300 points

Problem Statement

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

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

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

Here, the endpoints of a path are considered visited.  

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

Figure 1: an example of an undirected graph

The following path shown in Figure 2 satisfies the condition.

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

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

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

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

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

Constraints

2≦N≦8 

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

1≦a_i<b_i≦N 

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

Input

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

N M  
a_1 b_1  
a_2 b_2
:  
a_M b_M  

Output

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

Sample Input 1

3 3
1 2
1 3
2 3

Sample Output 1

2

The given graph is shown in the following figure:

The following two paths satisfy the condition:

Sample Input 2

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

Sample Output 2

1

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



Sample input:
3 3
1 2
1 3
2 3


Sample output:
2

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter

lis = []
n = 0
m = 0
ans = 0
visited = []

def dfs(i, d, fr):
    global lis, ans, visited
    if visited[i] == 1:
        return
    if d == n - 1:
        ans += 1
        return
    for j in lis[i]:
        if j != fr:
            visited[i] = 1
            # print(i+1 , j+1)
            dfs(j, d+1, i)
            visited[i] = -1


def main():
    global lis, n, m, ans, visited
    n, m = map(int, input().strip().split())
    lis = [[] for _ in range(n)]
    visited = [-1] * n
    for _ in range(m):
        a, b = list(map(lambda x: x-1, map(int, input().strip().split())))
        lis[a].append(b)
        lis[b].append(a)
    # print("##")
    dfs(0, 0, -1)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter

lis = []
n = 0
m = 0
ans = 0

def dfs(i, d, fr, used):
    global lis, ans
    if i in used:
        return
    if d == n - 1:
        ans += 1
        return
    for j in lis[i]:
        if j != fr:
            used.append(i)
            # print(i+1 , j+1)
            dfs(j, d+1, i, used)
            used.pop()


def main():
    global lis, n, m, ans
    n, m = map(int, input().strip().split())
    lis = [[] for _ in range(8)]
    for _ in range(m):
        a, b = list(map(lambda x: x-1, map(int, input().strip().split())))
        lis[a].append(b)
        lis[b].append(a)
    # print("##")
    dfs(0, 0, -1, [])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
N, M = map(int, input().split())
edge = [[False]*N for _ in range(N)]
ans = 0
for _ in range(M):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  edge[a][b] = True
  edge[b][a] = True
for i in itertools.permutations(range(N), N):
  if i[0] == 0:
    for j in range(N):
      if j == N-1:
        ans += 1
        break
      if not edge[i[j]][i[j+1]]:
        break
print(ans)

Submission status: Accepted

Solution code:
visited, g = ([], [])

def dfs(i):
    visited[i] = True
    ans = 0
    if all(visited):
        visited[i] = False
        return 1
    for j, b in enumerate(g[i]):
        if b and not visited[j]:
            ans += dfs(j)
    visited[i] = False
    return ans


def main():
    global visited, g
    n, m = [int(i) for i in input().split()]
    visited = [False for i in range(n)]
    g = [[False for i in range(n)] for j in range(n)]
    for i in range(m):
        t, f = [int(j)-1 for j in input().split()]
        g[t][f] = True
        g[f][t] = True
    print(dfs(0))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(m):
        a,b=map(lambda x:int(x)-1,input().split())
        E[a].append(b)
        E[b].append(a)
    def dfs(v,vis):
        vis[v]=1
        if all(vis): return 1
        res=0
        for u in E[v]:
            if vis[u]==0:
                nvis=vis[:]
                res+=dfs(u,nvis)
        return res
    print(dfs(0,[0]*n))
resolve()

Submission status: Accepted

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

s = [1]
count = 0
L = [[i for i in edgelist if (len(i&set([1]))!=0)]]
while s != []:
    if len(s) == N:
        count = count + 1
        L.pop()
        s.pop()
    elif L[-1] == []:
        L.pop()
        s.pop()
    else:
        p = L[-1].pop()
        r = list(p - set([s[-1]]))
        L.append([i for i in edgelist if (len(i&set(r))!=0)*(len(i&set(s))==0)])
        s.append(r[0])
print(count)

Submission status: Accepted

Solution code:
# ABC054C - One-stroke Path
from itertools import permutations as perm


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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC054C - One-stroke Path
from itertools import permutations as perm


def main():
    N, M, *A = map(int, open(0).read().split())
    E = {(i, j) for i, j in zip(A[::2], A[1::2])}
    E |= {(j, i) for i, j in zip(A[::2], A[1::2])}  # add reversed paths
    ans = 0
    for path in perm(range(2, N + 1), N - 1):  # check all possible paths (O(N!))
        path = (1,) + path
        if all((i, j) in E for i, j in zip(path, path[1:])):
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC054C - One-stroke Path
# an undirected unweighted graph is given
# -> count up paths which visit all the vertices exactly once
# exhaustive search
from itertools import permutations as perm


def main():
    N, M = tuple(map(int, input().split()))
    E = set(tuple(map(int, input().split())) for _ in range(M))  # edges
    E |= {(j, i) for i, j in E}  # undirected graph -> add reversed paths
    ans = 0
    for path in perm(range(2, N + 1), N - 1):  # check all possible paths (O(N!))
        path = (1,) + path
        if all((i, j) in E for i, j in zip(path, path[1:])):
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

import itertools

M = [[0] * (n+1) for i in range(n+1)]
for i in range(m):
    M[A[i][0]][A[i][1]] = 1
    M[A[i][1]][A[i][0]] = 1

B = list(itertools.permutations(range(2, n+1)))

#print(B)

ans = 0
for i in range(len(B)):
    pt = 0
    if M[1][B[i][0]] == 1:
        pt += 1
    else:
        continue

    for j in range(len(B[i])-1):
        if M[B[i][j]][B[i][j+1]] == 1:
            pt += 1
    # print(B[i],pt)
    if pt == n-1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools

N, M = map(int, input().split())
edges = [tuple(sorted(map(int, input().split()))) for _ in range(M)]

answer = 0
for i in itertools.permutations(range(2, N+1), N-1):
    l = [1] + list(i)
    answer += sum(1 for x in zip(l, l[1:]) if tuple(sorted(x)) in edges) == N-1
print(answer)

Submission status: Accepted

Solution code:
from itertools import permutations

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

count = 0
for p in permutations(range(1, N)):
    s = 0
    for i in p:
        if G[s][i] == 0:
            break
        else:
            s = i
    else:
        count += 1

print(count)

Submission status: Accepted

Solution code:
from itertools import permutations
n,m = map(int,input().split())
e = [tuple(sorted(map(int,input().split()))) for _ in range(m)]

ans = 0
for i in permutations(range(2, n+1), n-1):
  l = [1] + list(i)
  ans += sum(1 for j in zip(l, l[1:]) if tuple(sorted(j)) in e) == n-1

print(ans)

Submission status: Accepted

Solution code:
import copy

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

def search(s, V):
    ans = 0
    if s in V:
        return 0
    Vc = copy.copy(V)
    Vc.add(s)
    if Vc == set(list(range(1, N+1))):
        return 1
    for v in T[s]:
        ans += search(v, Vc)
    return ans

print(search(1, set()))

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)

def dfs(i, visited):
    if all(visited):
        return 1
    total = 0
    for j in graph[i]:
        if not visited[j]:
            nvisited = visited[:]
            nvisited[j] = True
            total += dfs(j, nvisited)
    return total

def main():
    """ main """
    visited = [False] * N
    visited[0] = True
    print(dfs(0, visited))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

N, M = map(int, input().split())
edges = {tuple(sorted(map(int, input().split()))) for _ in range(M)}

answer = 0
for i in itertools.permutations(range(2, N+1), N-1):
    l = [1] + list(i)
    answer += sum(1 for edge in zip(l, l[1:]) if tuple(sorted(edge)) in edges) == N-1
print(answer)

Submission status: Accepted

Solution code:
from itertools import permutations

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

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

P = []
for p in permutations(range(2, N+1)):
    tmp = [1]
    tmp.extend(list(p))
    P.append(tmp)

ans = 0
for p in P:
    for i in range(1, N):
        exist = False
        for e in E:
            if set(e) == {p[i-1], p[i]}:
                exist = True
                break
        if exist is False:
            break
    else:
        if exist is False:
            break
    if exist:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
n,m=map(int,input().split())
con=[[0]*n for _ in range(n)]
for _ in range(m):
	a,b=map(int,input().split())
	con[a-1][b-1]=con[b-1][a-1]=1
ans=0
for p in permutations(range(n)):
	if p[0]!=0:
		continue
	if all(con[x][y] for x,y in zip(p,p[1:])):
		ans+=1
print(ans)

Submission status: Accepted

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

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

    for i in range(M):
        a, b = map(int, input().split())
        link[a-1][b-1] = True
        link[b-1][a-1] = True
    
    ans = 0
    path = [i for i in range(1, N)]
    for p in permutations(path):
        if link[0][p[0]]:
            ok = True
            for i in range(N-2):
                if not link[p[i]][p[i+1]]:
                    ok = False
                    break
            if ok:
                ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools

N,M = map(int,input().split())
Data = []
for _ in range(N+1):
    Data.append([0]*(N+1))
for _ in range(M):
    a,b = map(int,input().split())
    Data[a][b] = 1
    Data[b][a] = 1

ans = 0
for r in itertools.permutations(range(2,N+1)):
    Rlist = list(r)
    a = 1
    b = Rlist[0]
    if Data[a][b] == 0:
        continue
    else:
        flag = True 
        for i in range(len(Rlist)-1):
            a = Rlist[i]
            b = Rlist[i+1]
            if Data[a][b] == 0:
                flag = False
                break
        if flag:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce




INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m = LI()
graph = [[] for _ in range(n)]
for a, b in LIR(m):
    graph[a-1] += [b-1]
    graph[b- 1] += [a - 1]



cnt = 0

for l in list(permutations(range(n), n)):
    if l[0]:
        continue
    for i in range(n-1):
        if not l[i+1] in graph[l[i]]:
            break
    else:
        cnt += 1



print(cnt)

Submission status: Accepted

Solution code:
import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

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)

def dfs(i, visited):
    if all(visited):
        return 1
    total = 0
    for ni in graph[i]:
        if not visited[ni]:
            nvisited = visited[:]
            nvisited[ni] = True
            total += dfs(ni,nvisited)
    return total


def main():
    """ main """
    visited = [False]*N
    visited[0] = True
    print(dfs(0, visited))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def tami(x, vis, cnt):
  global ans
  if cnt == N:
    ans += 1
    #print(vis)
    return
  for i in root[x]:
    if i not in vis:
      tami(i, vis+[i], cnt+1)

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

root = [[] for _ in range(N+2)]
for a,b in ab:
  root[a].append(b)
  root[b].append(a)

visited = []
ans = 0
tami(1, visited+[1], 1)
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split());L=[[]for _ in range(N+1)]
for _ in range(M):a,b=map(int,input().split());L[a]+=[b];L[b]+=[a]
def s(n,v):
 if n in v:return 0
 if len(v)==N-1:return 1
 return sum(s(i,v|{n})for i in L[n])
print(s(1,set()))

Submission status: Accepted

Solution code:
import sys
from pprint import pprint

import itertools

n, m = map(int, sys.stdin.readline().strip().split(" "))

edges = set()
for _ in range(m):
    a, b = map(int, sys.stdin.readline().strip().split(" "))
    edges.add((a, b))
    edges.add((b, a))

ans = 0
for seq in itertools.permutations([i for i in range(1,n+1)]):
    # pprint(seq)
    flag = True
    for i in range(n-1):
        # print(seq[i], seq[i+1])
        if i == 0 and seq[i] != 1:
            # print("Not start from 1")
            flag = False
            break
        if (seq[i], seq[i+1]) not in edges:
            # print("Not")
            flag = False
            break
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M=(int(i) for i in input().split())
P=[]
for i in range(M):
    P.append([int(i) for i in input().split()])


ans=0
q=[]
s=1

def func(s,Q,r):
    global ans
    for q ,P in Q:
        if r==N-1:
            ans+=1
        n_s=[i for i in q if i!=s][0]
        n_q=[]
        for p in P:
            if n_s in p:
                n_q.append([p, [_p for _p in P if n_s not in _p]])
        if len(n_q)==0:
            continue
        else:
            func(n_s, n_q, r+1)


for p in P:
    if s in p:
        q.append([p, [_p for _p in P if s not in _p]])
func(s,q,1)
print(ans)

Submission status: Accepted

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

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

def dfs(visited, now):
    tv = copy.copy(visited)
    tv[now-1] = 1
    if all(tv) == 1:
        return 1

    count = 0
    for i in graph[now]:
        if tv[i-1] == 0:
            count += dfs(tv, i)
    return count

print(dfs([0] * n, 1))

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

#2,...,nの順列を表すイテレータ
for i in itertools.permutations(range(2, n + 1), (n - 1)):
    li = [1] + list(i)
    #順列を経路とみなし、実際に辺が存在するかをcheck.辺の本数がn-1となればよい.
    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:
import itertools

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

for i in itertools.permutations(range(n),n):
    if i[0]==0:
        for j in range(n):
            if j==n-1:
                ans += 1
                break
            if not path[i[j]][i[j+1]]:
                break

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

for i in itertools.permutations(range(n), n):
    if i[0] == 0:
        for j in range(n):
            if j == n - 1:
                ans += 1
                break
            if not path[i[j]][i[j + 1]]:
                break

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
from copy import deepcopy

N,M = [int(i) for i in input().split()]
links  = set([input().strip() for _ in range(M)])

ans = 0

for path in permutations(range(2,N+1)):
    l = deepcopy(links)
    p_node = 1
    for n_node in path:
        e_l = " ".join([str(s) for s in sorted([p_node,n_node])])
        if e_l in l:
            l.remove(e_l)
            p_node = n_node
            continue
        else:
            break
    else:
        ans += 1 

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
from copy import deepcopy

N,M = [int(i) for i in input().split()]
links  = [[int(i) for i in input().split()] for _ in range(M)]

ans = 0

for path in permutations(range(2,N+1)):
    l = deepcopy(links)
    p_node = 1
    for n_node in path:
        if sorted([p_node,n_node]) in l:
            l.pop(l.index(sorted([p_node,n_node])))
            p_node = n_node
            continue
        else:
            break
    else:
        ans += 1 
print(ans)

Submission status: Accepted

Solution code:
import itertools
N,M=map(int,input().split())
edges={tuple(sorted(map(int,input().split()))) for i in range(M)}
ans=0

for i in itertools.permutations(range(2,N+1)):
    l= [1]+ list(i)
    counte = 0
    for edge in zip(l,l[1:]):
        if tuple(sorted(edge)) in edges:
            counte += 1
    if counte == N-1:
        ans+=1

print(ans)

Submission status: Accepted

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

dic = {}
for i in range(1, n+1):
  dic[i] = []
for i in range(m):
  a1, a2 = map(int, input().split())
  dic[a1] += [a2]
  dic[a2] += [a1]

def next_position(position, history, dic):
  next_you_can_move = list(set(dic[position]) - set(history))
  return next_you_can_move

def serch(position, history, dic):
  counter = 0
  if len(history) == n:
    return 1
  else:
    next_you_can_move = next_position(position, history, dic)
    if next_you_can_move == []:
      return 0
    for cand in next_you_can_move:
      new_history = history + [cand]
      counter += serch(cand, new_history, dic)
    return counter
count = serch(1, [1], dic)
print(count)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N, M = map(int, input().split())
tLst = [[] for _ in range(N)]
vLst = [0] * N

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

def dfs(n, index, v, ans):
    vLst[index] = 1
    if n == N - 1:
        ans += 1
        return ans
    for i in tLst[index]:
        if v == i:
            continue
        elif vLst[i] == 1:
            continue
        ans = dfs(n + 1, i, index, ans)
        vLst[i] = 0
    return ans
print(dfs(0, 0, 0, 0))

Submission status: Accepted

Solution code:
from collections import deque

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

q = deque()
q.append((0, set(), -1))
ans = 0
while len(q):
    a, s, p = q.pop()
    s.add(a)
    if len(s) == N:
        ans += 1
        continue
    for b in to[a]:
        if b not in s:
            q.append((b, s | {b}, a))
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in [0]*m]
g=[[] for _ in [0]*n]
[g[a-1].append(b-1) for a,b in ab]
[g[b-1].append(a-1) for a,b in ab]

from itertools import permutations

cnt=0
for i in permutations(range(1,n)):
    i=(0,)+i
    for j in range(n-1):
        if i[j+1] not in g[i[j]]:
            break
    else:
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
N, M = map(int,input().split(" "))
nm = [[0 for i in range(N)] for j in range(N)]
for i in range(M):
  x,y = (map(int,input().split(" ")))
  nm[x-1][y-1]=1
  nm[y-1][x-1]=1

cnt = [0]
def dfs(V, s):
  V[s]=1
  if sum(V)==N:
    cnt[0] += 1
  for i in range(N):
    if nm[i][s]==1 and V[i]==0:
      dfs(V,i)
  V[s]=0
  
dfs([0]*N,0)
print(cnt[0])

Submission status: Accepted

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

for _ in range(n):
    conn.append([False]*n)

visited = [False] * n

v = []

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

for start, end in v:
    conn[start][end] = conn[end][start] = True

def dfs(now, depth):
    if visited[now] : return 0
    if depth == n - 1: return 1

    visited[now] = True
    ret = 0

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

    visited[now] = False
    return ret

print(dfs(0, 0))

Submission status: Accepted

Solution code:
import itertools
N,M=map(int,input().split())
l=list(itertools.permutations(range(N-1)))
h=[set(map(int, input().split())) for i in range(M)]
a=0
for i in range(len(l)):
    for k in range(M):
        if {1,l[i][0]+2}==h[k]:
            break
    else:
        continue
    for j in range(1,N-1):
        for k in range(M):
            if {l[i][j-1]+2,l[i][j]+2}==h[k]:
                break
        else:
            break
    else:
        a+=1
print(a)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import copy
import string
import  math
from _bisect import *
from collections import *
from operator import itemgetter
from math import factorial
"""
from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)
"""
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

def dfs(v):
    flag = True
    for i in range(n):
        if not visit[i]:
            flag = False
    if flag:
        return 1

    ret = 0

    for i in range(n):
        if not g[v][i]:
            continue
        if visit[i]:
            continue

        visit[i] = True
        ret += dfs(i)
        visit[i] = False

    return ret


    for next in g[v]:
        if visit[next]:
            continue
        else:
            visit[next] = True
            dfs(next)


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

visit = [False] * n
visit[0] = True
print(dfs(0))

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
L=[[] for _ in range(N)]
visited=[True]+[False]*(N-1)
for _ in range(M):
    a,b=map(int,input().split())
    L[a-1].append(b-1)
    L[b-1].append(a-1)
def dfs(now,cnt):
    ans=0
    if cnt==N:
        return 1
    for nxt in L[now]:
        if visited[nxt]:
            continue
        visited[nxt]=True
        ans+=dfs(nxt,cnt+1)
        visited[nxt]=False
    return ans
print(dfs(0,1))

Submission status: Accepted

Solution code:
import itertools
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)
cnt=0
for i in itertools.permutations(range(N),N):
    if i[0]==0:
        for j in range(N):
            if j==N-1:
                cnt+=1
                break
            if not (i[j+1] in L[i[j]]):
                break
print(cnt)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
e = [[False]*n for _ in range(n)]
visited = [False]*n
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    e[a][b] = True
    e[b][a] = True

def traverse(t,d):
    #print(t,d)
    visited[t] = True

    ans = 0
    is_end = True

    for i in range(n):
        if e[t][i] and not visited[i]:
            is_end = False
            ans += traverse(i, d+1)


    visited[t] = False
    if is_end:
        if d != n-1:
            return 0
        else:
            return 1
    
    return ans

print(traverse(0, 0))

Submission status: Accepted

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

Map = [[] for _ in range(N)]
reached = [False]*N

for _ in range(M):
    aa, bb = map(int, input().split())
    Map[aa-1].append(bb-1)
    Map[bb-1].append(aa-1)

cnt = 0

def DFS(x):
    global cnt
    global reached

    reached[x] = True

    if all(reached):
        cnt += 1
        reached[x] = False

        return

    for i in Map[x]:
        if reached[i]:
            continue

        else:
            DFS(i)

    reached[x] = False


DFS(0)
print(cnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
import copy

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

ans = 0

def dfs(visited, now):
    tv = copy.copy(visited)
    tv[now-1] = True
    
    if all(tv):
        return 1

    temp = 0
    for i in graph[now]:
        if tv[i-1] != 1:
            temp += dfs(tv, i)
    return temp

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

Submission status: Accepted

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

used = [0 for i in range(n)]
ans = 0
#print(link)
def dfs(now, prev):
    global ans

    if sum(used) == n:
        #print('+1')
        ans += 1

    for i in link[now]:
        #print(now,i,used)
        if i != now and used[i] == 0:
            used[i] = 1
            #print('a')
            dfs(i, now)
            #print('b')
            used[i] = 0
            #print('c')

used[0] = 1
dfs(0,-1)
print(ans)

Submission status: Accepted

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

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

# [[1, 2], [0, 2], [0, 1]]

visited = [0] * n

def dfs(current, prev):

    if sum(visited) == n:
        return 1

    res = 0

    for next in edge[current]:
        if next != prev and visited[next] == 0:
            visited[next] = 1
            res += dfs(next, current)
            visited[next] = 0
    
    return res

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

Submission status: Accepted

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

visited = [0]*n
ans = 0

def dfs(now, prev):
    global ans

    if sum(visited) == n:
        ans += 1

    for i in link[now]:
        if i != now and visited[i] == 0:
            visited[i] = 1
            dfs(i, now)
            visited[i] = 0

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
g = [[] for i in range(n)]
for i in range(m):
    u,v = map(int, input().split())
    g[u-1].append(v-1)
    g[v-1].append(u-1)

visited = [0] * n

def dfs(now, pre):
    if sum(visited) == n:
        return 1
    
    res = 0
    
    for i in g[now]:
        if i != pre and visited[i] == 0:
            visited[i] = 1
            res = res + dfs(i, now)
            visited[i] = 0
    
    return res

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

def dfs(graph, start_node):
  queue = deque()
  queue.append([start_node,1,[0]])
  ans = 0
  while len(queue) > 0:
    prv_node, node_num, done = queue.pop()
    for node in graph[prv_node]:
      if node not in done:
        if node_num+1 == N:ans += 1
        else:queue.append([node,node_num+1,done+[node]]) 
  return ans

N,M=map(int,input().split())
graph = defaultdict(list)

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

Submission status: Accepted

Solution code:
import copy

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



def dfs(flg, E, i):
	q = []
	for e in E:
		if e[0] == i:
			if flg[e[1]-1] == 0:
				q.append(e[1])
		if e[1] == i:
			if flg[e[0]-1] == 0:
				q.append(e[0])
	if len(q) == 0:
		if flg.count(0) == 0:
			return 1
		else:
			return 0

	ans = 0
	for n in q:
		temp = copy.deepcopy(flg)
		temp[n-1] = 1
		ans += dfs(temp, E, n)

	return ans

flg = [0 for _ in range(N)]
flg[0] = 1
print(dfs(flg, E, 1))