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 dfs(v,n,visi,G):
    allv=True

    if False in visi:
        allv=False

    if allv:
        return 1

    ret=0

    for i in range(n):
        if G[v][i]==False:
            continue
        if visi[i]:
            continue
        visi[i]=True
        ret+=dfs(i,n,visi,G)
        visi[i]=False

    return ret

def main():
    ans=0
    n,m=map(int,input().split())
    ab=[list(map(int,input().split()))for i in range(m)]
    G=[[False for i in range(8)]for i in range(8)]
    for a,b in ab:
        G[a-1][b-1]=G[b-1][a-1]=True

    visi=[False for i in range(n)]

    visi[0]=True

    return dfs(0,n,visi,G)

print(main())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

ans=0


def dfs(v,n,visi):
    allv=True

    for i in visi:
        if not i:
            allv=False

    if allv:
        return 1

    ret=0

    for i in range(n):
        if G[v][i]==False:
            continue
        if visi[i]:
            continue
        visi[i]=True
        ret+=dfs(i,n,visi)
        visi[i]=False

    return ret

n,m=map(int,input().split())
ab=[list(map(int,input().split()))for i in range(m)]
G=[[False for i in range(8)]for i in range(8)]

for a,b in ab:
    G[a-1][b-1]=G[b-1][a-1]=True

visi=[False for i in range(n)]

visi[0]=True

print(dfs(0,n,visi))

Submission status: Accepted

Solution code:
#始点と終点は決まっていないので、軸優先や、深さ優先では手間が増えそう(これらは根っこのようなものがあるので)
#順列を使ってといて見ようと思う
#あ、、、始点決まってたわ()終点は決まってないですね。まあ、DFSやBFSでもできるけども。O(n^2)よりはO(n!)の方が小さい
from itertools import permutations

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

for vertexs in permutations(V):
    #print(vertexs)
    if vertexs[0] != 1:
        continue
    #print(vertexs)
    one_strike = True#一筆描きできるならTrue
    for vertex_index in range(len(vertexs)-1):
        flag = False
        for i in range(M):
            a,b = E[i]
            if (a == vertexs[vertex_index] and b == vertexs[vertex_index+1]) or (a == vertexs[vertex_index+1] and b == vertexs[vertex_index]):
                flag = True
                break
        if not flag:
            one_strike = False
            break
    if one_strike:
        one_strike_cnt += 1

print(one_strike_cnt)

Submission status: Accepted

Solution code:
from collections import defaultdict
vertices, edges = map(int, input().split(" "))
connect = defaultdict(set)
for i in range(edges):
    a, b = map(int, input().split(" "))
    connect[a] |= {b}
    connect[b] |= {a}

answer = 0
queue = [[set(), 1]]
while queue:
    visited, now = queue.pop()
    visited |= {now}
    # print(visited, now, need_visit)
    if len(visited) == vertices:
        answer += 1
    else:
        for conn in connect[now]:
            if conn not in visited:
                queue.append([visited | {conn}, conn])
        # print(visited, now, need_visit)

print(answer)

Submission status: Accepted

Solution code:
z,m=map(int,input().split());a=[[],[]];ans=0
for i in range(m):aa,bb=map(int,input().split());a[0].append(aa);a[1].append(bb)
def d(n,nl,ml):
  if sorted(nl+[n])==[i+1for i in range(z)]:return 1
  if n in nl:return 0
  l=len(ml[0]);ans=0
  for i in range(l):
    c=[ml[0][:i]+ml[0][i+1:],ml[1][:i]+ml[1][i+1:]]
    if ml[0][i]==n:ans+=d(ml[1][i],nl+[n],c)
    if ml[1][i]==n:ans+=d(ml[0][i],nl+[n],c)
  return ans
