Problem:


Score : 300 points

Problem Statement

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

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

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

Here, the endpoints of a path are considered visited.  

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

Figure 1: an example of an undirected graph

The following path shown in Figure 2 satisfies the condition.

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

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

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

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

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

Constraints

2≦N≦8 

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

1≦a_i<b_i≦N 

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

Input

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

N M  
a_1 b_1  
a_2 b_2
:  
a_M b_M  

Output

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

Sample Input 1

3 3
1 2
1 3
2 3

Sample Output 1

2

The given graph is shown in the following figure:

The following two paths satisfy the condition:

Sample Input 2

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

Sample Output 2

1

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



Sample input:
3 3
1 2
1 3
2 3


Sample output:
2

Submission status: Accepted

Solution code:
def dfs(now,flags):
    global graph
 
    if len(flags) == len(graph)-1:
        return 1

    flags.add(now)
    ans = 0
    for vis in graph[now]:
        if not vis in flags:
            #print(vis,flags)
            ans += dfs(vis,flags)
    flags.remove(now)
    return ans



ans = 0
nums = [int(x) for x in input().split()]
N, M = nums[0], nums[1]
graph = {i:[] for i in range(1,N+1)}

for i in range(M):
    nums = [int(x) for x in input().split()]
    graph[nums[0]].append(nums[1])
    graph[nums[1]].append(nums[0])

print(dfs(1,set()))

Submission status: Accepted

Solution code:
def count_path(graph, node, visited):
    if node in visited: return 0
    if len(visited)==len(graph)-1: return 1
    visited.add(node)
    res=0
    for i in range(len(graph)):
        if graph[node][i]:
            res+=count_path(graph, i, visited)
    visited.remove(node)
    return res

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

    res=count_path(graph, 0, set())
    print(res)

if __name__=="__main__":
    main()

Submission status: Accepted

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

E = [[] for _ in range(N)]
visited = [False]*N
visited_all = [True]*N

def DFS(V):
    if visited == visited_all:
        return 1
    count = 0
    for e in E[V]:
        if not visited[e]:
            visited[e] = True
            count += DFS(e) 
            visited[e] = False
    else:
        return count

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

visited[0] = True
print(DFS(0))

Submission status: Accepted

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

line = input().split(" ")
n = int(line[0])
m = int(line[1])
edge = [[] for _ in range(n+1)]

for _ in range(m):
    line = input().split(" ")
    a = int(line[0])
    b = int(line[1])

    edge[a].append(b)
    edge[b].append(a)


visited = [False for _ in range(n+1)]
visited[0] = True#dummy
visited[1] = True

def solve(x):
    allVisited = True
    for e in visited:
        allVisited = allVisited and e
    if allVisited:
        return 1

    ret = 0
    for e in edge[x]:
        if not visited[e]:
            visited[e] = True
            ret += solve(e)
            visited[e] = False
    return ret


print(solve(1))

Submission status: Accepted

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

for i in range(M):
    f,g = map(int,input().split())
    dic[f].append(g)
    dic[g].append(f)


stack = [[1,1,[1]]]
root = 0
while len(stack) >0:
    now = stack[-1][0]
    length = stack[-1][1]
    visited = stack[-1][2]
    del stack[-1]
    for next in dic[now]:
        if next not in visited:
            temp = visited.copy()
            if length +1 <=N-1:
                temp.append(next)
                stack.append([next,length+1,temp])
            elif length +1 == N:
                root += 1


print(root)

Submission status: Accepted

