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
input = sys.stdin.readline

used = []
connect = []
N = 0
M = 0


def main():
    global used
    global connect
    global N
    global M
    sc = Scan()
    N, M = sc.intarr()
    a = [0] * M
    b = [0] * M
    for i in range(M):
        aa, bb = sc.intarr()
        a[i] = aa - 1
        b[i] = bb - 1
    connect = [[0] * N for i in range(N)]
    used = [0] * N
    for i in range(M):
        connect[a[i]][b[i]] = 1
        connect[b[i]][a[i]] = 1

    print(dfs(0, 1))


def dfs(now, depth):
    global used
    global connect
    if used[now] == 1:
        return 0

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


class Scan():

    def intarr(self):
        num_array = list(map(int, input().split()))
        return num_array

    def intarr_ver(self, n):
        return [int(input()) for _ in range(n)]

    def strarr(self):
        line = input()
        array = line.split(' ')
        array[-1] = array[-1].strip('\n')
        return array


def display(array):
    for a in range(len(array)):
        if len(array) - a != 1:
            print(array[a], end=' ')
        else:
            print(array[a])


def gcd(a, b):  # 最大公約数
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):  # 最小公倍数
    return a * b // gcd(a, b)


main()

Submission status: Accepted

Solution code:
def dfs(g, v, i):
    if len(v) == len(g) - 1:
        return 1
    v.add(i)
    c = 0
    for u in g[i]:
        if u not in v:
            c += dfs(g, v, u)
    v.remove(i)
    return c


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

print(dfs(tree, set(), 0))

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = MAP()
G = list2d(N, N, 0)
for i in range(M):
    a, b = MAP()
    a -= 1; b -= 1
    G[a][b] = G[b][a] = 1

# dp[S][i] := 訪問済の頂点集合をSとして、最後に頂点iにいる場合の通り数
dp = list2d(1<<N, N, 0)
# 最初は頂点1にいる状態から
dp[1][0] = 1
for S in range(1, 1<<N):
    for i in range(N):
        # iが遷移元に含まれていない
        if not S & 1<<i:
            continue
        for j in range(N):
            # jが遷移元に含まれている(ので遷移先にはできない)
            if S & 1<<j:
                continue
            # 辺の張られた頂点間であれば遷移させる
            if G[i][j]:
                dp[S|1<<j][j] += dp[S][i]
# 全頂点訪問できた通り数を合計する
ans = sum(dp[(1<<N)-1])
print(ans)

Submission status: Accepted

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

import sys
from itertools import permutations

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = MAP()
edges = set()
for i in range(M):
    a, b = MAP()
    a -= 1; b -= 1
    edges.add((a, b))
    edges.add((b, a))

cnt = 0
for perm in permutations(range(N)):
    if perm[0] != 0:
        continue
    for i in range(N-1):
        a = perm[i]
        b = perm[i+1]
        if (a, b) not in edges:
            break
    else:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
def dfs(g, v, i):
    if len(v) == len(g) - 1: return 1
    v.add(i)
    c = 0
    for u in g[i]:
        if u not in v: c += dfs(g, v, u)
    v.remove(i)
    return c

