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())
Edge = [tuple(map(int, input().split())) for _ in range(M)]

Graph = [[] for _ in range(N)]
for a,b in Edge:
    Graph[a-1].append(b-1)
    Graph[b-1].append(a-1)


def dfs(v, seen):
    global Graph
    seen.add(v)
    if len(seen) == N:
        seen.remove(v)
        return 1
    Res = [dfs(nv, seen) for nv in Graph[v] if not nv in seen]
    seen.remove(v)
    return sum(Res)

print(dfs(0, set()))

Submission status: Accepted

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

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

color=["W" for i in range(N)]

clear=["B" for i in range(N)]

def path(x,d):
    if color[x-1]=="B":
        return False
        
    color[x-1]="B"

    if color==clear:
        color[x-1]="W"
        return True
    
    ans=0
    for i in range(len(A[x-1])):
        ans+=int(path(A[x-1][i],d+1))

    color[x-1]="W"
    return ans

print(path(1,0))

Submission status: Accepted

Solution code:

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

for i in range(M):
    a,b=map(int,input().split())
    path_matrix[a-1][b-1]=True
    path_matrix[b-1][a-1]=True
view=[False]*N

def path(x,depth):
    if view[x-1]:
        return False
    
    if depth==N-1:
        return True

    view[x-1]=True
    total_ans=0
    for i in range(N):
        if path_matrix[x-1][i]:
            total_ans+=int(path(i+1,depth+1))
    
    view[x-1]=False

    return total_ans

print(path(1,0))

Submission status: Accepted

Solution code:
import itertools

n,m=map(int,input().split())
rin=[[]for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  rin[a-1].append(b-1)
  rin[b-1].append(a-1)
  
li=[ i for i in range(2,n+1)]

ans=0

for v in itertools.permutations(li):
  pas=0
  ch=0
  st=1
  for x in range(n-1):
    if v[x]-1 not in rin[st-1]:
      ch+=1
      break
    else:
      st=v[x]
  if ch==0:
    ans+=1
    
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

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)

for lst in itertools.permutations([j for j in range(1,n)],n-1):
  now=0
  flag=True
  for i in range(n-1):
      if lst[i] not in graph[now]:
          flag=False
          break
      
      else:
          now=lst[i]

  if flag:
          ans+=1


print(ans)

Submission status: Accepted

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

G = [list() for _ in range(n + 1)]
for a, b in edges:
    G[a].append(b)
    G[b].append(a)

checked = [False for _ in range(n)]

ans = 0

def dfs(v):
    global ans
    if all(checked):
        ans += 1
        return
    for u in G[v]:
        if not checked[u - 1]:
            checked[u - 1] = True
            dfs(u)
            checked[u - 1] = False
    return

checked[0] = True
dfs(1)
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

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

ans = 0

for i in itertools.permutations(range(n),n):
    #頂点が0のものだけ抽出
    if i[0] == 0:
        #確かめる
        for j in range(n):
            if j == n - 1:
                ans += 1
                break

            if not path[i[j]][i[j+1]]:
                break

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

LIS = [i for i in range(2, n + 1)]
big_lis = list(itertools.permutations(LIS))
L = len(big_lis)

ans2 = 0
for j in range(L):
    i = 1
    ans1 = 1
    for k in big_lis[j]:
        if((i, k) not in lis) & ((k, i) not in lis):
            ans1 = 0
        i = k
    ans2 += ans1
print(ans2)

Submission status: Accepted

Solution code:
def abc054c_one_stroke_path():
    import itertools
    n, m = map(int, input().split())
    e = [set() for _ in range(n + 1)]
    for _ in range(m):
        a, b = map(int, input().split())
        e[a].add(b)
        e[b].add(a)
    pattern = itertools.permutations(range(2, n + 1))
    cnt = 0
    for p in pattern:
        p_m = [1] + list(p)
        for i in range(n - 1):
            if p_m[i+1] not in e[p_m[i]]:
                break
        else:
            cnt += 1
    print(cnt)


abc054c_one_stroke_path()

Submission status: Accepted

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

def search(lst):
  if len(lst) == N:
    return 1
  else:
    a = lst[-1]
    next = [n for n in edges[a] if n not in lst]
    if len(next) == 0:
      return 0

    tot = 0
    for n in next:
      tot += search(lst + [n])
    
    return tot