for i in range(m):
  if a[0][i]==1:
    c=[a[0][:i]+a[0][i+1:],a[1][:i]+a[1][i+1:]]
    ans+=d(a[1][i],[1],c)
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
dict = {}
for m in range(M):
    a,b = map(int,input().split())
    if a in dict:
        dict[a].append(b)
    else:
        dict[a] = [b]
    if b in dict:
        dict[b].append(a)
    else:
        dict[b] = [a]
ans = 0
l = [0 for i in range(N+1)]
l[1] = 1
def dfs(l,now):
    global ans
    if sum(l) == N:
        ans += 1
        return(0)
    for i in dict[now]:
        if l[i] == 0:
            l[i] += 1
            now = i
            dfs(l,now)
            l[i] -= 1
        else:
            continue
dfs(l,1)
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(M)]
visited = {i:False for i in range(N)}
visited[0] = True
ans = 0

def DFS(x):
#  print(visited)
  global ans
  nextx = []
  if False not in visited.values():
    ans += 1
    return
  for i in range(M):
    if x in ab[i]:
      xcol = ab[i].index(x)
      if visited[ab[i][1-xcol]-1]:
        continue
      else:
        nextx.append(ab[i][1-xcol])
#  print(nextx)
  for i in nextx:
    visited[i-1] = True
    DFS(i)
    visited[i-1] = False
  return

DFS(1)
print(ans)

Submission status: Accepted

Solution code:
def one_stroke_path(N: int, M: int, edges: list) -> int:
    g = [[] for _ in range(N)]
    for u, v in edges:
        g[u-1].append(v-1)
        g[v-1].append(u-1)

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

    def dfs(current: int, visited_num: int) -> int:
        if not visited[current] and visited_num + 1 == N:
            return 1

        visited[current] = True

        total = sum(dfs(to, visited_num + 1)
                    for to in g[current] if not visited[to])

        visited[current] = False

        return total

    return dfs(0, 0)


if __name__ == "__main__":
    M = 0
    N, M = map(int, input().split())
    edges = [tuple(int(s) for s in input().split()) for _ in range(M)]
    ans = one_stroke_path(N, M, edges)
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque
def dfs(v,N,memo):
    ans =0
    if not False in memo.values():
        return 1
    for u in E[v]:
        if memo[u]!=True:
            memo[u] = True
            ans += dfs(u,N,memo)
            memo[u] = False
    return ans
N,M = list(map(int,input().split()))
memo = {i:False for i in range(1,N+1)}
E = {i: []for i in range(1,N+1)}
for i in range(M):
    u,v = list(map(int,input().split()))
    E[u].append(v)
    E[v].append(u)
memo[1] = True
print(dfs(1,N,memo))

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
edge_list = [list() for i in range(N)]
for i in range(M):
        a,b = map(int,input().split())
        edge_list[a-1].append(b-1)
        edge_list[b-1].append(a-1)
done = [0] * N
chk = 0
def dfs(s,done):
    done = done[:]
    global chk
    done[s] = True
    if all(done):
        chk += 1
    for i in edge_list[s]:
        if not done[i]:
            dfs(i,done)
    return 0
dfs(0,done)
print(chk)

Submission status: Accepted

Solution code:
import sys
n,m=map(int,input().split())
number=[[int(i) for i in l.split()] for l in sys.stdin]
visit=[0]*(n+1)
visit[1]=1
node=[[] for i in range(n+1)]
for i in number:
  node[i[0]].append(i[1])
  node[i[1]].append(i[0])
ans=0
def dfs(x):
  global ans
  if visit.count(1)==n:
    ans+=1
    return 0
  for i in node[x]:
    if visit[i]==0:
      visit[i]=1
      dfs(i)
      visit[i]=0
  return 0
dfs(1)
print(ans)

Submission status: Accepted

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

def find(now, checked):
  if len(checked) == N:
    return 1
  res = 0
  for i in set(range(N)) - checked:
    if neighbor_graph[now][i]:
      res += find(i, checked | {i})
  return res

print find(0, {0})

Submission status: Accepted

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

memo={}
for a,b in AB:
  #print(a,b)
  memo.setdefault(a, set([])).add(b)
  memo.setdefault(b, set([])).add(a)

