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
import math
import itertools
def input():
    return sys.stdin.readline()[:-1]

n,m=map(int,input().split())
g = [[]for i in range(n)]
lis = [i for i in range(2,n+1)]

for i in range(m):
    a,b=map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
ans=0
for i in itertools.permutations(lis):
    now = 0
    jud = True
    for j in list(i):
        if j-1 not in g[now]:
            jud = False
            continue
        else:
            now = j-1

    if jud==True:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
def DFS(now, visited):
    ans = 0
    if all(visited):
        return 1
    for i in range(N):
        if path[now][i] and visited[i] == False:
            visited[i] = True
            ans += DFS(i, visited)
            visited[i] = False
    return ans
    


N, M = map(int, input().split())
path = [[0]*N for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    path[a-1][b-1] = 1
    path[b-1][a-1] = 1
visited = [False]*N
visited[0] = True
print(DFS(0, visited))

Submission status: Accepted

Solution code:
import sys
from collections import Counter
from collections import deque
import heapq
import math
import fractions
import bisect
import itertools
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n,m=mp()
tree=[[False]*(n+1) for i in range(n+1)]
for i in range(m):
    a,b=mp()
    tree[a][b]=True
    tree[b][a]=True
ans=0
for path in itertools.permutations(range(2,n+1), n-1):
    if tree[1][path[0]]:
        for i in range(n-1):
            if i==n-2:
                ans+=1
                break
            if not tree[path[i]][path[i+1]]:
                break

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

path = list(itertools.permutations(range(1, N), N-1))
ans = 0
for p in path:
  now = 0
  res = True
  for child in p:
    if child not in graph[now]:
      res = False
      break
    now = child
  ans += res

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

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

ans = 0
lsts = list(permutations(range(n)))

for lst in lsts:
    if lst[0] != 0:
        continue
    now = 0
    for l in lst[1:]:
        if not l in graph[now]:
            break
        now = l
    else:
        ans += 1
        
print(ans)

Submission status: Accepted

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

for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    adj[a].append(b)
    adj[b].append(a)
    
sum=0
for i in permutations(list(range(1,n))):
    i = [0]+list(i)
    c=1
    for j in range(n-1):
        if not(i[j+1] in adj[i[j]]):
            c*=0
    sum+=c
            
print(sum)

Submission status: Accepted

Solution code:

#グラフの初期化
import itertools

n, m = map(int, input().rstrip().split())
mylist = [[0 for j in range(n)] for i in range(n)]

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

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

result = 0
for v in itertools.permutations(vist):
    index = 0
    mylist2 = mylist[:]
    past = 0
    for i in v:
        a = min(past, i)
        b = max(past, i)
        if mylist2[a][b] != 1:               
            break
        past = i
        index += 1
    if index == n-1:
        result += 1
        
print(result)

Submission status: Accepted

Solution code:
# n : ノード数
# m : パス数
n, m = map(int, input().split())

# iノード, jノードにパスがある場合はconn[i][j] = conn[j][i] = True
conn = []
for _ in [0]*n:
    conn.append([False]*n)

# iノードに訪れたことがある場合はvisited[i] = True
visited = [False] * n

# グラフ入力
# ノード番号から-1して0始まりにしておく
v = []
for _ in [0]*m:
    line = map(int, input().split())
    v.append([x-1 for x in line])

# connテーブルを初期化
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(0, n):
        if conn[now][i]: ret += dfs(i, depth+1)
    
    visited[now] = False

    return ret

print(dfs(0, 0))

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
adj = [[] for _ in range(N)] #隣接している街のリストを作る
for i in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    adj[a].append(b)
    adj[b].append(a)

def DFS(now, visited):
    global ans
    if len(visited) == N:
        ans += 1 #到着したら1回増やす
    else:
        for u in adj[now]:
            if u not in visited: #向かう道の中で訪れていない場所を攻める
                DFS(u, visited+[u])
                #もしappendにすると、visitedが他のルートを選んだ時
                #まえのvisitedを引きずってしまう
        return



ans = 0
visited = [0] #到達したところを記憶していく
DFS(0, visited)
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())))
ct = 0
N_lis = [(i + 2) for i in range(n - 1)]
Pat = itertools.permutations(N_lis)
for one_case in Pat:
    tmp = 1
    all_flag = True
    for j in one_case:
        flag = False
        for k in range(m):
            if AB[k][0] == tmp:
                if AB[k][1] == j:
                    tmp = j
                    flag = True
                    break
            elif AB[k][1] == tmp:
                if AB[k][0] == j:
                    tmp = j
                    flag = True
                    break
        if not flag:
            all_flag = False
            break
    if all_flag:
        ct += 1