ans = search([1])

print(ans)

Submission status: Accepted

Solution code:
import collections 
n,m = map(int,input().split())
g = collections.defaultdict(list)
for i in range(m):
  a,b= map(int,input().split())
  g[a-1].append(b-1)
  g[b-1].append(a-1)
  
#print(g)

ans = 0
def dfs(node,num,visit):
  visite = visit.copy()
  global ans
  num += 1
  if num == n:
    ans += 1
    return
  else:
    visite[node] = True
    for neib in g[node]:
      if visite[neib] == False:
        dfs(neib,num,visite)
  
visited = [False]*n
dfs(0,0,visited)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

N,M=map(int,input().split())
E=[[0]*(N+1) for _ in range(N+1)]

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

P=permutations([x for x in range(2,N+1)])

K=0
for p in P:
    Q=[1]+list(p)

    F=1
    for k in range(N-1):
        F*=E[Q[k]][Q[k+1]]

    K+=F
print(K)

Submission status: Accepted

Solution code:
from itertools import permutations

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

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

ans = 0

for p in permutations(range(N)):
    now = p[0]
    
    if now!=0:
        continue

    for i in range(1, N):
        if G[now][p[i]]==1:
            now = p[i]
        else:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools as it

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

#print(a)

#無向グラフのルート作成（リスト）
for i in range(len(a)):
    a.append([a[i][1],a[i][0]])
#print(a)


#１を始点とするルートを全探索で作成
lis  = list(it.permutations(range(2, n + 1)))
#print(lis)
for i in range(len(lis)):
    lis[i] = (1,) + lis[i]
#print(lis)

#リストに変換
lis2 = []
for i in range(len(lis)):
    lis[i] = list(lis[i])
    lis2.append(lis[i])
#print(lis2)

#ルート探索
#lis3 = []
ans = 0
for i in range(len(lis2)):
    check = True
    for j in range(len(lis2[i]) - 1):
        if lis2[i][j : j + 2] not in a:
            check = False
    if check:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools as it

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

#無向グラフのルート作成（リスト）
for i in range(len(a)):
    a.append([a[i][1],a[i][0]])

lis  = list(it.permutations(range(2, n + 1)))
for i in range(len(lis)):
    lis[i] = (1,) + lis[i]

lis2 = []
for i in range(len(lis)):
    lis[i] = list(lis[i])
    lis2.append(lis[i])

#ルート探索
ans = 0
for i in range(len(lis2)):
    check = True;
    for j in range(len(lis2[i]) - 1):
        if lis2[i][j : j + 2] not in a:
            check = False;
    if(check):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:

import itertools as itt

n, m = map(int, input().split())
l = set()
for i in range(m):
    a, b = map(int, input().split())
    l.add((a, b))
    l.add((b, a))

lis = [i for i in range(1, n+1)]
p_lis = list(itt.permutations(lis))

cnt = 0

for i in range(len(p_lis)):
    if p_lis[i][0] != 1:
        continue
    flg = [0]*(n-1)
    for j in range(n-1):
        x = (p_lis[i][j], p_lis[i][j+1])
        if x in l:
            flg[j] = 1
    if all(flg):
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
from itertools import groupby, accumulate, product, permutations, combinations
import numpy as np
N, M = map(int, input().split())
adj = np.zeros((N,N),np.int64)
for i in range(M):
  a,b = map(lambda x:int(x)-1, input().split())
  adj[a,b] = 1
  adj[b,a] = 1
ans = 0
for per in permutations(range(1,N),N-1):
  if adj[0,per[0]]==0:
    continue
  for i in range(N-2):
    if adj[per[i],per[i+1]]==0:
      break
  else:
    ans += 1
print(ans)

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 path in itertools.permutations(range(N), N):
    if path[0] == 0: #先頭が頂点1の時
        for i in range(N):
            if i==N-1:
                ans += 1
                break
            if not graph[path[i]][path[i+1]]:
                break
print(ans)

Submission status: Accepted

Solution code:
#Nはノード数、Mはエッジ数
N, M = map(int, input().split())

path_matrix = []

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

#まず無向グラフを表す行列を作る
for m in range(M):
    line = map(int, input().split())
    paths = [x - 1 for x in line]
    path_matrix[paths[0]][paths[1]] = True
    path_matrix[paths[1]][paths[0]] = True