answer=0
from itertools import permutations
for p in permutations(list(range(2,N+1))):
  if p[0] not in memo[1]:
    continue
  for i in range(N-2):
    if p[i+1] in memo[p[i]]:
      pass
    else:
      break
  else:
    answer+=1
      
print(answer)

Submission status: Accepted

Solution code:
#input
n, m = map(int, input().split())
A = []
B = []
for i in range(m):
    a, b = map(int,input().split())
    A.append(a)
    B.append(b)

#operation
pointvisited = [False] * (n + 1)
pointvisited[0] = True
pointvisited[1] = True
ans = 0
def DFS(point):
    if all(pointvisited):
        global ans
        ans += 1
    nextpoints = findnextpoint(point)
    for nextpoint in nextpoints:
        if not pointvisited[nextpoint]:
            pointvisited[nextpoint] = True
            DFS(nextpoint)
            pointvisited[nextpoint] = False

def findnextpoint(point):
    nepo = []
    for i, a in enumerate(A):
        if a == point:
            nepo.append(B[i])
    for i, b in enumerate(B):
        if b == point:
            nepo.append(A[i])
    return nepo

#output
DFS(1)
print(ans)

Submission status: Accepted

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

# 探索済みリスト
closed_list = [False] * N
closed_list[0] = True
cnt = 0
level = 1

# 深さ優先探索
def dfs(target):
    global cnt, level
    if all(closed_list):
        cnt += 1
        return
    # open_listリストのnode
    for node in open_list[target]:
        # 探索済みでない場合
        if closed_list[node] is False:
            # 探索開始
            closed_list[node] = True
            # 再帰
            level += 1
            dfs(node)
            level = 1
            # levalを戻す
            closed_list[node] = False
    return


dfs(0)
print(cnt)

Submission status: Accepted

Solution code:
n,m=(int(i) for i in input().split())
mtrx=[[int(i) for i in input().split()] for j in range(m)]
#print(mtrx)
mtrx+=[[mtrx[i][1],mtrx[i][0]] for i in range(m)]
#print(mtrx)
mylist=[10*mtrx[i][0]+mtrx[i][1] for i in range(len(mtrx))]
#print(mylist)
# 順列を格納するリスト
perm = []
cnt=[]
# 順列の生成
def make_perm(n, m = 0):
    if n == m and perm[0]==1:
        flag=1
        for i in range(len(perm)-1):
            myval=10*perm[i]+perm[i+1]
            myval1=mylist.count(myval)
            flag=flag*myval1
        cnt.append(flag)
        
    else:
        for x in range(1, n + 1):
            if x in perm: continue
            perm.append(x)
            make_perm(n, m + 1)
            perm.pop()
            
make_perm(n)
print(sum(cnt))

Submission status: Accepted

Solution code:
# from log import logger

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

# logger.info('key_value: {}\n'.format(key_value))

closed_list = [False] * N
closed_list[0] = True
cnt = 0


def dfs(target):
    global cnt
    # logger.info('key_value[target]: {}'.format(key_value[target]))
    if all(closed_list):
        cnt += 1
        return
    for node in key_value[target]:
        # logger.info('node: {}'.format(node))
        # 探索済みでない場合
        if closed_list[node] is False:
            closed_list[node] = True
            dfs(node)
            closed_list[node] = False
        # logger.info('closed_list: {}\n'.format(closed_list))
    return


dfs(0)
print(cnt)

Submission status: Accepted

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

def dfs(fr):
    global cnt
    if all(visited):
        cnt+=1
        return
    for to in edges[fr]:
        if not visited[to]:
            visited[to]=True
            dfs(to)
            visited[to]=False
    return

dfs(0)
print(cnt)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

edges = defaultdict(set)
used = [False] * N
for i in range(M):
    a, b = map(int, input().split())
    edges[a-1].add(b-1)
    edges[b-1].add(a-1)

