Problem:


Score : 300 points

Problem Statement

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

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

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

Here, the endpoints of a path are considered visited.  

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

Figure 1: an example of an undirected graph

The following path shown in Figure 2 satisfies the condition.

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

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

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

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

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

Constraints

2≦N≦8 

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

1≦a_i<b_i≦N 

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

Input

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

N M  
a_1 b_1  
a_2 b_2
:  
a_M b_M  

Output

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

Sample Input 1

3 3
1 2
1 3
2 3

Sample Output 1

2

The given graph is shown in the following figure:

The following two paths satisfy the condition:

Sample Input 2

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

Sample Output 2

1

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



Sample input:
3 3
1 2
1 3
2 3


Sample output:
2

Submission status: Accepted

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

#グラフの問題は行き先を入力の段階でしまっておく
to = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
#grobalで答えを管理
cnt = 0
#i現在いる、visited過去行った
def search(i,visited):
    global cnt
    if len(visited)==n:
        cnt += 1
    #隣に行って、現在を過去に追加
    #forで再帰先が複数になるが、searchの値を求めるわけではなくsearchでループを回すのが目的なのでok
    #if v not in visitedを満たすものがない(行けるとこはもう行った)ならそのループは終了
    for v in to[i]:
        if v not in visited:
            search(v,visited+[v])
search(0,[0])
print(cnt)

Submission status: Accepted

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

to = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
cnt = 0
def search(i,visited):
    global cnt
    if len(visited)==n:
        cnt += 1
    for v in to[i]:
        if v not in visited:
            search(v,visited+[v])
search(0,[0])
print(cnt)

Submission status: Accepted

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

V = [i+1 for i in range(N)]
import itertools

ptr = list(itertools.permutations(V, N))

res = 0
for p in ptr:       
    if p[0] == 1:
        now = 1
        flag = [0 for _ in range(N)]
        flag[0] = 1
        for i in range(N-1):
            for j in range(M):
                if A[j][0] == now and A[j][1] == p[i+1]:
                    flag[A[j][1] - 1] += 1
                    now = p[i+1]
                if A[j][1] == now and A[j][0] == p[i+1]:
                    flag[A[j][0] - 1] += 1
                    now = p[i+1]
                    
        tmp = 1         
        for i in range(N):
            if flag[i] != 1:
                tmp = 0
                break
                
        res += tmp
 