#最初はvisited、つまり訪問したことのあるノードはひとつもないので、Falseにする
visited = [False] * N


#再帰関数、ここが難しいかもしれない。
def dfs(now, depth):
    if visited[now]:
        return 0
    if depth == N - 1:
        return 1

    visited[now] = True
    total_paths = 0
    for i in range(0, N):
        if path_matrix[now][i]:
            total_paths += dfs(i, depth + 1)

    visited[now] = False

    return total_paths

print(dfs(0, 0))

Submission status: Accepted

Solution code:
import itertools

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

a = list(itertools.permutations(range(n)))
ans = 0
for i in a:
    if i[0] != 0:
        break
    for j in range(n-1):
        if g[i[j]][i[j+1]] == 0:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def dfs(v):
    if sum(visited) == N:
        return 1
    res = 0
    for nv in g[v]:
        if visited[nv]:
            continue
        visited[nv] = 1
        res += dfs(nv)
        visited[nv] = 0
    return res


N, M, *ab = map(int, open(0).read().split())
g = [[] for _ in range(N)]
for a, b in zip(*[iter(ab)] * 2):
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

visited = [0] * N
visited[0] = 1
print(dfs(0))

Submission status: Accepted

Solution code:
from itertools import permutations


N, M, *ab = map(int, open(0).read().split())
g = [[0] * N for _ in range(N)]
for a, b in zip(*[iter(ab)] * 2):
    g[a - 1][b - 1] = 1
    g[b - 1][a - 1] = 1

ans = 0
for path in permutations(range(1, N)):
    path = [0] + list(path)
    if all(g[v][nv] for v, nv in zip(path, path[1:])):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations, islice


def window(seq, n):
    it = iter(seq)
    result = tuple(islice(it, n))
    if len(result) == n:
        yield result
    for elem in it:
        result = result[1:] + (elem,)
        yield result


N, M, *ab = map(int, open(0).read().split())
g = [[0] * N for _ in range(N)]
for a, b in zip(*[iter(ab)] * 2):
    g[a - 1][b - 1] = 1
    g[b - 1][a - 1] = 1

ans = 0
for path in permutations(range(1, N)):
    path = [0] + list(path)
    if all(g[v][nv] for v, nv in window(path, 2)):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations


N, M, *ab = map(int, open(0).read().split())
g = [[] for _ in range(N)]
for a, b in zip(*[iter(ab)] * 2):
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

ans = 0
for path in permutations(range(1, N)):
    v = 0
    for nv in path:
        if nv not in g[v]:
            break
        v = nv
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

l = range(2, N + 1)

ans = 0

for p in itertools.permutations(l):
    # 試す順列を作る
    nums = [1]
    for n in p:
        nums.append(n)

    flag = True

    for i in range(N - 1):
        if nums[i + 1] in G[nums[i]]:
            continue
        else:
            flag = False
            break
    if flag == True:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

#隣接行列
path=[[False]* n for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    path[a][b] = True
    path[b][a] = True

ans = 0

for i in itertools.permutations(list(range(n))):
	#頂点１が始点
	if i[0]==0:
		# 生成した順列の中をさらにループ
		for j in range(n):
			# n - 1 まで続いたら条件を満たすパスが存在する
			if j == n-1:
				ans+=1
				break
			# i[j] から i[j + 1] に行くパスがなければ終了
			if not path[i[j]][i[j + 1]]:
				break
print(ans)

Submission status: Accepted

Solution code:
import copy


def dfs(i, path, reached, n):
    if reached[i]:
        return n
    reached[i] = True

    if all(reached):
        n += 1
        return n

    for p in path[i]:
        org_reached = copy.deepcopy(reached)
        n = dfs(p, path, org_reached, n)

    return n


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

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

    for a, b in AB:
        a -= 1
        b -= 1
        path[a].append(b)
        path[b].append(a)

    reached = [False for _ in range(N)]
    n = 0

    n = dfs(0, path, reached, n)
    print(n)


main()

Submission status: Accepted

Solution code:
from itertools import permutations

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

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys


def dfs(A: list):
    if len(A) == n:
        for i in range(len(A)-1):
            if A[i+1] not in node[A[i]]:
                break
            if i == n-2:
                ans[0] += 1
        return
    for v in range(2, n+1):
        if v not in A:
            A.append(v)
            dfs(A)
            A.pop()


n, m = map(int, input().split())
node = [set() for _ in range(n+1)]
for x in sys.stdin.readlines():
    a, b = map(int, x.split())
    node[a].add(b)
    node[b].add(a)
ans = [0]
dfs([1])
print(ans[0])

Submission status: Accepted

Solution code:
import itertools
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)
ans=0
for junretu in list(itertools.permutations(list(range(2,n+1)))):
  now=1
  flag=True
  for i in list(junretu):
    if not(i in edge[now]):
      flag=False
      break
    now=i
  if flag:
    ans+=1