n, m = map(int, input().split())
g = [list() for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
print(dfs(g, set(), 0))

Submission status: Accepted

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

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

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

transported = [0]
count = 0

def dfs(loc):
    global count
    if graph[loc] != []:
        for i in graph[loc]:
            if i not in transported:
                transported.append(i)
                dfs(i)
                transported.remove(i)

        if len(transported) == n:
            count += 1



for i in graph[0]:
    transported = [0, i]
    dfs(i)

print(count)

Submission status: Accepted

Solution code:
import sys
import itertools
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,M=map(int,input().split())
    edge=[[] for _ in range(N)]
    for i in range(M):
        a,b=map(lambda x:int(x)-1,input().split())
        edge[a].append(b)
        edge[b].append(a)
    l=list(range(1,N))
    ps=itertools.permutations(l)
    ans=0
    for p in ps:
        node=0
        for nextnode in p:
            if nextnode in edge[node]:
                node=nextnode
            else:
                break
        else:
            ans+=1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# 深さ優先探索
def dfs(V, closed): # V:探索頂点, closed:探索済み頂点リスト
 
    # 全頂点を探索したとき
    if not False in closed:
        return 1
    
    answer = 0
    for i in range(N):
        if not graph[V][i]:
            continue
        if closed[i]:
            continue
 
        # 頂点iを探索済みにする
        closed[i] = True
        answer += dfs(i,closed)
 
        # 最深まで探索したとき
        closed[i] = False
    
    return answer
 
N,M = map(int,input().split())
graph = [[False for i in range(N)] for j in range(N)]
 
for i in range(M):
    a,b = map(int,input().split())
    graph[a-1][b-1] = graph[b-1][a-1] = True
 
closed_list = [False]*N
closed_list[0] = True
 
print(dfs(0,closed_list))

Submission status: Accepted

Solution code:
import sys
# 再帰上限を引き上げる
sys.setrecursionlimit(10**6)

####
# DFS(深さ優先探索

count = 0
def dfs(graph, v, seen):
    #print(seen)
    # Falseがない、つまり頂点が1個しかない場合は、1を返す
    if not False in seen:
        global count
        count += 1
        return
    
    # 頂点Vから行ける頂点を全探索
    for i in graph[v]:
        # 行ける場所はTrueである。
        if seen[i]:
            continue
        
        # いったんTrueにして
        seen[i] = True
        # 探索したら
        dfs(graph, i, seen)
        # 戻す
        seen[i] = False
        
    return
        
        

####

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

# グラフを作る
graph = [[] for i in range(N)]
#print(graph)

for i in range(M):
    a, b = map(int, input().split())
    # index番号にあわせたいので、1引く
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    
seen = [False for i in range(N)]
seen[0] = True
dfs(graph, 0, seen)

# 全探索できた数を表示
print(count)

Submission status: Accepted

Solution code:
import sys

# 再帰上限を引き上げる
sys.setrecursionlimit(10**6)

count = 0
def dfs(graph, v, seen):

    if not False in seen:
        global count
        count += 1
        return

    # 頂点vから行ける頂点を全探索
    for i in graph[v]:
        if seen[i]:
            continue
        seen[i] = True
        dfs(graph, i, seen)
        seen[i] = False
    
    return

# ここから本文
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)

seen = [False for i in range(N)]
seen[0] = True
dfs(graph, 0, seen)

print(count)

Submission status: Accepted

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

g = [[] for _ in range(N)]

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

visited = [False for _ in range(N)]

def dfs(v, visited):
  if all(visited):
    return 1
  total = 0
  for cv in g[v]:
    if not visited[cv]:
      visited[cv] = True
      total += dfs(cv, visited)
      visited[cv] = False
  return total
    
visited[0] = True
ret = dfs(0, visited)
print(ret)

Submission status: Accepted

Solution code:
import itertools
 