Solution code:
import itertools
N,M=map(int,input().split())
m=[[0 for i in range(N)] for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    m[a-1][b-1]+=1
    m[b-1][a-1]+=1
S=list(itertools.permutations(range(1,N),N-1))
#print(S)
T=0
for sg in S:
    root=[0]
    for i in sg:
        root.append(i)
    flag=0
    for i in range(N-1):
        if m[root[i+1]][root[i]]==0:
            flag=1
            break
    if flag==0:
        T+=1
print(T)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
E = [[] for _ in range(N)]
dp = {}

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

S = 1
G = (1 << N) - 1


def is_visited(v: int, path: int):
    return path & (1 << v)


def visit(v: int, path: int):
    return path ^ (1 << v)


def count(u: int, path: int):
    if path == G:
        return 1

    k = (u, path)
    if k in dp:
        return dp[k]

    s = sum(
        count(v, visit(v, path))
        for v in E[u]
        if not is_visited(v, path)
    )
    dp[k] = s
    return s


print(count(0, S))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
E = [[] for _ in range(N)]
dp = {}

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

S = 1
G = (1 << N) - 1


def is_visited(v: int, path: int):
    return path & (1 << v)


def visit(v: int, path: int):
    return path ^ (1 << v)


def count(u: int, path: int):
    if path == G:
        return 1

    if (u, path) in dp:
        return dp[(u, path)]

    return sum(
        count(v, visit(v, path))
        for v in E[u]
        if not is_visited(v, path)
    )


print(count(0, S))

Submission status: Accepted

Solution code:
from functools import lru_cache


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

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

S = 1
G = (1 << N) - 1


@lru_cache(2**N*N)
def is_visited(v, path):
    return path & (1 << v)


@lru_cache(2**N*N)
def count(u, path):
    if path == G:
        return 1

    return sum(
        count(v, path ^ (1 << v))
        for v in E[u]
        if not is_visited(v, path)
    )


print(count(0, S))

Submission status: Accepted

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

q = [(0, [0])]
c = 0
while q:
    x, p = q.pop()

    if len(p) == N:
        c += 1

    for v in E[x]:
        if v in p:
            continue
        q.append((v, p + [v]))

print(c)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import permutations
N, M = [int(i) for i in input().split()]

dd = defaultdict(list)
ans = 0
for _ in range(M):
    po = [int(i) for i in input().split()]
    dd[po[0]].append(po[1])
    dd[po[1]].append(po[0])
for route in permutations(range(1,N+1)):
    can = True
    if route[0] != 1:
        continue
    for i in range(N-1):
        if route[i+1] not in dd[route[i]]:
            can = False
            break
    if can:
        ans += 1

print(ans)

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:

from itertools import permutations

n,m=map(int,input().split())
ans=0
s=[list(map(int,input().split())) for i in range(m)]

t=list(permutations(list(range(1,n+1))))
for i in range(len(t)):
    flag=True
    if t[i][0]!=1: continue
    for j in range(n-1):
        a=sorted([t[i][j],t[i][j+1]])
        if a not in s: flag=False
    if flag: ans+=1
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

d=[int(x)+1 for x in range(N-1)]
ans=0
for exam in itertools.permutations(d):
  cnt=list(exam)
  cnt.insert(0,0)
  flg=True
  for i in range(N-1):
    if not(cnt[i+1] in C[cnt[i]]):
      flg=False
      break
  if flg:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m = (int(i) for i in input().split())
a = [[int(i) for i in input().split()] for i in range(m)]
b,c,answer = [],[],0
for i in range(2,n+1):
	c.append(i)
for i in range(n):
	x = []
	for j in a:
		if j[0]==i+1:
			x.append(j[1])
		elif j[1]==i+1:
			x.append(j[0])
	b.append(x)
for i in list(itertools.permutations(c,n-1)):
	if i[0] in b[0] and all(i[j+1] in b[i[j]-1] for j in range(n-2)):
		answer += 1
print(answer)

Submission status: Accepted

Solution code:
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=[0]*n#どこを通ったか記憶
visited[0]=1#１は最初に通る
def dfs(position,visited,n):#深さ優先探索
    all_visited=1
    for i in range(n):
        if visited[i]==0:
            all_visited=0#行ったことがない点があれば０
            break#どこかで見つかったらループ終了
    if all_visited==1:
        return 1#全部回れたら１回カウント
    count=0#経路の個数をカウント
    for next in range(n):#次に移動する点
        if path[position][next]==0:
            continue#道がなければ次へ
        if visited[next]==1:
            continue#行ったことがあれば次へ
        visited[next]=1
        count+=dfs(next,visited,n)
        visited[next]=0#行った記録を消去して前のループに戻る
    visited[position]=0

    return count
print(dfs(0,visited,n))

Submission status: Accepted

Solution code:
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=[0]*n#どこを通ったか記憶
visited[0]=1#１は最初に通る
def dfs(position,visited,n):#深さ優先探索
    all_visited=1
    for i in range(n):
        if visited[i]==0:
            all_visited=0#行ったことがない点があれば０
            break#どこかで見つかったらループ終了
    if all_visited==1:
        return 1#全部回れたら１回カウント
    count=0#経路の個数をカウント
    for next in range(n):#次に移動する点
        if path[position][next]==0:
            continue#道がなければ次へ
        if visited[next]==1:
            continue#行ったことがあれば次へ
        visited[next]=1
        count+=dfs(next,visited,n)
        visited[i]=0#行った記録を消去して前のループに戻る
    visited[position]=0

    return count
print(dfs(0,visited,n))

Submission status: Accepted

Solution code:
def dfs(v,n,visited):
    all_visted=1
    for i in range(n):
        if visited[i]==0:
            all_visted=0
    if all_visted==1:
        return 1
    count=0
    for i in range(n):
        if path[v][i]==0 or visited[i]==1:
            continue
        visited[i]=1
        count+=dfs(i,n,visited)
        visited[i]=0
    return count
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=[0]*n
visited[0]=1#点1は訪問済み
print(dfs(0,n,visited))

Submission status: Accepted

Solution code:
def dfs(v,n,visited):
    all_visted=1#全ての点を探索したか判別する
    for i in range(n):
        if visited[i]==0:#まだi番目の点を訪問していない時
            all_visted=0
    if all_visted==1:#全ての辺を訪問した場合
        return 1
    count=0#全ての辺を訪問する回数を格納する変数
    for i in range(n):
        if path[v][i]==0:#辺がないとき、つまり隣接していない時
            continue
        if visited[i]==1:#既に訪問している
            continue
        visited[i]=1#訪問する
        count+=dfs(i,n,visited)#countに+1をする
        visited[i]=0#まだ探索していないノードまで戻る
    return count
#グラフの位置情報を読み取る
n,m=map(int,input().split())
path=[[0]*n for i in range(n)]#0は未訪問,1は訪問済み
for i in range(m):
    a,b=map(int,input().split())
    path[a-1][b-1]=1#隣接しているところは1になる
    path[b-1][a-1]=1
visited=[0]*n
visited[0]=1#点1は既に訪問済みなので記録
print(dfs(0,n,visited))

Submission status: Accepted

Solution code:
def dfs(v,n,visited):
    all_visted=1
    for i in range(n):
        if visited[i]==0:
            all_visted=0
    if all_visted==1:
        return 1
    count=0#全ての辺を訪問する回数を格納する変数
    for i in range(n):
        if path[v][i]==0:#辺がないとき、つまり隣接していない時
            continue
        if visited[i]==1:#既に訪問している
            continue
        visited[i]=1#訪問する
        count+=dfs(i,n,visited)
        visited[i]=0
    return count
#グラフの位置情報を読み取る
n,m=map(int,input().split())
path=[[0]*n for i in range(n)]#0は未訪問,1は訪問済み
for i in range(m):
    a,b=map(int,input().split())
    path[a-1][b-1]=1#隣接しているところは1になる
    path[b-1][a-1]=1
visited=[0]*n
visited[0]=1#点1は既に訪問済みなので記録
print(dfs(0,n,visited))

Submission status: Accepted

Solution code:
n,m=[int(i) for i in input().split()]
es=set()
for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    es|={(u,v),(v,u)}


p=[[0]]
x=0
while p:  
  p1=p.pop()
  if len(p1)==n:
    x+=1
  else:
    for l0,l1 in es:
      if l0==p1[len(p1)-1] and l1 not in p1:
          p.append(p1+[l1])

print(x)

Submission status: Accepted

Solution code:
def dfs(v,n,visited):
    all_visted=1
    for i in range(n):
        if visited[i]==0:
            all_visted=0
    if all_visted==1:
        return 1
    ret=0
    for i in range(n):
        if path[v][i]==0:
            continue
        if visited[i]==1:
            continue
        visited[i]=1
        ret+=dfs(i,n,visited)
        visited[i]=0
    return ret
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=[0]*n
visited[0]=1
print(dfs(0,n,visited))

Submission status: Accepted

Solution code:
def dfs(v,n,visited):
    all_visted=True
    for i in range(n):
        if visited[i]==False:
            all_visted=False
    if all_visted==True:
        return 1
    ret=0
    for i in range(n):
        if path[v][i]==False:
            continue
        if visited[i]==True:
            continue
        visited[i]=True
        ret+=dfs(i,n,visited)
        visited[i]=False
    return ret
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())
    path[a-1][b-1]=True
    path[b-1][a-1]=True