print(ans)

Submission status: Accepted

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

res=0
for i in itertools.permutations(range(2,N+1),N-1):
    path=[1]+list(i)
    check=[sorted(path[i:i+2]) in edges for i in range(len(path)-1)]
    if not False in check:
        res+=1
print(res)

Submission status: Accepted

Solution code:
#
# abc054 c
#

import sys
from io import StringIO
import unittest
import itertools


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)


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

    R = itertools.permutations(range(1, N+1))

    ans = 0
    for r in R:
        flag = True
        r = list(r)
        if r[0] != 1:
            break
        for i in range(1, N):
            for p in P:
                if (r[i-1] == p[0] and r[i] == p[1]) or (r[i-1] == p[1] and r[i] == p[0]):
                    break
            else:
                flag = False
        if flag == True:
            ans += 1

    print(ans)


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

Submission status: Accepted

Solution code:
from networkx import *
N,M = map(int,input().split())
A = [list(map(int,input().split())) for m in range(M)]
G = Graph(A)
ans = 0

for n in range(2,N+1):
  for p in all_simple_paths(G,1,n):
    if len(p)==N:
      ans+=1

print(ans)

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())
    to[a-1].append(b-1)
    to[b-1].append(a-1)

ans = 0
v = [0] * N

def DFS(n):
    global ans
    v[n] = 1
    #print(v)
    if sum(v) == N:
        ans += 1
    for i in to[n]:
        if v[i] == 0:
            DFS(i)
    v[n] = 0

DFS(0)
print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m = map(int,input().split())
routes = list(itertools.permutations([i for i in range(2,n+1)]))
nodes = {}
ans = 0
for i in range(1,n+1):
    nodes[i] = []
for _ in range(m):
    a,b = map(int,input().split())
    nodes[a].append(b)
    nodes[b].append(a)
for i in range(len(routes)):
    jud = 1
    if routes[i][0] not in nodes[1]:
        jud = 0
    for j in range(n-2):
        if routes[i][j+1] not in nodes[routes[i][j]]:
            jud = 0
    ans += jud
print(ans)

Submission status: Accepted

Solution code:
import itertools
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)

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

def sati(x):
  #xはリスト[4,5,7]
  now=1
  for i in range(n-1):
    if not (x[i] in edge[now]):
      return 0
    now=x[i]
  return 1