def count(index):
    if all(used):
        return 1

    total = 0
    for dest in edges[index]:
        if not used[dest]:
            used[dest] = True
            total += count(dest)
            used[dest] = False
    return total

used[0] = True
print(count(0))

Submission status: Accepted

Solution code:
n,m=(int(i) for i in input().split())
mtrx=[[int(i) for i in input().split()] for j in range(m)]
#print(mtrx)
mtrx+=[[mtrx[i][1],mtrx[i][0]] for i in range(m)]
#print(mtrx)
mylist=[10*mtrx[i][0]+mtrx[i][1] for i in range(len(mtrx))]
#print(mylist)
# 順列を格納するリスト
perm = []
cnt=[]
# 順列の生成
def make_perm(n, m = 0):
    if n == m and perm[0]==1:
        flag=1
        for i in range(len(perm)-1):
            myval=10*perm[i]+perm[i+1]
            myval1=mylist.count(myval)
            flag=flag*myval1
        cnt.append(flag)
        
    else:
        for x in range(1, n + 1):
            if x in perm: continue
            perm.append(x)
            make_perm(n, m + 1)
            perm.pop()
            
make_perm(n)
print(sum(cnt))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
r = [[] * N for i in range(N)]
reached = [0] * N
reached[0] = 1
count = 0
 
def dfs(now):
    global count
    if all(reached):
        count += 1
    for next in r[now]:
        if reached[next] == 0:
            reached[next] = 1
            dfs(next)
            reached[next] = 0
 
for i in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    r[a].append(b)
    r[b].append(a)
 
dfs(0)
 
print(count)

Submission status: Accepted

Solution code:
import copy

N, M = list(map(int, input().split()))
route = [[0 for i in range(N)] for l in range(N)]
count = 0
for i in range(M):
    a, b = list(map(int, input().split()))
    route[a-1][b-1] = 1
    route[b-1][a-1] = 1

queue = [[[0],i] for  i in range(N) if route[0][i]]

while len(queue):
    r = queue.pop(0)
    n = r[1]
    r[0].append(n)
    if len(r[0]) == N:
        count += 1
    else:
        for i in range(1, N):
            if route[n][i] and i not in r[0]:
                x = copy.deepcopy(r[0])
                queue.append([x, i])

print(count)

Submission status: Accepted

Solution code:
n, m = [int(x) for x in input().split(' ')]
 
edges = set([tuple(input().split(' ')) for _ in range(m)])
edges.update([(x[1], x[0]) for x in list(edges)])
 
 
def dfs(node, history):
    ans = 0
    if len(history) == n - 1:
        return 1
 
    nextnodes = [
        x[1] for x in edges if x[1] not in history and x[0] == node and x[1] != node
    ]
    history.add(node)
    for next in nextnodes:
        ans += dfs(next, history)
    history.remove(node)
    return ans
 
 
print(dfs('1', set()))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
r = [[] * N for i in range(N)]
reached = [0] * N
reached[0] = 1
count = 0

def dfs(now, pre):
    global count
    if all(reached):
        count += 1
    for next in r[now]:
        if next != pre:
            if reached[next] == 0:
                reached[next] = 1
                dfs(next, now)
                reached[next] = 0

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

dfs(0, -1)

print(count)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
r = [[] * N for i in range(N)]
reached = [0] * N
reached[0] = 1
count = 0

def dfs(now):
    global count
    if all(reached):
        count += 1
    for next in r[now]:
        if reached[next] == 0:
            reached[next] = 1
            dfs(next)
            reached[next] = 0

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

dfs(0)

print(count)

Submission status: Accepted

Solution code:
import numpy as np
N, M = map(int, input().split())
 
G = np.zeros((N, N)) 
total_path_num = 0
not_reach_node = list(range(1, N))
node = 0
 
for i in range(M):
  a, b = map(int, input().split())
  G[a-1, b-1] += 1
  G[b-1, a-1] += 1
  