visited=[False]*n
visited[0]=True
print(dfs(0,n,visited))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
if m==0:
    print(0)
    exit()
ans=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    ans[a-1].append((b-1))
    ans[b-1].append((a-1))
v=[]#全ての点を訪問済み
def dfs(now,visited=[]):
    
    if len(visited)==n:
        v.append([visited])
        return
    for j in ans[now]:
        if j not in visited:
            dfs(j,visited+[j])
dfs(0,[0])
print(len(v))

Submission status: Accepted

Solution code:
def dfs(t):
    if 0 not in already:#全ての辺を訪問していた場合
        return 1
    allReach=0#全ての辺を訪問する回数を格納する変数
    for i in range(n):
        if connect[t][i]==1 and already[i]==0:#辺があり、訪問しいない場合
            already[i]=1
            allReach+=dfs(i)
            already[i]=0
    return allReach

n,m=map(int,input().split())
connect=[[0 for i in range(n)]for j in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    #辺の情報を記録する
    connect[a-1][b-1]=1
    connect[b-1][a-1]=1
already=[0 for i in range(n)]#訪問した点を記録する
already[0]=1#必ず1から始まるので訪問履歴をつけておく
print(dfs(0))#記録した情報をもとに0からdfs

Submission status: Accepted

Solution code:
def dfs(t):
    if 0 not in already:#全ての辺を訪問していた場合
        return 1
    allReach=0
    for i in range(n):
        if connect[t][i]==1 and already[i]==0:#辺があり、訪問しいない場合
            already[i]=1
            allReach+=dfs(i)
            already[i]=0
    return allReach

n,m=map(int,input().split())
connect=[[0 for i in range(n)]for j in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    #辺の情報を記録する
    connect[a-1][b-1]=1
    connect[b-1][a-1]=1
already=[0 for i in range(n)]#訪問した点を記録する
already[0]=1#必ず1から始まるので訪問履歴をつけておく
print(dfs(0))#記録した情報をもとに0からdfs

Submission status: Accepted

Solution code:
def dfs(t):
    if 0 not in already:
        return 1
    allReach=0
    for i in range(n):
        if connect[t][i]==1 and already[i]==0:
            already[i]=1
            allReach+=dfs(i)
            already[i]=0
    return allReach

n,m=map(int,input().split())
connect=[[0 for i in range(n)]for j in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    connect[a-1][b-1]=1
    connect[b-1][a-1]=1
already=[0 for i in range(n)]
already[0]=1
print(dfs(0))

Submission status: Accepted

Solution code:
nmax = 8
def dfs(v, N, visited):
    all_visited=True
    for i in range(N):
        if visited[i]==False:
            all_visited=False

    if all_visited==True:
        return 1

    ret=0
    for i in range(N):
        if graph[v][i]==False:
            continue
        if visited[i]==True:
            continue

        visited[i]=True
        ret+=dfs(i,N,visited)
        visited[i]=False

    return ret

N, M = map(int, input().split())
graph = [[False]*N for i in range(N)]
for i in range(M):
    A, B = map(int, input().split())
    graph[A-1][B-1]=True
    graph[B-1][A-1]=True

visited = [False]*N

visited[0]=True
print(dfs(0,N,visited))

Submission status: Accepted

Solution code:
def dfs(t):
    # 全ての辺を訪問していた場合
    if (0 not in already): return 1
    # 全ての辺を訪問する回数を格納する変数
    allReach=0
    for i in range(N):
        # 辺があり、訪問していない場合
        if connect[t][i]==1 and already[i]==0:
            already[i]=1
            allReach+=dfs(i)
            already[i]=0
    return allReach


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

connect=[[0for i in range(N)]for j in range(N)]
for i in range(M):
    a,b=map(int, input().split())
    # 辺の情報を記録する
    connect[a-1][b-1]=1
    connect[b-1][a-1]=1

# 訪問した頂点を記録する
already=[0 for i in range(N)]
# 必ず1から始まるので訪問履歴をつけておく
already[0]=1
# 記録した情報をもとに0からdfs
print(dfs(0))

Submission status: Accepted

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

n,m=map(int,input().split())
g=[[0 for i in range(8)]for i in range(8)]
for i in range(m):
    a,b=map(int,input().split())
    g[a-1][b-1]=1
    g[b-1][a-1]=1
check(0,[0,0,0,0,0,0,0,0][:],n)
print(count)

Submission status: Accepted

Solution code:
def dfs(v):
  if(0 not in already):return(1)
  allReach=0
  for i in range(n):
    if(connect[v][i]==1 and already[i]==0):
      already[i]=1
      allReach+=dfs(i)
      already[i]=0
  return(allReach)

n,m=map(int,input().split())
connect=[[0for i in range(n)]for j in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  connect[a-1][b-1]=1
  connect[b-1][a-1]=1
  
already=[0for i in range(n)]
already[0]=1
print(dfs(0))

Submission status: Accepted

Solution code:
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] = graph[b-1][a-1] = 1


visited = [True] + [False]*(n-1)
ans = 0


def dfs(x):
    global ans
    global visited
    
    if all(visited):
        ans += 1
        return
    
        
    for j in [j for j,v2 in enumerate(graph[x]) if v2 == 1 and not visited[j]]:
        visited[j] = True
        dfs(j)
        visited[j] = False

dfs(0)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
n,m = map(int,input().split())
edge = [[0]*n for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a-=1; b-=1
    edge[a][b] = edge[b][a] = 1
ret = 0
for i in permutations(range(n)):
    if i[0] != 0 : break
    for j in range(n-1):
        if edge[i[j]][i[j+1]] == 0: break
    else:
        ret += 1
print(ret)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
if m==0:
    print(0)
    exit()
ans=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    ans[a-1].append((b-1))
    ans[b-1].append((a-1))
v=[]#全ての点を訪問済み
def dfs(now,visited=[]):
    global v
    if len(visited)==n:
        v.append([visited])
        return
    for j in ans[now]:
        if j not in visited:
            dfs(j,visited+[j])
dfs(0,[0])
print(len(v))

Submission status: Accepted

Solution code:
import numpy as np
n,m=map(int,input().split())
if m==0:
    print(0)
    exit()
ans=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    ans[a-1].append((b-1))
    ans[b-1].append((a-1))
v=[]
def dfs(now,visited=[]):
    global v
    if len(visited)==n:
        v.append([visited])
        return
    for j in ans[now]:
        if j not in visited:
            dfs(j,visited+[j])
dfs(0,[0])
print(len(v))

Submission status: Accepted

Solution code:
def dfs(ver, p):
    global visited, ans
    if p == N:
        ans += 1
        return
    for i in range(N):
        if graph[ver][i] == 1 and visited[i] != 1:
            visited[i] = 1
            dfs(i, p+1)
            visited[i] = 0

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

graph = [[0] * N for _ 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

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

dfs(0, 1)

print(ans)

Submission status: Accepted

Solution code:
def do_dp(N, Adj):
    univ = 2 ** N - 1
    dp = [[0] * N for i in range(univ + 1)]
    dp[1][0] = 1

    for S in range(2, univ + 1):
        for v in range(N):
            S2 = S & (univ ^ (1 << v))
            for u in range(N):
                if ((1 << u) & S2) and Adj[u][v]:
                    dp[S][v] += dp[S2][u]
    
    ans = sum(dp[univ][u] for u in range(1, N))

    return ans

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

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

    ans = do_dp(N, Adj)
    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import numpy as np
n, m = map(int, input().split())
if m == 0:
    print(0)
    exit()
r = [[] for i in range(n)]
for i in range(m):
    f, s = map(int, input().split())
    r[f-1].append(s - 1)
    r[s-1].append(f - 1)
ans = []
def dfs(now, visited = []):
    global ans
    if len(visited) == n:
        ans.append([visited])
        return
    for j in r[now]:
        if j not in visited:
            dfs(j, visited + [j])
dfs(0, [0])
print(len(ans))

Submission status: Accepted

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

def dfs(v):
    if vis==[1]*n:
        return 1
    count=0
    for i in edges[v]:
        if vis[i]==0:
            vis[i]=1
            count+=dfs(i)
            vis[i]=0
    else:
        return count
print(dfs(0))

Submission status: Accepted

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

def dfs(v):
    if vis==[1]*n:
        return 1
    count=0
    for i in edges[v]:
        if vis[i]==0:
            vis[i]=1
            count+=dfs(i)
            vis[i]=0
    else: return count
print(dfs(0))

Submission status: Accepted

Solution code:
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)
count=0
for i in itertools.permutations(range(2,n+1)):
    if i[0] not in e[1]:
        continue
    f=True
    for j in range(n-2):
        if i[j+1] not in e[i[j]]:
            f=False
            break
    if f:
        count+=1
print(count)

Submission status: Accepted

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

# path候補を全列挙
route = [i for i in range(2, N+1)]
routes = list(permutations(route))
ans = 0

for route in routes:
    now = 1
    for r in route:
        if ([now, r] not in AB) and ([r, now] not in AB):
            now = r
            break
        now = r
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def c_One_stroke_Path(N, M, E):
    import itertools
    edge = [[] for j in range(N + 1)]
    for a, b in E:
        edge[a].append(b)
        edge[b].append(a)

    ans = 0
    route = itertools.permutations(range(2, N + 1), N - 1)
    for r in route:
        if not r[0] in edge[1]:
            # 頂点1からrが示す次の行き先に行くことができない
            continue
        count = 0
        for i in range(len(r)):
            if count == len(r) - 1:
                # すべての頂点を回れた
                ans += 1
                break
            if not r[i + 1] in edge[r[i]]:
                # 次の行き先に行くことができなかった
                break
            count += 1

    return ans

N,M = [int(i) for i in input().split()]
E = [[int(i) for i in input().split()] for j in range(M)]
print(c_One_stroke_Path(N, M, E))

Submission status: Accepted

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

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

went=[False for i in range(N)]

def dfs(now):
	if went.count(False)==0:
		return 1
	ans=0
	for _next in edge[now]:
		if not went[_next]:
			went[_next]=True
			ans+=dfs(_next)
			went[_next]=False
	return ans
went[0]=True

print(dfs(0))

Submission status: Accepted

Solution code:
def main():
    """
    N<=8, M<=N(N-1)/2
    →全探索?
    """
    N, M = map(int, input().split())

    # 無向グラフ
    g = [
        [False] * N
        for _ in range(N)
    ]
    for _ in range(M):
        a, b = map(int, input().split())
        g[a - 1][b - 1] = True
        g[b - 1][a - 1] = True

    # 訪問状態
    visited = [False for _ in range(N)]
    visited[0] = True

    def dfs(v, N, visited):
        if all(visited):
            return 1

        ret = 0
        for i in range(N):
            # 経路存在と訪問済み確認
            if not g[v][i] or visited[i]:
                continue

            # 再帰後に元に戻す
            visited[i] = True
            ret += dfs(i, N, visited)
            visited[i] = False

        return ret

    ans = dfs(0, N, visited)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
import collections
N,M=map(int,raw_input().split())
#print N,M
a=[map(int,raw_input().split()) for i in range(M)]
#print a
b=list(itertools.permutations(range(1,N+1)))
#print b

ans=0
for i in b:
	if i[0]!=1:
		continue
	c=[]
	for j in i:
		#print i,j
		if len(c)<2:
			c.append(j)

		if len(c)==2:
			if c in a or c[::-1] in a:
				cnt=1
			else:
				cnt=0
				break
			c.pop(0)
	ans+=cnt
print ans

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
edges=[[] for _ in range(N)]
for i in range(M):
  a,b=map(int,input().split())
  edges[a-1]+=[b-1]
  edges[b-1]+=[a-1]
vis=[1]+[0]*(N-1)#訪問フラグ

def DFS(v):
  if vis==[1]*N: 
    return 1
  ret=0
  for u in edges[v]:
    if vis[u]==0:
      vis[u]=1
      ret+=DFS(u)
      vis[u]=0
  else: return ret
print(DFS(0))

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
edges=[[] for _ in range(N)]
for i in range(M):
  a,b=map(int,input().split())
  edges[a-1]+=[b-1]
  edges[b-1]+=[a-1]
vis=[1]+[0]*(N-1)#訪問フラグ

ans=0
def DFS(v):
  global ans
  if vis==[1]*N: 
    ans+=1
    return 0
  for u in edges[v]:
    if vis[u]==0:
      vis[u]=1
      DFS(u)
      vis[u]=0
  else: return 0
DFS(0)
print(ans)

Submission status: Accepted

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

ret = 0
for path in itertools.permutations(range(2, N + 1)):
    if path[0] not in E[1]:
        continue
    f = True

    for i in range(N - 2):
        if path[i + 1] not in E[path[i]]:
            f = False
            break
    if f:
        ret += 1

print(ret)

Submission status: Accepted

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

for i in range(M):
    a,b = read_int_list()
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
    
def dfs(v):
    if len(v) == N:return 1
    ans=0
    for u in set(g[v[-1]]) - set(v):
        ans += dfs(v + [u])
    return ans
print(dfs([0]))

Submission status: Accepted

Solution code:
#bid DP
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)

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

def dfs(v, used):
    if used == All_used:
        return 1
    
    key = (v, used)
    if key in memo:
        return memo[key]
    
    ans = 0
    for u in g[v]:
        if (used >> u) & 1 == 1:
            continue
        
        used ^= (1 << u)
        ans += dfs(u, used)
        used ^= (1 << u)
        
    memo[key] = ans
    return ans

print(dfs(0, 1))

Submission status: Accepted

Solution code:
import itertools

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

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

cnt = 0

for each in itertools.permutations(range(N)):
    if each[0] != 0:
        break
    factor = 1
    for i in range(N-1):
        factor *= adj_matrix[each[i]][each[i+1]]
    cnt += factor

print(cnt)

Submission status: Accepted

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


def solve(before, visited, now):
    visited.append(now)
    if len(visited) is N:
        return 1
    pattern = 0
    for way in road[now]:
        if way is now:
            continue
        if way in visited:
            continue
        pattern += solve(now, visited[:], way)
    return pattern


print(solve(0, [], 1))