ans=0
for i in all_lis:
  ans+=sati(i)
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
G = [[] for i in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
cnt = [0]
def dfs(V,s):
    V[s] = 1
    if sum(V) == N:
        cnt[0] += 1
    else:
        for adj in G[s]:
            if V[adj] == 0:
                dfs(V[:adj] + [1] + V[adj + 1:], adj)
dfs([0] * N,0)
print(cnt[0])

Submission status: Accepted

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

ans = 0
import itertools
for ptn in itertools.permutations(range(1,N)):
    ptn = list(ptn)
    for a,b in zip([0]+ptn, ptn):
        if not es[a][b]: break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

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

count = 0
prev[0] = 1

def keiro(pre,q,now):
    global count
    if len(q) == 0:
            return

    now = q.popleft()
    
    for no in g[now-1]:
        if pre[no-1] == 0:

            pre_1 = pre.copy()
            pre_1[no-1] = 1
            if sum(pre_1) == n:
                count+=1
                return
            q.append(no)
            keiro(pre_1,q,no)
        else:

            keiro(pre,q,no)


keiro(prev,deque([1]),1)
print(count)

Submission status: Accepted

Solution code:
n,m=list(map(int,input().split()))
#隣接リスト表現
es=[[0 for i in range(n)] for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  es[a-1][b-1]=1
  es[b-1][a-1]=1

# 再帰の深さが1000を超えそうなときはこれをやっておく
import sys
sys.setrecursionlimit(10**7)


#深さ優先探索
#n個の頂点が未探索であるとしておく
visited=[0 for i in range(n)]
check=[1 for i in range(n)]

def dfs(v,visited):
  #ansは頂点vから始まるパスの数
  ans=0
  #自分がいることろを探索済にしておく
  visited[v-1]=1

  if visited==check:
    visited[v-1]=0
    return 1
  #そこから行けるところに対して深さ優先探索
  for i in range(n):
    #つながっていて未探索
    if es[v-1][i]==1 and visited[i]==0:
        ans+=dfs(i+1,visited)
  #全部探索し終わったら今自分がいるところは未探索に戻しておく
  visited[v-1]=0
  return ans

print(dfs(1,visited))

Submission status: Accepted

Solution code:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip.split())
def main():
    n,m = LI()
    root = [[] for _ in range(n+1)]
    for _ in range(m):
        a,b = LI()
        root[a].append(b)
        root[b].append(a)

    pers = itertools.permutations(list(range(2,n+1)))
    ans = 0

    for per in pers:
        for i in range(n-1):
            if i == 0:
                now = 1
                next = per[0]
                if next not in root[now]:
                    break
            else:
                now = per[i-1]
                next = per[i]
                if next not in root[now]:
                    break
        else:
            ans += 1
    
    print(ans)
main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10**9)

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

    visited = [0] * N
    visited[0] = 1
    ans = [0]

    def stroke(u):
        #print("now={}, vis={}".format(u, visited))
        if visited == [1] * N:
            ans[0] += 1
            return
        for v in repn[u]:
            if visited[v] == 1: continue
            visited[v] = 1
            stroke(v)
            visited[v] = 0

    stroke(0)
    print(ans[0])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin
def input():
    return stdin.readline().strip()

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

# BFS
from collections import deque

# todoに(現在の頂点, [通った頂点の履歴])を追加する
first = [True] * n
first[0] = False
todo = deque([(0, first)])
ans = 0
while len(todo) > 0:
    now, history = todo.popleft()
    if not any(history):
        ans += 1
        continue
    for i in tree[now]:
        if history[i]:
            next_history = history.copy()
            next_history[i] = False
            todo.append((i, next_history))

print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m=map(int,input().split())
l=[[0]*n for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    l[a-1][b-1]=1
    l[b-1][a-1]=1
d=[int(i)+1 for i in range(n)]
ans=chk=0
for i in list(itertools.permutations(d,n)):
    chk=1
    if i[0]!=1: continue
    for j in range(n-1):
        chk*=l[i[j+1]-1][i[j]-1]
    ans+=chk
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
N, M = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(M)]
m = [set() for _ in range(27)]
for a, b in AB:
    m[a].add(b)
    m[b].add(a)

def main():
    ans = []
    def traverse(n, visits):
        visits = visits | set([n])
        if len(visits) == N:
            ans.append(1)
            return
        for c in m[n] - visits:
            traverse(c, visits)
    traverse(1, set())
    return len(ans)

print(main())

Submission status: Accepted

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

dp = [[0]*n for i in range(2**n)]
dp[1][0] = 1

for s in range(2**n):
    for v in range(n):
        if (s >> v) & 1:
            # t = s - {v}
            t = s ^ (1 << v)
            for u in g[v]:
                if (t >> u) & 1:
                    dp[s][v] += dp[t][u]
#print(dp)
ans = 0
for v in range(n):
    ans += dp[-1][v]
print(ans)

Submission status: Accepted

Solution code:
import itertools


def main():
    N, M = map(int, input().split())
    node_lst = [x for x in range(N)]
    edge_lst = [list(map(int, input().split())) for _ in range(M)]
    ans = 0

    for route in itertools.permutations(node_lst):
        is_visited = [False] * N
        is_visited[0] = True
        if route[0] != 0:
            continue

        for i in range(N - 1):
            if [route[i] + 1, route[i + 1] + 1] in edge_lst and is_visited[route[i + 1]] == False:
                is_visited[route[i + 1]] = True
            if [route[i + 1] + 1, route[i] + 1] in edge_lst and is_visited[route[i + 1]] == False:
                is_visited[route[i + 1]] = True

        if is_visited == [True] * N:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools
import math
N,M = (int(T) for T in input().split())
List = [[] for TM in range(0,M)]
for TM in range(0,M):
    List[TM] = [int(T) for T in input().split()]
    
Node = [[] for TN in range(0,N+1)]
for TM in range(0,M):
    Node[List[TM][0]].append(List[TM][1])
    Node[List[TM][1]].append(List[TM][0])
    
Count = math.factorial(N-1)
for TI in itertools.permutations(range(2,N+1)):
    Root = (1,)+TI
    for TR in range(0,N-1):
        if Root[TR+1] not in Node[Root[TR]]:
            Count -= 1
            break
print(Count)

Submission status: Accepted

Solution code:
def DFS(num):
    global ans,color
    color[num]="black"
    if "white" not in color[1:]:
        ans +=1
    for i in MAP[num]:
        if color[i]=="white":
            DFS(i)
    color[num]="white"


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

MAP=[[] for _ in range(n+1)]
for a,b in AB:
    MAP[a].append(b)
    MAP[b].append(a)

color=["white" for _ in range(n+1)]
ans=0
DFS(1)
print(ans)

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)]
MAP=[[] for _ in range(n)]
for a,b in AB:
    MAP[a-1].append(b-1)
    MAP[b-1].append(a-1)

ans=0
for A in permutations(range(n),n):
    if A[0]==0:
        for i in range(n):
            if i==n-1:
                ans +=1
                break
            if A[i+1] not in MAP[A[i]]:break
print(ans)

Submission status: Accepted

Solution code:
n,m=list(map(int,input().split()))
# 再帰の深さが1000を超えそうなときはこれをやっておく
import sys
sys.setrecursionlimit(10**7)

#隣接行列表現
es=[[0 for i in range(n)] for j in range(n)]
for i in range(m):
  a,b=list(map(int,input().split()))
  es[a-1][b-1]=1
  es[b-1][a-1]=1

  
#深さ優先探索

def dfs(v,visited):
  ans=0
  
  #自分が今いるところは探索済にする
  visited[v-1]=1
 
  #全部探索できたことになる
  if visited==check:
    visited[v-1]=0
    return 1
  
  #vから行けるところを考える
  for i in range(n):
    #道があって未訪問
    if visited[i]==0 and es[v-1][i]==1:
      ans=ans+dfs(i+1,visited)
  #次の探索のため未訪問にしておく
  visited[v-1]=0
   
  return ans





visited=[0 for i in range(n)]
check=[1 for i in range(n)]
print(dfs(1,visited))

Submission status: Accepted

Solution code:
n,m=map(int, input().split())
alist=[]
for i in range(m):
  a,b=map(int, input().split())
  alist.append([a,b])
  alist.append([b,a])
ans=0
import itertools
t=[i for i in range(1,n+1)]
blist=list(itertools.permutations(t,n))
ans=0
for i in blist:
  flag=True
  for j in range(n-1):
    if [i[j],i[j+1]] not in alist:
      flag=False
  if i[0]!=1:
      flag=False
  if flag:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int, input().split())
alist=[]
for i in range(m):
  a,b=map(int, input().split())
  alist.append([a,b])
  alist.append([b,a])
ans=0
import itertools
t=[i for i in range(1,n+1)]
blist=list(itertools.permutations(t,n))
ans=0
for i in blist:
  flag=True
  for j in range(n-1):
    if [i[j],i[j+1]] not in alist:
      flag=False
    if i[0]!=1:
      flag=False
  if flag:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
#制約が小さいので全探索する
n,m=list(map(int,input().split()))
#辺があるかどうかが知りたい→隣接行列表現
es=[[0]*n for i in range(n)]
for i in range(m):
  a,b=list(map(int,input().split()))
  es[a-1][b-1]=1
  es[b-1][a-1]=1

#順列を作る
from itertools import permutations
per=[i+1 for i in range(n-1)]
per=list(permutations(per,n-1))

#全探索する
ans=0
for i in per:
  cnt=0
  if es[0][i[0]]==0:
    continue
  else:
    for j in range(1,n-1):
      if es[i[j]][i[j-1]]==0:
        cnt+=1
    if cnt==0:
      ans=ans+1
print(ans)