def search_path(G, not_reach_node, node):
  global total_path_num
  if len(not_reach_node) == 0:
    total_path_num += 1
    return total_path_num
  
  for x in np.where((G[node] == 1))[0]:
    if (x in not_reach_node):
      not_reach_node_copy = not_reach_node.copy()
      not_reach_node_copy.remove(x)
      search_path(G, not_reach_node_copy, x)

search_path(G, not_reach_node, node)      	
 
print(total_path_num)

Submission status: Accepted

Solution code:
import itertools

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

count = 0
for V in itertools.permutations(range(1, N)):
    if V[0] in E[0] and all(V[i] in E[V[i-1]] for i in range(1, N-1)):
        count += 1
print(count)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
edges = [list() for _ in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
visited = [0]*N
cnt = 0
def dfs(u,visited):
    visited = visited[:]
    global cnt
    visited[u] = True
    if all(visited):
        cnt += 1
        return
    for v in edges[u]:
        if not visited[v]:
            dfs(v,visited)
    return 0

dfs(0,visited)
print(cnt)

Submission status: Accepted

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

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

def dfs(v, used):
    if not False in used:       # chek complete or not
        return 1

    ans = 0
    for i in range(N):           # check all edge
        if not adj_matrix[v][i]: # edge check
            continue
        if used[i]:              # used check
            continue

        used[i] = True           #　使用済みを示す
        ans += dfs(i, used)
        used[i] = False          # ほかのエッジのためにFalseにする

    return ans

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

print(dfs(0, used))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab=[list(map(int, input().split())) for i in range(m)]
e=[[0]*10 for i in range(10)]
for abi in ab:
    e[abi[0]][abi[1]]=1
    e[abi[1]][abi[0]]=1
ans=0
def dfs(l, v):
    l.append(v)
    if len(l)==n:
        global ans
        ans+=1
        return
    for i in range(10):
        if e[v][i]==1 and i not in l:
            ll=[i for i in l]
            dfs(ll, i)
    return
dfs([],1)
print(ans)

Submission status: Accepted

Solution code:
def dfs(n,depth):
    if used[n]:
        return 0
    if depth==N:
        return 1
    used[n]=1
    ans=0
    for i in range(N):
        if connect[n][i]:
            ans+=dfs(i,depth+1)
    used[n]=0
    return ans

N,M=map(int,input().split())
used=[0]*N
connect=[[0 for i in range(N)]for j in range(N)]
a=[];b=[]

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

for i in range(M):
    connect[a[i]][b[i]]=connect[b[i]][a[i]]=1

print(dfs(0,1))

Submission status: Accepted

Solution code:
import itertools
N,M = map(int,input().split())
adj = [[0] * (N) for i in range(N)]
for m in range(M):
    a,b = map(int,input().split())
    adj[a-1][b-1] = 1
    adj[b-1][a-1] = 1

ans = 0

for i in itertools.permutations(range(2,N+1)):
    f = 0
    #print(i)
    for n in range(0,N-2):
        #print(i[n]-1,i[n+1]-1)
        if adj[0][i[0]-1] != 1:
            f = 1
            break
        if adj[i[n]-1][i[n+1]-1] != 1:
            #print(adj[i[n]-1][i[n+1]-1])
            f = 1
            break
    if f == 0:
        #print(i)
        ans += 1
print(ans)

Submission status: Accepted

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

d = [0]*n
d[0] = 1
cnt = 0

def dfs(x):
  global cnt
  if all(d):
    cnt += 1
    return
  for i in D[x]:
    if d[i] == 0:
      d[i] = 1
      dfs(i)
      d[i] = 0

dfs(0)
print(cnt)

Submission status: Accepted

Solution code:
from itertools import permutations

n,m = map(int,input().split())
D = [[0]*n for i in range(n)]
for i in range(m):
	a,b = map(int,input().split())
	D[a-1][b-1] = 1
	D[b-1][a-1] = 1
cnt = 0
for a in permutations(range(n)):
	if a[0] != 0:
		break
	tmp = 1
	for i in range(n-1):
		tmp = tmp * D[a[i]][a[i+1]]
	cnt += tmp
print(cnt)

Submission status: Accepted

Solution code:
import itertools

N,M = (int(i) for i in input().split())
li = [[None]*N for i in range(N)]
cnt = 0

for i in range(N):
  li[i][i] = 1

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

for i in itertools.permutations(range(1,N)):
  if li[i[0]][0] == 1:
    flag = True
    for j in range(1,N-1):
      if li[i[j]][i[j-1]] == None:
        flag = False
        break
    if flag:
      cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
n,m = (int(i) for i in input().split())
e = sorted([[int(i)-1 for i in input().split()] for i in range(m)])

g = [[0 for i in range(n)] for j in range(n)]
for x in e:
    g[x[0]][x[1]] = 1
    g[x[1]][x[0]] = 1

import copy
count = 0
def f(idx, arr):
    used = copy.copy(arr)
    global count
    used[idx] = 1
    if used.count(0) == 0:
        count += 1

    for i, x in enumerate(g[idx]):
        if x==1 and used[i]==0:
            f(i, used)

used = [0]*n
f(0, used)

print(count)

Submission status: Accepted

Solution code:
N,M=map(int,input().split(' '))
A=[sorted(list(map(int,input().split(' ')))) for i in range(M)]
ans=0
stack=[1]
visited=[1]
def dfs():
    global stack
    global ans
    #終了判定
    if stack==[]:
        return None
    else:
        #これ以上訪問できるnodeがないとき
        if len(stack)==N: #全訪問した
            ans+=1
            stack.pop(0)
        else:
            for i in range(1,N+1): #未訪問の子ノードを検討
                if i not in stack and sorted([stack[0], i]) in A:
                    stack = [i] + stack
                    dfs()
            stack.pop(0)
dfs()
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
sides = [list(map(int, input().split())) for _ in range(m)]
check = [0] * n
ans = 0

def DFS(v):
    # print(v)
    if check.count(0) == 0:
        global ans
        ans += 1
        return
    for side in sides:
        if side[0] == v and check[side[1]-1] == 0:
            check[side[1]-1] = 1
            DFS(side[1])
            check[side[1]-1] = 0
        if side[1] == v and check[side[0]-1] == 0:
            check[side[0]-1] = 1
            DFS(side[0])
            check[side[0]-1] = 0
    return ans


check[0] = 1
print(DFS(1))

# procedure DFS(現在の頂点 v)
#     if 全ての頂点を訪問済み then
#         答えを 1 増やす。
#         return
#     end if
#     for 頂点 i: 頂点 v に隣接しているかつ未訪問 do
#         頂点 i を訪問済みとする。
#         DFS(i)
#         頂点 i を未訪問とする。
#      end for
#      return
#  end procedure

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, AB):
    g = defaultdict(set)

    for a, b in AB:
        g[a].add(b)
        g[b].add(a)

    ans = 0
    for ns in permutations(range(2, N+1), N-1):
        ns = list(ns)
        ns.insert(0, 1)
        for i in range(N-1):
            if ns[i+1] not in g[ns[i]]:
                break
        else:
            ans += 1
    return ans