N, M = map(int, input().split())
graph = [[0] * N for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    graph[a-1][b-1] = 1
    graph[b-1][a-1] = 1
 
p = list(itertools.permutations(range(N)))
 
Sum = 0
 
for i in range(len(p)):
    if p[i][0] != 0:
        break
    for j in range(N - 1):
        if graph[p[i][j]][p[i][j + 1]] != 1:
            break
        elif j == N - 2:
            Sum += 1
 
print(Sum)

Submission status: Accepted

Solution code:
from collections import deque

def dfs(corrent, cnt):
  if cnt == N-1:
    return 1
  visited[corrent] = True
  ret = 0
  for to in graph[corrent]:
    if visited[to] == True:
      continue
    ret += dfs(to, cnt+1)
  visited[corrent] = False
  return ret


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

ans = 0
visited = [False]*(N)

for _ in range(M):
  x, y = map(int, input().split())
  x -= 1
  y -= 1
  graph[x].append(y)
  graph[y].append(x)

print(dfs(0, 0))

Submission status: Accepted

Solution code:
from itertools import permutations

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

patterns = list(permutations(range(n)))

g = [ [False for _ in range(n)] for _ in range(n) ]
for a, b in ab:
    g[a-1][b-1] = True
    g[b-1][a-1] = True

ans = 0
for p in patterns:
    if p[0] != 0:
        continue
    ok = True
    for i in range(n-1):
        if not g[p[i]][p[i+1]]:
            ok = False
    if ok:
        ans += 1
print(ans)

Submission status: Accepted

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

P = []
V = [False]*N
V[0] = True
p = [0] + [None]*(N-1)
def dfs(i):
    if i==N:
        P.append(p[:])
        return
        
    for v, visited in enumerate(V):
        if not visited:
            p[i] = v
            V[v] = True
            dfs(i+1)
            V[v] = False

dfs(1)

ans = 0
for p in P:
    ok = True
    for i in range(N-1):
        if not E[p[i]][p[i+1]]:
            ok = False
            break
    if ok: ans+=1
print(ans)

Submission status: Accepted

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

import copy
import sys
input = sys.stdin.readline

# 頂点, 辺の数
N, M = map(int, input().split())

# グラフのリスト
# 各頂点からどこの頂点に向かう辺があるかどうかという情報
Graph_list = [[] for i in range(N)]

# 入力
for i in range(M):
    a, b = map(int, input().split())
    a += -1
    b += -1

    # 無向グラフなのでa, b両方
    Graph_list[a].append(b)
    Graph_list[b].append(a)

ans_count = 0           # 正解の経路の数
visited = [False] * N
visited[0] = True

def dfs(i, current, visited):   
    # 頂点をN個通ったら終了処理
    if i >= N-1:

        # 全ての点に到達している場合
        if all(visited):
            global ans_count
            ans_count += 1
            return 
        return 

    for j in Graph_list[current]:
        if visited[j] == False:
            # 現在地を書き込む
            visited[j] = True
            # 次の点に移動する        
            dfs(i + 1, j, visited)

            visited[j] = False

dfs(0, 0, visited)
print(ans_count)

Submission status: Accepted

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

for _ in range(m):
    a, b = map(int, input().split())
    ab.add((a, b))
    ab.add((b, a))

cnt = 0
for x in itertools.permutations(range(1, n + 1)):
    if x[0] != 1:
        break
    flag = True
    for i in range(len(x)-1):
        if (x[i], x[i + 1]) not in ab:
            flag = False
            break
    if flag:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
from collections import deque

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

E = [[] for i in range(n+1)]

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

   
check = [0]*n
count = 0
def dfs(i):
    check[i-1] = 1
    result = 0
    if not 0 in check:
        
        return 1
        

    for j in E[i]:
        if check[j-1] == 0:
            check[j-1] = 1
            result += dfs(j)
            check[j-1]=0

    return result


print(dfs(1))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
N, M = map(int, input().split())
G = {k: [] for k in range(N)}
for _ in range(M):
    a, b = map(int, input().split())
    # 無向グラフ
    G[a-1].append(b-1)
    G[b-1].append(a-1)

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


def dfs(v):
    if all(visited):
        return 1
    r = 0
    for nv in G[v]:
        if visited[nv] is False:
            visited[nv] = True
            r += dfs(nv)
            visited[nv] = False
    return r


print(dfs(0))

Submission status: Accepted

Solution code:
import copy
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
cnt = 0
fin = set([i + 1 for i in range(n)])
def path(now, edges, past):
    global cnt
    if set(past) == fin:
        cnt += 1
        return 0
    for i in range(len(edges)):
        if now == edges[i][0] and edges[i][1] not in past:
            new_now = edges[i][1]
            new_edges = copy.deepcopy(edges)
            new_past = copy.deepcopy(past)
            new_edges.pop(i)
            new_past.append(edges[i][1])
            # print("now", now, "edges", edges, "new", new_edges, "past", past, "cnt", cnt)
            path(new_now, new_edges, new_past)
        elif now == edges[i][1] and edges[i][0] not in past:
            new_now = edges[i][0]
            new_edges = copy.deepcopy(edges)
            new_past = copy.deepcopy(past)
            new_edges.pop(i)
            new_past.append(edges[i][0])
            # print("now", now, "edges", edges, "new", new_edges, "past", past, "cnt", cnt)
            path(new_now, new_edges, new_past)

for i in range(m):
    if ab[i][0] == 1:
        edges = copy.deepcopy(ab)
        edges.pop(i)
        path(ab[i][1], edges, [1, ab[i][1]])
    elif ab[i][1] == 1:
        edges = copy.deepcopy(ab)
        edges.pop(i)
        path(ab[i][0], edges, [1, ab[i][0]])
print(cnt)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

def dfs():
    path = 1
    lst_path = []
    lst_path.append((0, path))
    cnt = 0
    while len(lst_path) > 0:
        node, path = lst_path.pop()
        for i in G[node]:
            if not path & (1 << i):
                if path + (1 << i) == -1 + (1 << N):
                    cnt += 1
                    continue
                lst_path.append((i, path + (1 << i)))
    return cnt

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)
    