print(res)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
edges=[[0]*n for i 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=[False]*n
count=0
def dfs(u,visited):
  global count
  visited=visited[:]
  visited[u]=True
  if all(visited):
    count+=1
    return
  for v in edges[u]:
    if not visited[v]:
      dfs(v,visited)
  return False

dfs(0,visited)
print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

def main():
    n, m = map(int, input().split())
    edges = defaultdict(list)

    for _ in range(m):
        a, b = [int(s) - 1 for s in input().split()]
        edges[a].append(b)
        edges[b].append(a)
    
    visited = 1
    pos = 0
    mask = (1 << n) - 1
    print(solve(edges, pos, visited, mask))
    
def solve(edges, pos, visited, mask):
    if visited == mask:
        return 1

    s = 0
    for e in edges[pos]:
        if ((1 << e) & visited) == 0:
            s += solve(edges, e, visited | (1 << e), mask)
    
    return s

main()

Submission status: Accepted

Solution code:
import itertools

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

per=[i for i in range(2,N+1)]
permu=[]
for i in itertools.permutations(per):
    lst=[1]
    lst.extend(i)
    permu.append(lst)
num=0
for lst in permu:
    can=True
    for i in range(N-1):
        if not([lst[i],lst[i+1]] in ab) and not([lst[i+1],lst[i]] in ab):
            can=False
            break
    if can:
        num+=1
print(num)

Submission status: Accepted

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

def dfs(x):
    if checked[x]==True:
        return
    checked[x]=True
    if checked.count(False)==0:
        ans[0] += 1
        checked[x]=False
        return

    for j in range(0, N):
        if hen[x][j] == True:
            dfs(j)
    checked[x] = False


#島0～N-1
for i in range(M):
    
    a,b=map(int,input().split())
    hen[a-1][b-1] = True
    hen[b-1][a-1] = True

dfs(0)
print(ans[0])

Submission status: Accepted

Solution code:
import itertools

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

def is_path(seq):
    for idx in range(len(seq)):
        if idx == 0:
            if [1, seq[idx]] not in edges and [seq[idx], 1] not in edges:
                return False
        else:
            if [seq[idx-1], seq[idx]] not in edges and [seq[idx], seq[idx-1]] not in edges:
                return False
    return True
        
num = 0
for seq in list(itertools.permutations(list(range(2, N+1)))):
    if is_path(seq):
        num += 1
print(num)

Submission status: Accepted

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

to = [[] for i in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
cnt = 0
def search(i,visited):
    global cnt
    if len(visited) == N:
        cnt += 1
    for v in to[i]:
        if v not in visited:
            search(v,visited+[v])
search(0,[0])
print(cnt)

Submission status: Accepted

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

vis = [0] * n
vis[0] = 1

G = [[0] * n for i in range(n)]
for a, b in A:
    G[a -1][b - 1] = 1
    G[b - 1][a - 1] = 1
    
cnt = 0
    
def dfs(x):
    global cnt
    if sum(vis) == n:
        cnt += 1
        return
    for i in range(n):
        if G[x][i] == 1 and vis[i] == 0:
            vis[i] = 1
            dfs(i)
            vis[i] = 0
    return

dfs(0)
print(cnt)

Submission status: Accepted

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

#A

#B

#C
n,m = LI()
v = LIR(m)
p2 = [1]
for i in range(n):
    p2.append(p2[-1]*2)
dp = [[0 for i in range(p2[n])] for j in range(n)]
dp[0][1] = 1
for i in range(1,p2[n]):
    for k in range(n):
        for a,b in v:
            a -= 1
            b -= 1
            if k==a or k == b:
                c = p2[a]
                d = p2[b]
                if i&c and not i&d:
                    dp[b][i|d] += dp[k][i]
                if (not i&c) and i&d:
                    dp[a][i|c] += dp[k][i]
ans = 0
for i in range(1,n):
    ans += dp[i][-1]
print(ans)
#D

#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Accepted

Solution code:
from collections import defaultdict


def solve(N, ab, ne_table, start: int, used: set):
    if len(used) == N:
        return 1
    res = 0
    next_list = ne_table[start]
    for i in next_list:
        if i not in used:
            res += solve(N, ab, ne_table, i, used.union({i}))
    return res


def main():
    N, M = [int(a) for a in input().split()]

    ab = [
        [int(a) - 1 for a in input().split()]
        for _ in range(M)
    ]

    ne_table = defaultdict(lambda: [])
    for (a, b) in ab:
        ne_table[a].append(b)
        ne_table[b].append(a)

    print(solve(N, ab, ne_table, 0, {0}))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write

cnt = 0
all_visited = False
def dfs(link, V, i):
    global cnt
    global all_visited
    for j in range(N):
        if V[j] == 0:
            all_visited = False
            break
        all_visited = True
    
    if all_visited == True:
        cnt += 1
        return
    
    adj = len(link[i])
    for j in range(adj):
        if V[link[i][j]] == 0:
            V[link[i][j]] = 1
            dfs(link, V, link[i][j])
            V[link[i][j]] = 0


a = list(map(int,input().split()))
N = a[0]
M = a[1]
link = [[] for i in range(N)]
visited = [0 for i in range(N)]
for i in range(M):
    temp = list(map(int,input().split()))
    link[temp[0]-1].append(temp[1]-1)
    link[temp[1]-1].append(temp[0]-1)
visited[0] = 1
dfs(link, visited, 0)
print(str(cnt))

Submission status: Accepted

Solution code:
N,M = (int(i) for i in input().split()) 
edge = []
for _ in range(N):
    edge.append([False] * N) 
for _ in range(M):
    a,b =  (int(i) - 1 for i in input().split())  
    edge[a][b] =True
    edge[b][a] = True


COUNT = 0
def func(choose,choosen,count):
    new_count = count
    if len(choose) == 0:
        can_move =True
        for i in range(len(choosen) - 1):
            can_move = can_move and edge[choosen[i]][choosen[i+1]]
        if can_move:
            #print('sex')
            return count + 1
        return count
    for i in range(len(choose)):
        new_choosen = choosen + [choose[i]]
        new_count = func(choose[:i] + choose[i + 1:],new_choosen,new_count)
    return new_count

a = func([i for i in range(1,N)],[0],0)
print(a)

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque

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

graph = defaultdict(list)
edges = []

# 無向グラフの表現
for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    edges.append((a, b))

ans = 0

def dfs(graph, node_start, visited):
    global ans
    if len(set(visited)) == len(set(graph)):
        ans += 1
        return
    for node_end in graph[node_start]:
        # 一回も訪れていない
        if node_end not in visited:
            dfs(graph, node_end, visited + [node_end])
    return

dfs(graph, 1, [1])
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque

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

graph = defaultdict(list)
edges = []

# 無向グラフの表現
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    edges.append((a, b))

ans = 0
def dfs(graph, node_start, visited):
    global ans
    if sum(visited) == len(graph):
        ans += 1
        return
    for node_end in graph[node_start]:
        # 一回も訪れていない
        if not visited[node_end]:
            visited[node_end] = True
            dfs(graph, node_end, visited)
            visited[node_end] = False
    return

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

Submission status: Accepted

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

tree= [[] for i in range(n)]
for i in range(m):
  tree[info[i][0]-1].append(info[i][1]-1)
  tree[info[i][1]-1].append(info[i][0]-1)

num = []  
for i in range(n):
  num.append(i)
  
ans = 0
for li in itertools.permutations(num, n):
  flag =True
  if li[0]==0:
    for i in range(n-1):
      if li[i+1] not in tree[li[i]]:
        flag =False
    if flag:
      ans = ans +1
    
  else:
    print(ans)
    exit()

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:
#dfs(再帰)
import sys
sys.setrecursionlimit(1000000000)

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

c = [[0]*N for _ in range(N)]
for x, y in zip(a, b):
    c[x-1][y-1] = 1
    c[y-1][x-1] = 1
visited = [-1]*N
visited[0] = 1
ans = 0

def dfs(n):
    global ans
    if sum(visited) == N:
        ans += 1
        return
    else:
        for i, x in enumerate(c[n]):
            if x == 1 and visited[i] == -1:
                visited[i] = 1
                dfs(i)
                visited[i] = -1
    return

dfs(0)
print(ans)

Submission status: Accepted

Solution code:
from collections import *
n,m=map(int,input().split())
d=defaultdict(list)
for s in m*[0]:
    a,b=map(int,input().split())
    d[a].append(b)
    d[b].append(a)
def DFS_dict(point,TFlist):
    if all(TFlist):
        return 1
    ans=0
    for i in d[point]:
        if TFlist[i-1]:
            continue
        TFlist[i-1]=True
        ans+=DFS_dict(i,TFlist)
        TFlist[i-1]=False
    return ans
TFlist=[True]+[False]*(n-1)
print(DFS_dict(1,TFlist))

Submission status: Accepted

Solution code:
from collections import *
n,m=map(int,input().split())

d=defaultdict(list)

for s in m*[0]:
    a,b=map(int,input().split())
    d[a].append(b)
    d[b].append(a)

#print(d)

#dはdefaultdict!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

def DFS_dict(point,TFlist):
#    print(TFlist)
#    print(d[point])
    if not False in TFlist:
        return 1
    ans=0
    for i in d[point]:
        if TFlist[i-1]:
            continue  #探索済みなら処理せず
        TFlist[i-1]=True #探索したのでTFlistをTrue
        ans+=DFS_dict(i,TFlist)
        TFlist[i-1]=False
    return ans

TFlist=[True]+[False]*(n-1)
print(DFS_dict(1,TFlist))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
AdjacencyMatrix=[[0]*n for i in [0]*n]
for i in [0]*m:
  a,b=map(int,input().split())
  AdjacencyMatrix[a-1][b-1]=1
  AdjacencyMatrix[b-1][a-1]=1
#print(AdjacencyMatrix)

def DFS(point,TFlist):
#  print(TFlist)
  if not False in TFlist:
    return 1
  ans=0
  for i in range(n):
    if not AdjacencyMatrix[point][i]:
      continue  #AMの0なら処理せず
    if TFlist[i]:
      continue  #探索済みなら処理せず
    TFlist[i]=True #探索したのでTFlistをTrue
    ans+=DFS(i,TFlist) #再帰的にansを加算
    TFlist[i]=False #枝を戻すためにTFlistをFalse
  return ans

TFlist=[True]+[False]*(n-1)
print(DFS(0,TFlist))

Submission status: Accepted

Solution code:
from itertools import permutations

N, M = [int(i) for i in input().split()]
edge_dict = dict()
for i in range(M):
    _from, _to = [int(i) for i in input().split()]
    if edge_dict.get(_from) is None:
        edge_dict[_from] = list()
    if edge_dict.get(_to) is None:
        edge_dict[_to] = list()
    edge_dict[_from].append(_to)
    edge_dict[_to].append(_from)

cnt = 0
for combi in permutations(range(2,N+1)):
    flg = 0
    combi = [1] + list(combi)
    for i in range(N-1):
        candidate = edge_dict.get(combi[i])
        if candidate is None:
            flg = 1
            break
        if combi[i+1] not in candidate:
            flg = 1
            break
    if flg == 0:
        cnt += 1
print(cnt)

Submission status: Accepted

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

def dfs(cur,*a): #現在地、通った場所→
  if cur in a:
    return 0
  else:
    if len(a) == N-1:
      return 1
    else:
      a = list(a)
      a.append(cur)
      count = 0
      for i in data[cur]:
        count += dfs(i,*a)
      return count
print(dfs(1,*[]))

Submission status: Accepted

Solution code:
import copy

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

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


def dfs(graph, now, done):
    result = 0
    doneCache = copy.deepcopy(done)
    doneCache.append(now)
    if len(doneCache) == N:
        return 1
    for a,b in graph:
        if a == now:
            if b not in doneCache:
                result += dfs(graph, b, doneCache)
        if b == now:
            if a not in doneCache:
                result += dfs(graph, a, doneCache)

    return result

print(dfs(abList, 1, []))

Submission status: Accepted

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

def dfs(edge, reach):
  if(all(reach)):
    return 1
  ret = 0
  for e in edges[edge]:
    if(reach[e]):
      continue
    reach[e] = True
    ret += dfs(e, reach)
    reach[e] = False
  return ret

edges = [[] for _ in range(N)]
all_reach = [False for _ in range(N)]

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

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
edges = [[] for _ in range(n)]
for a, b in ab:
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
reached = [False for i in range(n)]
def dfs(edge, r):
    if all(r):
        return 1
    ret = 0
    for e in edges[edge]:
        if r[e]:
            continue
        r[e] = True
        ret += dfs(e, r)
        r[e] = False
    return ret
reached[0] = True
print(dfs(0, reached))

Submission status: Accepted

Solution code:
import itertools

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

num=0
for a in itertools.permutations(range(N)):
    #print(a)
    connect=1
    if a[0]==0:
        for i in range(N-1):
            connect=connect*g[a[i]][a[i+1]]
            #print(connect)
        num=num+connect
        #print(num)
print(num)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
array = [[int(x) for x in input().split()] for y in range(m)]
modify = [[] for x in range(n + 1)]

for value1, value2 in array:
    modify[value1].append(value2)
    modify[value2].append(value1)


def solver(start, array, visited, cnt):
    if visited[start]:
        return cnt
    else:
        visited[start] = True

    for i in array[start]:
        if len(set(visited)) == 1:
            return cnt+1
        else:
            cnt = solver(i, array, list(visited), cnt)

    return cnt



start = modify[1]
res = 0
for i in start:
    visited = [False if x != 0 and x != 1 else True for x in range(n + 1)]
    res += solver(i, modify, visited, 0)

print(res)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
a = [0]*M
b = [0]*M
for i in range(M):
    a_, b_ = map(int,input().split())
    # 配列の添字としたいので-1
    a[i] = a_ -1
    b[i] = b_ -1

route = [0]*N  # 通過済
connect=[[0]*N for _ in range(N)]
def dfs(now, depth):
    # print("#"*depth,now, depth)
    # 通過済ならNG
    if route[now]: return 0
    # depth = Nなら達成
    if depth == N: return 1
    
    route[now] = 1
    ans = 0
    for i in range(N):
        if connect[now][i]:
            ans += dfs(i, depth+1)
    route[now] = 0
    return ans

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

# for xx in connect:
#     print(xx)
print(dfs(0,1))

Submission status: Accepted

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

EDGELIST=[[] for i in range(N+1)]

for x,y in EDGE:
    EDGELIST[x].append(y)
    EDGELIST[y].append(x)


import itertools

ITER=list(itertools.permutations(range(2,N+1),N-1))
ANS=0

for ite in ITER:
    ROUTE=(1,)+ite

    for j in range(1,N):
        if ROUTE[j] in EDGELIST[ROUTE[j-1]]:
            continue
        else:
            break
    else:
        ANS+=1

print(ANS)

Submission status: Accepted

Solution code:
import itertools
N, M = map(int, input().split())
e = set([])
for i in range(M):
    a, b = map(int, input().split())
    e.add((a, b))
ans = 0
for i in list(itertools.permutations(range(2, N + 1))):
    a = 1
    for b in i:
        if (a, b) in e or (b, a) in e:
            a = b
            continue
        break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
N, M = map(int, input().split())
ab = []
for i in range(M):
    ab.append(list(map(int, input().split())))
ans = 0
if M >= N - 1:
    for i in list(itertools.combinations(ab, N - 1)):
        g = {}
        for j in range(N):
            g[j + 1] = []
        for j, k in i:
            g[j].append(k)
            g[k].append(j)
        if len(g[1]) == 1:
            p = 1
            q = g[p][0]
            for j in range(N - 2):
                l = g[q]
                if len(l) != 2:
                    break
                l.remove(p)
                p = q
                q = l[0]
            else:
                ans += 1
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
count=0
def check(now,v,n):
    global count
    v[now]=1
    if sum(v)==n:
        count+=1
    else:
        for i in range(n):
            if v[i]==0 and g[now][i]==1:
                check(i,v[:],n)

n,m=map(int,input().split())
g=[[0 for i in range(n)]for i 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
check(0,[0 for i in range(n)],n)
print(count)

Submission status: Accepted

Solution code:
#ABC054C
n,m=map(int,input().split())
from collections import defaultdict
branch=defaultdict(set)
for i in range(m):
    a,b=map(int,input().split())
    branch[a]|={b,}
    branch[b]|={a,}

def roop(now,nonvisit,ans):
    nownonvisit=nonvisit.copy()
    nownonvisit-={now,}
    if len(nownonvisit)==0:return ans+1
    nex=branch[now].copy()
    for x in nex&nownonvisit:
        ans=roop(x,nownonvisit,ans)
    return ans

print(roop(1,{i for i in range(1,n+1)},0))

Submission status: Accepted

Solution code:
import itertools

n,m = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(m)]
num = list(range(1,n+1))
ans = 0
for l in itertools.permutations(num):
    if l[0]!=1:
        continue
    flag = True
    for i in range(len(l)-1):
        if not([l[i],l[i+1]] in edges or [l[i+1],l[i]] in edges):
            flag = False
            break
    if flag:
        # print(l)
        ans+=1
print(ans)

Submission status: Accepted

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


dp = [[0]*N for i in range(1 << N)]
dp[1][0]=1

for S in range(1 << N):
    for v in range(N):
        # if not v in S:
        if S & (1<<v) == 0:
            continue
        
        # sub = S - {v}
        sub = S ^ (1 << v)

        for u in range(N):
            # if u in sub and Adj[u][v] == 1:
            if (1 << u) & sub and Adj[u][v] :
                dp[S][v]+=dp[sub][u]

ans = sum(dp[(1<<N)-1][u] for u in range(1,N))

print(ans)

Submission status: Accepted

Solution code:
N, M = [int(x) for x in input().split()]
G = [[] for x in range(N)]
V = (1 << N) - 1
count = 0

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


def dfs(s, v):
    global count
    if v == V:
        count += 1
    for t in G[s]:
        if (v >> t & 1) == 0:
            dfs(t, v | 1 << t)


dfs(0, 1)

print(count)

Submission status: Accepted

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

from collections import deque

N, M = map(int, input().split())
Ms = {i:set() for i in range(1, N + 1)}
for _ in range(M):
    a, b = map(int, input().split())
    Ms[a].add(b)
    Ms[b].add(a)

all = set(range(1, N + 1))
q = deque()
q.append((1, [1]))

ans = 0
while q:
    n, v = q.popleft()
    if set(v) == all:
        ans += 1
        continue
    for to in Ms[n]:
        if not to in v:
            q.append((to, v + [to]))

print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc054/tasks/abc054_c
import itertools


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

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

seq = [i + 1 for i in range(1, N)]
# print(list(itertools.permutations(seq)))

count = 0
for l in itertools.permutations(seq):
    # print(l)
    connected = True
    for i in range(len(l) - 1):
        a = min(l[i], l[i+1])
        b = max(l[i], l[i+1])
        if i == 0 and [1, l[i]] not in C:
            connected = False
            break
        if [a, b] not in C:
            connected = False
            break
    if connected:
        # print(l)
        count += 1

print(count)

Submission status: Accepted

Solution code:
from itertools import permutations
N, M = map(int, input().split())
edge = []
for _ in range(M):
    a, b = map(int, input().split())
    edge.append(set((a, b)))

p = list(map(lambda x: [1] + list(x), permutations([i for i in range(2, N + 1)])))

ans = 0

for root in p:
    for i in range(len(root) - 1):
        if not set((root[i], root[i + 1])) in edge:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

import itertools

def array2d(dim1, dim2, init=None):
    return [[init for _ in range(dim2)] for _ in range(dim1)]

II = lambda: int(input())
MI = lambda: map(int, input().split())
MIL = lambda: list(MI())
MIS = lambda: input().split()


def main():
    N, M = MI()
    nb = array2d(N, N, False)
    for i in range(M):
        a, b = MI()
        a -= 1
        b -= 1
        nb[a][b] = nb[b][a] = True
    cnt = 0
    for perm in itertools.permutations(range(1, N)):
        p = [0] + list(perm)
        cnt += all([nb[p[i-1]][p[i]] for i in range(1, N)])
    return cnt

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

Submission status: Accepted

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

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

def print_set(s):
    for e in s:
        print(e + 1, end=" ")
    print()

checker = N*(N - 1)//2
cnt = 0
def dfs(visited: set, stack: list):
    global cnt
    if sum(list(visited)) == checker:
        cnt += 1
    elif len(stack) > 0:
        v = stack.pop()
        for i in range(N):
            if g[v][i] and not (i in visited):
                dfs(visited | set([i]), stack + [i])

dfs(set([0]), [0])
print(cnt)

Submission status: Accepted

Solution code:
def dfs(u, g, visited):
    # all visited
    if sum(visited) == len(visited):
        return 1

    res = 0
    for v in g[u]:
        if visited[v]:
            continue

        visited[v] = True
        # print("{} -> {}".format(u, v), visited)
        res += dfs(v, g, visited)
        visited[v] = False

    return res


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

    import collections
    g = collections.defaultdict(list)

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

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

    ans = dfs(0, g, visited)
    return ans


def main():
    print(solve())


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
T = {}
for i in range(M):
    a,b = map(int,input().split())
    if a not in T.keys():
        T[a] = []
    if b not in T.keys():
        T[b] = []
    T[a].append(b)
    T[b].append(a)

ans = 0
def dfs(graph,start,path):
    global ans
    global N
    path = path + [start]

    if len(path) == N:
        ans += 1

    for node in graph[start]:
        if node not in path:
            new = dfs(graph,node,path)

    return ans


print(dfs(T,1,[]))

Submission status: Accepted

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

def res(a, i, E, visit):
    global cnt
    if i == N:
        cnt += 1
        return None
    if E[a]:
        for b in E[a]:
            if b in visit:
                pass
            else:
                res(b, i+1, E, visit + [a])
        return None
    else:
        return None

cnt = 0
res(1, 1, E, [])
print(cnt)

Submission status: Accepted

Solution code:
from itertools import permutations as p
from collections import defaultdict as dd

n,m=map(int,input().split())
d=dd(list)
for _ in range(m):
    a,b=map(int,input().split())
    d[a].append(b)
    d[b].append(a)
d=dict(d)
ans=0

for i in p(range(2,n+1)):
    pos=1
    for j in i:
        if not j in d[pos]:
            break
        pos=j
    else:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
def multival(): return map(int,input().split())
def data(N=1): return [list(map(int,input().split())) for _ in range(N)]
mod = 10**9 + 7
inf = float("inf")

N,M = multival()
nemat = [[0]*N for _ in range(N)]
ans = 0
for _ in range(M):
    a,b = multival()
    a -= 1; b-= 1
    nemat[a][b] = 1
    nemat[b][a] = 1

def dfs(now=0,visited=[False]*N):
    visited[now] = True
    if all(visited) is True:
        global ans
        ans += 1
    for ne in range(N):
        if nemat[now][ne] == 1 and visited[ne] is False:
            dfs(ne,visited[:])
            # visited[:]
            # n方向に分かれて探索する際にそれぞれ別のvisitedを持たせる
            # そうしなければ例えばsample1では 1->2->3 と進んで全てに訪問済みの印が付く
            # 次に1->2と進もうとしても2は既にTrueに更新済みなので探索が終了してしまう

dfs()
print(ans)