def main():
    N, M = read_int_n()
    AB = [read_int_n() for _ in range(M)]
    print(slv(N, M, AB))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

vis_N = [-1]*(N+1)
count = 0
vis_N[1] = 1

def search(a):
    global count,vis_N,vis_Nij
    #print(count,vis_N)
    if sum(vis_N)+1 == N:
        count = count + 1
        return# count#print(count,"A",i)
    
    for i in range(M):
        if (P[i][0] == a and vis_N[P[i][1]] == -1) or (P[i][1] == a and vis_N[P[i][0]] == -1):
            if P[i][0] == a:
                nxt = P[i][1]
            else:
                nxt = P[i][0]
            #vis_N[a] = 1
            vis_N[nxt] = 1
            search(nxt)
            vis_N[nxt] = -1
    
    return# count

search(1)
print(count)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
arr = [list() for _ in range(n)]
for _ in range(m):
  a,b = map(int, input().split())
  arr[a-1].append(b)
  arr[b-1].append(a)
d = [0]*n
d[0] = 1
cnt = 0
def dfs(x):
  global cnt
  if all(d):
    cnt += 1
    return
  for i in arr[x-1]:
    if d[i-1] == 0:
      d[i-1] = 1
      dfs(i)
      d[i-1] = 0
dfs(1)
print(cnt)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
arr = [[0]*n for _ in range(n)]
for _ in range(m):
  a,b = map(int, input().split())
  arr[a-1][b-1] = 1
  arr[b-1][a-1] = 1