result = dfs()
print(result)

Submission status: Accepted

Solution code:
import itertools


N, M = map(int, input().split())
graph = [[False]*N for _ in range(N)]

for _ in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    graph[a][b] = True
    graph[b][a] = True

ans = 0
for x in itertools.permutations(range(1, N)):
    # このxの順番で訪問できるか確かめる
    flag = True
    now = 0
    for e in x:
        if not graph[now][e]:
            flag = False
        now = e
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from copy import copy
N, M = map(int, input().split())
br = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    br[a-1].append(b-1)
    br[b-1].append(a-1)
ans = 0
stack = []
seen = [False]*N
seen[0] = True
stack.append((0, copy(seen)))
while len(stack):
    n, s = stack.pop()
    f = False
    for m in br[n]:
        if not s[m]:
            s2 = copy(s)
            s2[m] = True
            stack.append((m, s2))
            f = True
    if not f and not False in s:
        ans += 1
print(ans)

Submission status: Accepted

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

Visit_list = [True] + [False for _ in range(n-1)]
count = 0

def Path(dict, start, Visited):

    if all(Visited):
        global count
        count += 1
        return

    for node in dict[start]:
        if Visited[node] == False:
            Visited[node] = True
            Path(dict, node, Visited)
            Visited[node] = False
    return

Path(Adj_dict, 0, Visit_list)
print(count)

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)
ans = 0


def dfs(v, history):
    if len(history) == N:
        global ans
        ans += 1
    else:
        children = graph[v]
        for child in children:
            if child not in history:
                dfs(child, history + (child,))


def solve():
    dfs(1, (1,))
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys

# 再帰上限を引き上げる
sys.setrecursionlimit(10**6)

count = 0
def dfs(graph, v, seen):

    if not False in seen:
        global count
        count += 1
        return

    # 頂点vから行ける頂点を全探索
    for i in graph[v]:
        if seen[i]:
            continue
        seen[i] = True
        dfs(graph, i, seen)
        seen[i] = False
    
    return

# ここから本文
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)

seen = [False for i in range(N)]
seen[0] = True
dfs(graph, 0, seen)

print(count)

Submission status: Accepted

Solution code:
#54c
import itertools
N,M = map(int, input().split())

from_to_dict = dict()

for i in range(M):
    a,b = map(int, input().split())
    
    if a in from_to_dict:
        from_to_dict[a].add(b)
    else:
        from_to_dict[a] = set([b])
        
    if b in from_to_dict:
        from_to_dict[b].add(a)
    else:
        from_to_dict[b] = set([a])
        
#候補は全部で8! = 40320通り。総当たりでOK
candidate_list = [i+1 for i in range(N)]
ans = 0

for candidate in list(itertools.permutations(candidate_list)):
    if candidate[0] == 1:
        for i in range(len(candidate)-1):
            from_node = candidate[i]
            to_node = candidate[i+1]

            if to_node not in from_to_dict[from_node]:
                break
        else:
            ans += 1
                          
print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
N,M=map(int,input().rstrip().split())
G=[[0 for _ in range(N)] for __ in range(N)]
used=[0 for _ in range(N)]
used[0]=True

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

def resolve():
    print(dfs(0,used))


def dfs(v,used):
    if not False in used:
        return 1
    ans=0
    for i in range(N):
        if G[v][i]==False:
            continue
        if used[i]==True:
            continue

        used[i]=True
        ans+=dfs(i,used)
        used[i]=False
    return ans

    