print(ct)

Submission status: Accepted

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

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

#dp[S][v] := 頂点０から出発し、集合Sに含まれる頂点を全て訪れるpathのうち、頂点vが最後になるようなpathの総数
dp = [[0] * n for _ in range(1 << n)]

#dpの初期化 dp({0}, 0) = 1
dp[1][0] = 1

for S in range(1 << n):
    for v in range(n):
        #vがSに含まれていないときはパスする
        if S & (1 << v) == 0:
            continue
        
        #sub = S - {v}
        sub = S ^ (1 << v)
        
        for u in range(n):
            #subにuが含まれており、かつuとvが辺で結ばれている
            if sub & (1 << u) and P[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 = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(M)]

from collections import defaultdict

memo = defaultdict(list)

for ele in ab:
    memo[ele[0]-1].append(ele[1]-1)
    memo[ele[1]-1].append(ele[0]-1)

que = []
visited = defaultdict(int)
ans = [0]

def dfs(visited,node,pre_node,tmp_sum):
    if tmp_sum == N:
        ans[0] += 1
        return

    for nn in memo[node]:
        if nn == pre_node: continue
        if visited[nn]==1: continue
        visited[nn] = 1
        dfs(visited,nn,node,tmp_sum+1)
        visited[nn] = 0

    return
        
flag = [False]
visited[0]=1
dfs(visited,0,-1,1)

print(ans[0])

Submission status: Accepted

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

# 各edgeが結ばれているかどうかを二次元配列で保持(0:エッジなし, 1:エッジあり)
edges = [[0 for _ in range(n)] for _ in range(n)]
for i in range(m):
    a,b = map(int, input().split())
    edges[a-1][b-1] = 1
    edges[b-1][a-1] = 1

ans = 0
for l in permutations(range(1,n)):
    l = [0] + list(l)
    cnt = 1
    for i in range(n-1):
        # エッジを持たない場合はカウントしない
        if edges[l[i]][l[i+1]] == 0:
            cnt = 0
            break
    ans += cnt
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),N-1):
    l=[1]+list(i)
    ans+=sum(1 for edge in zip(l,l[1:])if tuple(sorted(edge))in edges)==N-1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque

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

def DFS(now, visited):
    if len(visited) == N:
        return 1
    else:
        count = 0
        for u in adj[now]:
            if u not in visited:
                count += DFS(u, visited+[u])
        return count


def main():
    queue = deque([0])
    visited = [0]
    ans = DFS(0, visited)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque

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

ans = 0

def DFS(now,visited):
    global ans
    if len(visited) == N:
        ans += 1
    else:
        for u in adj[now]:
            if u not in visited:
                DFS(u,visited+[u])

def main():
    queue = deque([0])
    visited = [0]
    DFS(0,visited)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
R=list(list(map(int,input().split())) for _ in range(M))
S=[i for i in range(2,N+1)]

import itertools
count=0
for p in itertools.permutations(S):
  damage=0
  p=list(p)
  q=[1]
  for j in range(N-1):
    q.append(p[j])
  for i in range(N-1):
    if not([q[i],q[i+1]] in R) and not([q[i+1],q[i]] in R):
      damage=1
  if not(damage):
    count+=1


print(count)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# input
from collections import deque
import itertools

n, m = map(int, input().split())
path = [[] for _ in range(n)]
for i in range(m):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    path[a].append(b)
    path[b].append(a)
# n-1 ! を全探索する
all_lis = itertools.permutations(range(1, n))  # 1(0)は出発点なので除く
# print(all_lis)

ans = 0
for i in all_lis:
    start = 0# これをfor の外においていて爆死。
    ok = 1
    for j in range(n - 1):
        if i[j] not in path[start]:
            ok = 0
            break
        else:
            start = i[j]
    if ok:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import permutations
input = sys.stdin.readline
N, M = map(int,input().rstrip().split())
node = []
for _ in range(M):
  a,b = map(int,input().rstrip().split())
  node.append((a,b))
  node.append((b,a))
ans = 0
for p in permutations(range(1,N+1)):
  flag = True
  if p[0] != 1:
    continue
  for i in range(N-1):
    if (p[i],p[i+1]) not in node:
      flag = False
  if flag:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
num_ver, num_edge = map(int,input().split())
# 隣接行列
graph_mat = [[0]*num_ver for _ in range(num_ver)]

for i in range(num_edge):
    start, goal = map(int,input().split())
    start -= 1
    goal -= 1
    graph_mat[start][goal] = 1
    graph_mat[goal][start] = 1