d = [0]*n
d[0] = 1
cnt = 0
def dfs(x):
  global cnt
  if all(d):
    cnt += 1
  for i in range(1,n+1):
    if arr[x-1][i-1] and d[i-1] == 0:
      d[i-1] = 1
      dfs(i)
      d[i-1] = 0
dfs(1)
print(cnt)

Submission status: Accepted

Solution code:
from collections import deque


def main():
    N, M = map(int, input().split())
    adj = [set() for _ in range(N)]
    for i in range(M):
        a, b = map(int, input().split())
        adj[a-1].add(b-1)
        adj[b-1].add(a-1)
    ans = 0
    q = deque([(0, set([0]))])
    while len(q):
        cur, visited = q.popleft()
        if len(visited) == N:
            ans += 1
            continue
        for nxt in adj[cur]:
            if nxt not in visited:
                nxtvst = set(visited)
                nxtvst.add(nxt)
                q.append((nxt, nxtvst))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# dfsでみる どうせ小さいので都度配列を渡していい
# 隣接リストでもつことにする
# クラスで管理するのすらめんどくさいのでlistオブジェクトでいいや

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

ans = 0

path = [0, [0]]
stack = [path]

while len(stack) > 0:
    cur = stack.pop()
    if len(cur[1]) == n:
        ans += 1
    else:
        for g in graph[cur[0]]:
            if g not in cur[1]:
                nex = cur[1][:]
                nex.append(g)
                stack.append([g, nex])

print(ans)

Submission status: Accepted

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

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

visited=[]
for j in range(n):
  visited.append(False)

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

visited[0]=True

print(dfs(n,0,graph,visited))

Submission status: Accepted

Solution code:
#ABC054C
import copy
N,M=map(int,input().split())
C={}
for m in range(M):
	a,b=list(map(int,input().split()))
	C[b]=C.get(b,[])+[a]
	C[a]=C.get(a,[])+[b]
def Search(a,check):
	ans=0
	if all(check):
		return 1
	else:
		check[a-1]=1
		for b in C[a]:
			tmp=copy.deepcopy(check)
			if check[b-1]!=1:
				tmp[b-1]=1
				ans+=Search(b,tmp)
		return ans
print(Search(1,[0]*N))

Submission status: Accepted

Solution code:
import numpy as np
from itertools import permutations
import copy

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

adj = np.zeros((n,n))

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

cnt = 0
for p in permutations(range(n)):
	if p[0]!=0:
		continue
	tmp_adj = copy.deepcopy(adj)
	for i in range(n-1):
		if tmp_adj[p[i],p[i+1]] != 1:
			# print('invalid:',p)
			break
	else:
		# print('valid:',p)
		cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    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:
N,M=map(int,input().split())
from collections import defaultdict
branch=defaultdict(set)
for m in range(M):
    a,b=map(int,input().split())
    branch[a]|={b,}
    branch[b]|={a,}
    
now=1
ans=0
def go(N,now,branch,visited,ans):
    if len(visited)==N:return ans+1
    for b in branch[now]:
        if b in visited:continue
        ans=go(N,b,branch,visited|{now,b},ans)
    return ans
print(go(N,1,branch,{1,},0))