from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3 3
1 2
1 3
2 3"""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """7 7
1 3
2 7
3 4
4 5
4 6
5 6
6 7"""
        output = """1"""
        self.assertIO(input, output)

if __name__ == "__main__":
    #unittest.main()
    resolve()

Submission status: Accepted

Solution code:
import sys
import itertools


def check(i,array):
    now=0
    while True:
        flag=0
        if(now==len(i)-1):
            return 1
        for x in array:
            if(i[now]==x[0] and i[now+1]==x[1] or \
                i[now]==x[1] and i[now+1]==x[0]):

                flag=1
                now+=1
                break

        if(flag==0):
            return 0


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

    array=[]
    sum=0

    for _ in range(0, M):
        array.append(list(map(int,input().split())))


    for i in itertools.permutations(range(1,N+1),N):
        if(i[0]==1):
            sum += check(i,array)
    print(sum)

main()

Submission status: Accepted

Solution code:

from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations
import sys
import bisect
import string
import math
import time
from fractions import gcd
#import random


def I(): return int(input())


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


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['Yes', 'No']
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)


# show_flg = False
show_flg = True


def main():
    N, M = MI()
    graph = [[] for i in range(N+1)]
    ans = 0

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

    q = deque()
    q.append((1, set([1])))

    while len(q) != 0:
        edge, visited = q.popleft()
        nxt = graph[edge]

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

        for i, e in enumerate(nxt):
            if e not in visited:
                v = visited.copy()
                v.add(e)
                q.append((e, v))
            # else:
            #     print('stop', e, visited)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc148/submissions/9089396

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)

memo = {}
all_use = (1 << N) - 1

def rec(v, use):
    if use == all_use:
        return 1

    key = (v, use)
    if key in memo:
        return memo[key]

    res = 0
    for u in graph[v]:
        if (use >> u) & 1 == 1:
            continue

        use ^= 1 << u
        res += rec(u, use)
        use ^= 1 << u

    memo[key] = res
    return res

print(rec(0, 1))

Submission status: Accepted

Solution code:
import itertools


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

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def solve():
    def dfs(node, path, rest):
        if rest == 0:
            nonlocal ans
            ans += 1
        for next_node in adj[node]:
            if next_node not in path:
                dfs(next_node, path + [next_node], rest - 1)
                
    
    from sys import stdin
    f_i = stdin
    
    N, M = map(int, f_i.readline().split())
    
    adj = [[] for i in range(N)]
    for i in range(M):
        a, b = map(int, f_i.readline().split())
        a -= 1
        b -= 1
        adj[a].append(b)
        adj[b].append(a)
    
    ans = 0
    dfs(0, [0], N - 1)
    
    print(ans)

solve()

Submission status: Accepted

Solution code:
import itertools
n,m = map(int,input().split())
s = set()
for i in range(m):
    a,b = map(int,input().split())
    s.add((a,b))
    s.add((b,a))
ans = 0
#print(s)
for i in itertools.permutations(range(2,n+1)):
    genzai = 1
    #print(i)
    for j in range(len(i)):
        if (genzai,i[j]) not in s:
            break
        genzai = i[j]
    else:
        ans += 1
print(ans)

Submission status: Accepted

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


#まず各頂点ごとに、どの頂点とつながってるかのリスト作る？
cho=[]
for i in range(n):
  temp=[]
  for x,y in li:
    if x==i+1:
      temp.append(y)
    if y==i+1:
      temp.append(x)
  cho.append(temp)
#cho[0]は、頂点1がどの頂点とつながってるかを記録してる


ans=0

#全ての頂点を訪問するまで深堀り続けるコードを書く。
#全てを訪問する前に、訪問済み頂点に来てしまったらbreak。
zumi=[1]
queue=[[cho[0],0,len(cho[0])]]
dankai=0

#print(queue)
while 1:
  #print("今は",dankai,"段目のを調べてます")
  if queue[dankai][1]<queue[dankai][2]:
    bango=queue[dankai][0][queue[dankai][1]]
    if bango not in zumi: #それが訪問済みの点でなければ、次にその頂点のchoを調べよう。
      dankai+=1
      #print("訪問済みじゃないので次の段を調べます")
      zumi.append(bango) #それを訪問済みにする。
      queue.append([cho[bango-1],0,len(cho[bango-1])])
      #「その頂点番号につながってる頂点」「その段階において、何番目を現在調査中か」「その段階の長さ」
      if dankai==n-1:
        ans+=1 #全部の頂点を調べ終わったら、答えが増えたということのため、+1する。
    else: #それが訪問済みの点であれば、同じ段階の次の点を訪問しよう
      #print("これは訪問済みなので同じ",dankai,"段目の次の頂点を調べます")
      queue[dankai][1]+=1
  else:
    #print("どうやらこの段目にはもう頂点がないので、ひとつ前の段に戻り、その段の次の頂点に移ります")
    dankai-=1
    if dankai<0:
      break
    #その段目の番号について、訪問済み
    zumi.pop()
    queue.pop()
    queue[dankai][1]+=1
    #そうやっていって、cho[0]の点を全て調べ終わってしまったら、末尾を削除し、上の段階に戻る。
print(ans)

Submission status: Accepted

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

path_matrix = []

#無向行列の初期化
for n in range(N):
    path_matrix.append([False] * N)

#まず無向グラフを表す行列を作る
for m in range(M):
    a,b = map(int, input().split())
    path_matrix[a-1][b-1] = True
    path_matrix[b-1][a-1] = True
#無向グラフを表す行列はpath_matrix[i][j]iの部分が各頂点でjが他の頂点との繋がりを意味する
#最初はvisited、つまり訪問したことのあるノードはひとつもないので、Falseにする
visited = [False] * N #この問題は各頂点をすべて通る方法を調べること
def dfs(now,depth):
    if visited[now]:#もし現在位置が訪問済みなら
        return 0
    if depth == N-1:#もし深さが最大までいったらすべての頂点を探索し終えたので１を返す
        return 1
    
    visited[now] = True#現在位置を訪問済みにする(これをしないとループし続ける)
    total_path = 0
    for i in range(N):
        if path_matrix[now][i]:#もし飛べる先があるのなら、その飛んだ先のノードで今いる位置と深さを更新した上で、もっと掘り下げてみる
            total_path += dfs(i,depth+1)#もし深さが最大まで行ったらすべての頂点について探索が終了したので1加える

    visited[now] = False

    return total_path


print(dfs(0,0))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
sys.setrecursionlimit(10**7)
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf')
ans = 0 ;count = 0 ;pro = 1

n,m=map(int,input().split())
data=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1;b-=1
    data[a].append(b)
    data[b].append(a)
def dfs(node,s):
    # print(node,s)
    if len(s)==n:
        global count
        count+=1
    s=s.copy()
    for vi in data[node]:
        if vi not in s:
            dfs(vi,s|{vi})
dfs(0,{0})
print(count)

Submission status: Accepted

Solution code:
import itertools

def main():
    N, M = map(int, input().split())
    VE = tuple(tuple(map(lambda x: int(x)-1, input().split())) for _ in range(M))
    # print(VE)

    adj_mat = [[0 for _ in range(N)] for _ in range(N)]
    for ve in VE:
        adj_mat[ve[0]][ve[1]] = 1
        adj_mat[ve[1]][ve[0]] = 1
    # for row in adj_mat:
    #     print(row)

    ans = 0
    for perm in itertools.permutations([i for i in range(1, N)]):
        # print(perm)
        flag = True
        now_V = 0
        for next_V in perm:
            # print('{} to {}'.format(now_V, next_V))
            # print('{}'.format(adj_mat[now_V][next_V]))
            if not adj_mat[now_V][next_V]:
                flag = False
                break
            now_V = next_V
        if flag:
            ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

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

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

if N == 1:
    print(1)
    exit()

for x in itertools.permutations(range(1, N), N-1):
    prev = 0
    for i in range(N-1):
        if G[prev][x[i]] == 0:
            break

        prev = x[i]

        if i == N-2:
            cnt += 1

print(cnt)