visited = [0] * num_ver

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

    for ver in range(num_ver):
        if graph_mat[now][ver]:
            num_path += dfs(ver, depth + 1)
    
    # 別の一筆書きの道として探索されることを考慮、もちろん頂点1についてはこれは意味ない
    visited[now] = 0

    return num_path
print(dfs(0,0))

Submission status: Accepted

Solution code:
num_ver, num_edge = map(int,input().split())
# 隣接行列
graph_mat = [[0]*num_ver for _ in range(num_ver)]

for i in range(num_edge):
    start, goal = map(int,input().split())
    start -= 1
    goal -= 1
    graph_mat[start][goal] = 1
    graph_mat[goal][start] = 1

visited = [0] * num_ver


#再帰関数
def dfs(now, depth):
    if visited[now]:
        return 0
    if depth == num_ver - 1:
        return 1

    visited[now] = 1
    total_paths = 0
    # 「同じ深さの処理」＝場合わけ
    for i in range(num_ver):
        if graph_mat[now][i]:
            total_paths += dfs(i, depth + 1)

    visited[now] = 0

    return total_paths

print(dfs(0, 0))

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
import math
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
from collections import deque
inf = 10 ** 15
mod = 10 ** 9 + 7

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


def dfs(visited, now):
    tmp = [visited[i] for i in range(n)]
    tmp[now] = True
    if all(tmp):
        return 1
    else:
        ret = 0
        for b in ab[now]:
            if not tmp[b]:
                ret+=dfs(tmp, b)
        return ret

print(dfs([False for i in range(n)], 0))

Submission status: Accepted

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

N,M = map(int,readline().split())
G = [[] for i in range(N)]

for i in range(M):
  a,b = map(int,readline().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)
  
ans = 0
stack = []
stack.append([0,set()])
while stack:
  v,visited = stack.pop()
  if v in visited:
    continue
  visited2 = visited.copy()
  visited2.add(v)
  if len(visited2) == N:
    ans += 1
    continue
  for child in G[v]:
    stack.append([child,visited2])

print(ans)

Submission status: Accepted

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

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

ans = []

def dfs(x):
  visited[x-1] = 1
  if visited == [1] * N:
    ans.append(1)
  for i in range(len(adj[x-1])):
    if visited[adj[x-1][i] - 1] == 0:
      dfs(adj[x-1][i])
  visited[x-1] = 0
      
dfs(1)
print(sum(ans))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

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

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

ans = []

def dfs(x):
  visited[x-1] = 1
  if visited == [1] * N:
    ans.append(1)
  for i in range(len(adj[x-1])):
    if visited[adj[x-1][i] - 1] == 0:
      dfs(adj[x-1][i])
  visited[x-1] = 0
      
dfs(1)
if ans == []:
  print(0)
else:
  print(sum(ans))

Submission status: Accepted

Solution code:
from itertools import permutations

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

ans = 0
lst = [i for i in range(n)]
lsts = list(permutations(lst, n))

for lst in lsts:
    if lst[0] != 0:
        continue
    now = 0
    for l in lst[1:]:
        if not l in graph[now]:
            break
        now = l
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N,M = map(int,input().split())
AB = [tuple(map(int,input().split())) for _ in range(M)]

A = [[False for _ in range(N)] for _ in range(N)]
for a,b in AB:
    A[a-1][b-1] = True
    A[b-1][a-1] = True

# 頂点を巡る順番を順列で生成する
from itertools import permutations
Ps = permutations([i for i in range(1,N)])

ans = 0
for P in Ps:
    flg = True
    x,y = 0,0
    for p in P:
        y = p
        # 経路がなければ
        if not A[x][y]:
            flg = False
            break
        x = p
    if flg:
        ans += 1

print(ans)

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

perms = permutations(range(1, N))
ans = 0

for perm in perms:
  now = 0
  for v in perm:
    if G[now][v] == 0:
      break
    now = v
  else:
    ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
#DFS
from collections import deque

N, M = map(int, input().split())
G = [[] for _ 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)
  
stack = deque([(0, 0)])
visited = [0] * N
depth = 0
ans = 0
while stack:
  now, depth = stack.pop()
  if depth == N-1:
    ans += 1
    continue
  visited[depth] = now
  for nxt in G[now]:
    if nxt not in visited[:depth+1]:
      stack.append((nxt, depth+1))
    
print(ans)

Submission status: Accepted

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

visit = [0] * (n + 1)
ans = 0


def dfs(now, depth):
    global ans
    if visit[now]:
        pass
    if depth == n:
        ans += 1

    visit[now] = 1
    if graph[now]:
        for i in graph[now]:
            if visit[i] == 0:
                dfs(i, depth + 1)
    visit[now] = 0


dfs(1, 1)
print(ans)

Submission status: Accepted

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

visit = [0] * (n + 1)


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

    count = 0
    visit[now] = 1
    if graph[now]:
        for i in graph[now]:
            count += dfs(i, depth + 1)
    visit[now] = 0

    return count


ans = dfs(1, 1)
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import permutations
from collections import Counter


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, M = list(map(int,_in[0].split(' ')))  # type:list(int)
    graph = []
    for i in range(M):
        _ = list(map(int,_in[i+1].split(' ')))  # type:list(int)
        graph.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    con = [[] for i in range(N)]
    for a,b in graph:
        a -= 1
        b -= 1
        con[a].append(b)
        con[b].append(a)
    for i, _ in enumerate(con):
        con[i] = Counter(con[i])

    cnt = 0
    for cand in permutations(range(1,N)):
        _cand = (0,)+cand
        mult = 1
        for v,nv in zip(_cand[:-1],_cand[1:]):
            try:
                mult *= con[v][nv]
            except:
                mult = 0
                break
        cnt += mult
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)

if __name__ == "__main__":
    main()

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:

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

def mkmap(N, M):
    mapdic = {}
    for i in range(1, N+1):
        mapdic[str(i)] = [] 
    for j in range(M):
        pathA, pathB = map(str, input().split())
        mapdic[pathA] = mapdic[pathA] + [pathB]
        mapdic[pathB] = mapdic[pathB] + [pathA]
    return mapdic

mapdic = mkmap(N, M)
import copy

roots = [[]]*N
roots[0] = ["1"]
for i in range(N-1):
    root = copy.deepcopy(roots[i])
    for nowroot in root:
        for nextroot in mapdic[nowroot[-1]]:
            if  i >= 1:
                if not nextroot in nowroot:                    
                    roots[i+1] = roots[i+1] + [nowroot + nextroot]
                else:
                    pass
            else:
                roots[i+1] = roots[i+1] + [nowroot + nextroot]


List = [str(n+1) for n in range(N)]
check = "".join(List)
ans = 0
for i in roots[-1]:
    TF = "".join(sorted(list(i))) == check
    if TF:
        ans = ans + 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

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

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

lis = list(c for c in permutations(range(n), n) if c[0] == 0)

res = 0
for li in lis:
    flg = True
    for i in range(1, n):
        if li[i-1] in g[li[i]]:
            continue
        else:
            flg = False
            break
    if flg:
        res += 1
print(res)

Submission status: Accepted

Solution code:
from itertools import permutations

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

ans = 0
for l in permutations(range(1,N)):
    l = [0] + list(l)
    cnt = 1
    for i in range(N-1):
        if edges[l[i]][l[i+1]] == 0:
            cnt = 0
    ans += cnt

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

G = [[] for i in range(N)]
for i in range(M):
    a, b = ab[i]
    G[a-1].append(b-1)
    G[b-1].append(a-1)

ls = [i for i in range(1, N)]
ans = 0
for route in itertools.permutations(ls, N-1):
    pre = 0
    for i in range(N-1):
        next_v = route[i]
        if next_v not in G[pre]:
            break
        pre = next_v
    else: ans += 1

print(ans)

Submission status: Accepted

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

G = [[] for i in range(N)]
for i in range(M):
    a, b = ab[i]
    G[a-1].append(b-1)
    G[b-1].append(a-1)

def rec(v, memo):
    if memo.count(-1) == 1:
        return 1

    memo[v] = 1

    count = 0
    for next_v in G[v]:
        if memo[next_v] == -1:
            count += rec(next_v, memo)

    memo[v] = -1
    return count

memo = [-1 for i in range(N)]
print(rec(0, memo))

Submission status: Accepted

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

G = [[] for i in range(N)]
for i in range(M):
    a, b = ab[i]
    G[a-1].append(b-1)
    G[b-1].append(a-1)

def rec(v, memo):
    memo[v] = 1

    if -1 not in memo:
        memo[v] = -1
        return 1

    count = 0
    for next_v in G[v]:
        if memo[next_v] == -1:
            count += rec(next_v, memo)

    memo[v] = -1
    return count

memo = [-1 for i in range(N)]
print(rec(0, memo))

Submission status: Accepted

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

import itertools
per = itertools.permutations([i for i in range(1,N+1)])
ans = 0
for item in per:
    if item[0] != 1:
        continue
    f = True
    for ind,num in enumerate(item):
        if ind + 1<= N-1:
            nnum = item[ind+1]
            if nnum not in edge[num]:
                f = False

    if f:
        ans += 1

print(ans)

Submission status: Accepted

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

result = []

import copy
def dfs(n,used,d):
    if d == N-1:
        result.append(1)
    for e in edge[n]:
        if used[e] == False:
            usedf = copy.deepcopy(used)
            usedf[e] = True
            dfs(e,usedf,d+1)


used = [False]*(N+1)
used[1] = True
dfs(1,used,0)
print(len(result))

Submission status: Accepted

Solution code:
from collections import defaultdict
import queue

def dfs(P,V,s,cnt):
    V[s] = 1
    # print(V)
    # 全部辿ったらインクリメント
    if len(V) == sum(V):
        cnt += 1
        # print('count',str(cnt))

    for t in P[s]:
        if V[t] > 0:
            continue
        # print(s,t)
        V,cnt = dfs(P,V,t,cnt)
    V[s] = 0
    return V,cnt

def main():
    N,M = [int(x) for x in input().split()]
    paths = []
    for _ in range(M):
        a,b = [int(x) for x in input().split()]
        paths.append((a,b))

    # 隣接リスト
    P = defaultdict(list)
    for a,b in paths:
        P[a-1].append(b-1)
        P[b-1].append(a-1)

    V = [0]*N
    s = 0
    cnt = 0
    # print(P)
    V,cnt = dfs(P,V,s,cnt)
    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

from itertools import permutations
c = 0
for p in permutations(range(1, N)):
    pi = 0
    for pj in p:
        if not pj in G[pi]:
            break
        pi = pj
    else:
        c += 1
print(c)

Submission status: Accepted

Solution code:
n,m=[int(x) for x in input().rstrip().split()]
l=[[]*n for i in range(n)]
done=[False for i in range(n)]
for i in range(m):
  a,b=[int(x) for x in input().rstrip().split()]
  l[a-1].append(b-1)
  l[b-1].append(a-1)


def bfs():
  stack=[[0,[]]]
  ans=0
  while(stack):
    now,visited=stack.pop(0)
    if len(visited)==n-1:
      ans+=1    
    for i in l[now]:
      if i not in visited:
        stack.append([i,visited+[now]])
  return ans

print(bfs())

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
p = [list(map(int, input().split())) for i in range(M)]
import itertools
v = list(map(list, itertools.permutations(range(2,N+1), N-1)))
cnt = 0
for i in range(len(v)):
    vit = True
    v_i = [1]+v[i]
    for j in range(N-1):
        if sorted(v_i[j:j+2]) not in p:
            vit = False
    if vit:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import itertools

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

edge = [[int(s) - 1 for s in input().split()] for _ in range(M)]
graph = [[] for _ in range(N)]
for i, j in edge:
    graph[i].append(j)
    graph[j].append(i)

result = 0
for path in itertools.permutations(range(1, N)):
    cnt = 0
    for p1, p2 in zip([0] + list(path[:-1]), list(path)):
        cnt += p2 in graph[p1]
    result += cnt == (N - 1)

print(result)

Submission status: Accepted

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

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


def DFS(now, visited):
    if all(visited):
        return 1
    ans = 0
    for i in range(N):
        if not pathmat[now][i]:
            continue
        if visited[i]:
            continue
        visited[i]=True
        ans += DFS(i, visited)
        visited[i]=False
    return ans

print(DFS(0,visited))

Submission status: Accepted

Solution code:
import itertools

N,M = map(int,input().split())
l = [ i for i in range(2,N+1)]

dist = {i:[] for i in range(1,N+1)}

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

cnt = 0

for v in itertools.permutations(l):
  a = 1  
  for v1 in v:
    if a in  dist.get(v1):
      a = v1
      if a == v[-1]:
        cnt += 1
      continue
    else:
      break

print(int(cnt))

Submission status: Accepted

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

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

ans = 0

def f(t, history):
    his = history[:]
    his[t] += 1
    global ans
    if sum(his)==n:
        ans += 1
    else:
        for i in L[t]:
            if his[i]==0:
                f(i, his)

f(0, [0]*n)
print(ans)

Submission status: Accepted

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

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

ans = 0
def f(t, history):
    his = history[:]
    his[t] += 1
    global ans
    if sum(his) == n:
        ans += 1
    else:
        for i in L[t]:
            if his[i] == 0:
                f(i, his)
            
f(0, [0]*n)
print(ans)