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 multival(): return map(int,input().split())
def data(N=1): return [list(map(int,input().split())) for _ in range(N)]
mod = 10**9 + 7
inf = float("inf")

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

def dfs(now=0,visited=[False]*N):
    visited[now] = True
    if all(visited) is True:
        global ans
        ans += 1
    for ne in range(N):
        if nemat[now][ne] == 1 and visited[ne] is False:
            dfs(ne,visited[:])

dfs()
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

# construct indirected graph
edges = [[] for _ in range(n)]
for i, j in li:
    edges[i - 1].append(j - 1)
    edges[j - 1].append(i - 1)

ans = 0
S = deque()
S.append([0])
while len(S) > 0:
    path = S.pop()
    for v in edges[path[-1]]:
        if v not in path:
            if len(path) + 1 == n:
                ans += 1
            else:
                S.append(path + [v])


print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from itertools import permutations

class Graph:
    def __init__(self, n_nodes):
        self.adj = [set() for i in range(n_nodes)]

    def add_edge(self, a1, b1):
        self.adj[a1 - 1].add(b1)
        self.adj[b1 - 1].add(a1)

    def are_adj(self, a1, b1):
        return b1 in self.adj[a1 - 1]

def main():
    n, m = map(int, input().split())
    gr = Graph(n)
    for i in range(m):
        a, b = map(int, input().split())
        gr.add_edge(a, b)
    paths = all_permutations_from_one(n)
    cnt = 0
    for p in paths:
        if is_possible(p, gr):
            cnt += 1
    print(cnt)

def all_permutations_from_one(n):
    perms_2_n = list(permutations(range(2, n + 1)))
    perms_1_n = [(1,) + p2n for p2n in perms_2_n]
    return perms_1_n

def is_possible(path, gr):
    l = len(path)
    flag = True
    for i in range(l - 1):
        a, b = path[i:i + 2]
        if not gr.are_adj(a, b):
            flag = False
    return flag

main()

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
from collections import defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


n, m = LI()
graph = defaultdict(list)
for _ in range(m):
    a, b = LI_()
    graph[a].append(b)
    graph[b].append(a)


def DFS(v: int, visited: list) -> int:
    # print(visited, id(visited))
    ans = 0
    visited[v] = 1
    if all(visited):
        return 1

    for next in graph[v]:
        if visited[next]:
            continue

        ans += DFS(next, visited[:])

    return ans


print(DFS(0, [0] * n))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
N,M = map(int,input().split())
note = [[0]*N for i in range(N)]
visited = [False]*N
visited[0] = True
ans = 0
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    note[a][b] = 1
    note[b][a] = 1

def dfs(p=0, depth=0):
    if depth == N-1:
        global ans
        ans += 1
        return
    for i in range(N):
        if note[p][i] == 1 and visited[i] is False:
            visited[i] = True
            dfs(i,depth+1)
            visited[i] = False

dfs()
print(ans)

Submission status: Accepted

Solution code:
def bit_dp(N, Adj):
    dp = [[0]*N for i in range(1 << N)]
    #dp[{0},0] = 1

    dp[1][0] = 1

    for S in range(1 << N):
        for v in range(N):
            # v がSに含まれていないときはパス
            if (S & (1 << v)) == 0:
                continue

            #sub = S - {v}
            sub = S ^ (1 << v)

            for u in range(N):
                # sub に uが含まれていて、かつ uとvがへんで結ばれている
                if (sub & (1 << u)) and (Adj[u][v]):
                    dp[S][v] += dp[sub][u]
    ans = sum(dp[(1 << N) - 1][u] for u in range(1, N))
    return ans


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

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import permutations
N, M = list(map(int, input().split()))
edges = []

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

mat = [[0]*N for _ in range(N)]

for s, g in edges:
    mat[s][g] = 1
    mat[g][s] = 1


P = permutations(range(N))
ans = 0
for route in P:
    if route[0] != 0:
        continue
    else:
        vis = 0
        for s, g in zip(route, route[1:]):
            if mat[s][g] == 1:
                vis += 1
                if vis == N-1:
                    ans += 1
                continue
            else:
                break
print(ans)

Submission status: Accepted

Solution code:
def rs(X, Y, i):
  if i not in Y:
    return 0
  elif len(Y)==1:
    return 1
  Y.remove(i)
  
  total=0
  X_tmp=[x for x in X if i in x]
  for x in X_tmp:
    st=set(x)&set(Y)
    if st!=set():
      target=list(st)[0]
    else:
      continue
    total+=rs(X, Y[:], target)
    
  return total
  

N,M=map(int, input().split())
X=[list(map(int,input().split())) for _ in range(M)]
Y=[i+1 for i in range(N)]
print(rs(X, Y, 1))

Submission status: Accepted

Solution code:
def rs(X, Y, i):
  if i not in Y:
    return 0
  elif len(Y)==1:
    return 1
  Y.remove(i)
  
  total=0
  X_tmp=[x for x in X if x[0]==i or x[1]==i]
  for x in X_tmp:
    if x[0]==i and x[1] in Y:
      target=x[1]
    elif x[1]==i and x[0] in Y:
      target=x[0]
    else:
      continue
    total+=rs(X, Y[:], target)
    
  return total
  

N,M=map(int, input().split())
X=[list(map(int,input().split())) for _ in range(M)]
Y=[i+1 for i in range(N)]
print(rs(X, Y, 1))

Submission status: Accepted

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

ans = 0
node = 0
remain.remove(0)

def find_next_node(remain_arr, current_node):
    global ans
    if remain_arr == []:
        ans += 1
        return
    for next_node in connected[current_node]:
        if next_node in remain_arr:
            find_next_node([i for i in remain_arr if i != next_node], next_node)

find_next_node(remain, 0) 
print(ans)

Submission status: Accepted

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

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

def conn(v1,v2):
    return (v1,v2) in edges

import itertools
ret=0
for x in itertools.permutations(list(range(1,n+1))):
    for i in range(n-1):
        if not conn(x[i],x[i+1]) or x[0]!=1:
            break
        if i==n-2:
            ret+=1

print(ret)

Submission status: Accepted

Solution code:
# ABC 054
def getInt(): return int(input())
def getIntList(): return [int(x) for x in input().split()]
def zeros(n): return [0 for i in range(n)]
def zeros2(n, m): return [[0 for i in range(m)] for j in range(n)]

debug = True
def db(x): 
    if debug: print(x)

debug = False
N,m = getIntList()
org = zeros(m)

for i in range(m):    org[i] = getIntList()

db(('org graph',org))
Count = 0

def find(graph, fromNode, route): # -1: NG, >=OK、評価値
    global Count
    db(('find in',fromNode, route))
    if fromNode in route: return -1
    else:
        route = route + [fromNode]  # +=だとrouteを書き換えてしまう
        if len(route)==N: 
            db(('N',N))
            Count += 1
            return 0
        for edge in graph:
            if edge[0]==fromNode:  # graphのソート、一旦fromが見つかった後の中断
                val = find(graph, edge[1], route)
                #if val==0: 
                #    db(('found', route, edge[1]))
                #    return 0
        #db(('cannot',fromNode))
        return -1
    
graph = zeros(m*2)
for i in range(m):
    graph[i*2] = org[i]
    graph[i*2+1] = [org[i][1], org[i][0]]
graph.sort()
db(('new graph',graph))
route = []
find(graph, 1, route)
print(Count)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=[[]for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    s[a-1].append(b-1)
    s[b-1].append(a-1)
c=0
k=[]
p=[[0]]
for i in range(m):
    k=[]
    for j in range(len(p[:])):
        for h in range(len(s[p[j][-1]])):
            t=s[p[j][-1]]
            if not t[h] in p[j]:
                k.append(p[j]+[t[h]])
                if len(k[-1])==n:
                    c+=1
                    k.pop(-1)
    else:
        p=k[:]
print(c)

Submission status: Accepted

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

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


def f(curpath, N):
    if len(curpath) == N:
        # print(curpath)
        return 1
    ret = 0
    now = curpath[-1]

    for e in edges:
        if now == e[0] and e[1] not in curpath:
            temp = curpath[:]
            temp.append(e[1])
            ret += f(temp, N)
    return ret


print(f([1], N))

Submission status: Accepted

Solution code:
from itertools import permutations

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

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

arange = permutations(range(1,N))
ans = 0
for i in arange :
    pm = [0] + list(i)
    for a,b in zip(pm, pm[1:]) :
        if not Matrix[a][b] :
            break
    else :
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import  itertools
n,m = map(int,input().split())
matrix = [[0]*n for _ in range(n)]

for i in range(m):
 a,b = map(int,input().split())
 matrix[a-1][b-1] = 1
 matrix[b-1][a-1] = 1
#print(matrix)
cnt = 0

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

Submission status: Accepted

Solution code:
import itertools

N, M = map(int, input().split(" "))
path = [[False for j in range(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

count = 0
for order in itertools.permutations(range(1, N)):
    before = 0
    for nextNode in order:
        if not path[before][nextNode]:
            break
        before = nextNode
    if before == order[-1]:
        count += 1
print(count)

Submission status: Accepted

Solution code:
def dfs(i):
    if all(visited):
        global ans
        ans += 1
        return
    for j in range(N):
        if g[i][j] and not visited[j]:
            visited[j] = True
            dfs(j)
            visited[j] = False

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

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

Submission status: Accepted

Solution code:
def bit_dp(N, Adj):
    dp = [[0]*N for i in range(1 << N)]
    # dp({0], 0) = 1 と初期化する
    dp[1][0] = 1

    for S in range(1 << N):
        for v in range(N):
            # v が S に含まれていないときはパスする
            if (S & (1 << v)) == 0:
                continue

            # sub = S - {v}
            sub = S ^ (1 << v)

            for u in range(N):
                # sub に u が含まれており、かつ u と v が辺で結ばれている
                if (sub & (1 << u)) and (Adj[u][v]):
                    dp[S][v] += dp[sub][u]

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


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

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

    ans = bit_dp(N, Adj)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import permutations
N,M = map(int,input().split())
E = [[False for _ in range(N)] for _ in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    E[a-1][b-1] = True
    E[b-1][a-1] = True

P = permutations([i for i in range(1,N)])

ans = 0
for pp in P:
    l = len(pp)
    ni,mi = 0,0
    chk = True
    for p in pp:
        mi = p
        if not E[ni][mi]:
            chk = False
            break
        ni = p
    if chk:
        ans += 1

print(ans)

Submission status: Accepted

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

nodes = {}
for n in range(N):
    nodes[n] = []

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


def dfs(v):
    global reached
    global ans
    if False not in reached:
        ans += 1
        return
    for i in range(N):
        if i in nodes[v] and not reached[i]:
            reached[i] = True
            dfs(i)
            reached[i] = False
    return

ans = 0
for v in range(1):
    reached = [False for i in range(N)]
    reached[v] = True
    dfs(v)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

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

Matrix = [[False for i in range(N)] for j in range(N)]

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

for i in range(N) :
    Matrix[i][i] = True

arange = list(range(2,N+1))

ans = 0
for pm in permutations(arange) :
    pm = [1] + list(pm)
    for row,col in zip(pm,pm[1:]) :
        row -= 1
        col -= 1
        if not Matrix[row][col] :
            break
    else :
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

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

Matrix = [[False for i in range(N)] for j in range(N)]

for i in range(N) :
    Matrix[i][i] = True
for i in range(M) :
    row,col = map(int,input().split())
    row -= 1
    col -= 1
    Matrix[row][col] = True
    Matrix[col][row] = True

arange = range(2,N+1)

ans = 0
for pm in permutations(arange) :
    pm = [1] + list(pm)
    for row,col in zip(pm,pm[1:]) :
        row -= 1
        col -= 1
        if not Matrix[row][col] :
            break
    else :
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

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

L = [[False for i in range(N)] for j in range(N)]

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

arange = range(2,N+1)

res = 0
for P in permutations(arange) :
    P = [1] + list(P)
    for S,G in zip(P,P[1:]) :
        if not L[S-1][G-1] :
            break
    else :
        res += 1
print(res)

Submission status: Accepted

Solution code:
n,m=[int(i) for i in input().split()]
pp=[[0 for i in range(2)] for j in range(m)]
not_bridge=0

#深さ優先探索---------------------------------
#参照元：Python3でグラフの実装＆深さ優先探索・幅優先探索の実装
#http://muromura.hatenablog.com/entry/2017/07/16/025414
def dfs(Graph, Start, Vn, Visited=None):
  
##追加（空から読んでも動くように修正）-----------------------
  if Graph[Start]==[] and Visited==None: 
        Next=Start+1
        dfs(Graph, Next, Vn, Visited)  #再帰
  else:
##--------------------------------------------------------

    if (Visited==None): 
        Visited = [] #開始点のときに探索済みリストをつくる
        Visited.append(Start)  #現在の頂点を探索済みリストに加える

    
    if len(Visited)==Vn: #全点訪問済みの場合、橋ではない
        #print(Visited)
        global not_bridge
        if len(set(Visited)) == n:
            not_bridge=not_bridge+1
#        print(Visited)
        return 0
        
    for Next in Graph[Start]:  #次に探索する頂点の候補
        Visited.append(Next)
        #if ( Next in Visited ):  continue  #訪問済みリストにある頂点は飛ばす
        dfs(Graph, Next, Vn, Visited)  #再帰
        Visited.pop()
    return 0
  
#--------------------------------------------------------        

for i in range(m) :
    pp[i] =[int(i) for i in input().split()]
    
#隣接リスト
l = [[] for i in range(n+1)] #頂点の数+1
for pi in pp:  #0-originedに注意、l[0]は空
    l[pi[0]].append(pi[1])
    l[pi[1]].append(pi[0])

#print(l)
dfs(l, 0, n)
print(not_bridge)

Submission status: Accepted

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

ans=[]
li=[0 for i in range(n+1)]

def dfs(a,r):
    r[a]=1
    p=0
    q=0
    for i in range(m):
        if l[i][0]==a or l[i][1]==a:
            q+=1
            b=l[i][0]*l[i][1]//a
            if r[b]==0:
                dfs(b,r)
                r[b]=0
            else:
                p+=1
    if p==q and sum(r)==n:
        ans.append(1)

dfs(1,li)
print(sum(ans))

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import permutations

n,m = li()
graph = [[False]*n for _ in range(n)]

for _ in range(m):
    a,b = li_()
    graph[a][b] = True
    graph[b][a] = True
    
cands = list(permutations([i for i in range(1,n)]))

ans = 0

for c in cands:
    cand = [0] + list(c)
    ok = True
    for i in range(n-1):
        if not graph[cand[i+1]][cand[i]]:
            ok = False
    
    if ok:   
        ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd
from itertools import groupby as gb
from itertools import permutations as perm
from collections import Counter as C
from collections import defaultdict as dd
sys.setrecursionlimit(10**5)

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

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

# n-1頂点のperm
l = range(2,n+1)

res = 0
for p in perm(l):
    p = [1] + list(p)
    for s,g in zip(p,p[1:]):
        if not coor[s-1][g-1]:
            break
    else:
        res += 1
print(res)

Submission status: Accepted

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

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

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

def search(path):
    global cou
    n = path[len(path) - 1]
    if len(path) == N:
        cou += 1
    else:
        for x in nums[n]:
            if x not in path:
                path.append(x)
                search(path)
                path.pop()

search([0])
print(cou)

Submission status: Accepted

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

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

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

def search(path):
    global cou
    n = path[len(path) - 1]
    if len(path) == N:
        cou += 1
    else:
        for x in nums[n]:
            if x not in path:
                path.append(x)
                search(path)
                path.pop()

search([0])
print(cou)

Submission status: Accepted

Solution code:
import itertools
def course_judge(edge,arr):
    ok = True
    for i in range(1,len(arr)):
        go = arr[i-1]
        to = arr[i]
        if edge[go][to] == 0 or edge[to][go] == 0:
            ok = False
    return ok

N,M = map(int,input().split())
arr = [i for i in range(1,N+1)]
edge = [[0]*(N+1) for i in range(N+1)]
for i in range(M):
    go,to = map(int,input().split())
    edge[go][to] = 1
    edge[to][go] = 1
count = 0
for a in itertools.permutations(arr):
    if a[0] == 1 and course_judge(edge,a):
        count += 1
print(count)

Submission status: Accepted

Solution code:
import itertools

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

ans = 0
for ex in itertools.permutations(example):
    e = [0] + list(ex)
    for a, b in zip(e, e[1:]):
        if path[a][b] is False:
            break
    else:
        # print(e)
        ans += 1
print(ans)

Submission status: Accepted

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

for i in range(M):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)
queue = [(1,)]
ans = 0
while queue:
    q = queue.pop()

    if len(q) == N:
        ans+=1
        continue
    now = q[-1]

    for nextp in adj[now]:
        if not nextp in q:
            queue.append(q+(nextp,))
print(ans)

Submission status: Accepted

Solution code:
import itertools
N,M=map(int,input().split())
edge=[]
for i in range(N+1):
  edge.append([0]*(N+1))
for j in range(M):
  a,b=map(int,input().split())
  edge[a][b]=1
  edge[b][a]=1
roots=list(itertools.permutations(range(2,N+1)))
ans=0
for root in roots:
  pos=1
  for i in range(N-1):
    nxt=root[i]
    if edge[pos][nxt]==1:
      pos=nxt
    else:
      break
  else:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
import itertools
N,M=map(int,input().split())
L=[]
c=[i for i in range(1,N+1)]
for _ in range(M):
    x,y = map(int,input().split())
    l1 = [x,y]
    l2 = [y,x]
    L.append(l1)
    L.append(l2)
c = [list(x) for x in itertools.permutations(c)]
count = 0
ans = 0
for x in c:
    if x[0] > 1:
        break
#    print(x)
    for i in range(N-1):
        if [x[i],x[i+1]] in L:
            count += 1
 #           print(x[i],x[i+1])
            if count == N - 1:
                ans += 1
                count = 0
        else:
            count = 0
            break

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

N,M=map(int,input().split())
L=[]
for i in range(N-1):
    L.append(1+i)
A=[]
a=[]
for i in range(N):
    for j in range(N):
        a.append(10)
    A.append(a)
    a=[]
    
#print(A)

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

#print(A)
cnt=0
for i in permutations(L,len(L)):
    S=0
    for j in range(len(i)-1):
        if A[i[j]][i[j+1]]==10:
            break
        else:
            S+=1
    if S==len(L)-1:
        if A[0][i[0]]==1:
            cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
edge = [[0] * N for i in range(N)] # 辺を行列で表す
for i in range(M):
    a, b = list(map(int, input().split()))
    edge[a-1][b-1] = 1
    edge[b-1][a-1] = 1

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 edge[v][i] == 0: # 繋がってない
            continue
        if visited[i]: # 訪問済み
            continue

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

    return ret

# 訪問したかどうかのフラグ（最初はFalse）
visited = [False] * N

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

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
d = {}
for i in range(m):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    if a not in d:
        d[a] = [b]
    else:
        d[a].append(b)
    if b not in d:
        d[b] = [a]
    else:
        d[b].append(a)

ans = 0

def DFS(now, visited):
    global ans
    if len(visited) == n:
        ans += 1
        return
    for i in d[now]:
        if i not in visited:
            DFS(i, visited + [i])

DFS(0, [0])
print(ans)

Submission status: Accepted

Solution code:
import copy
s=list()

N,M=map(int,raw_input().split())
n=[[0 for i in range(N)] for j in range(N)]
for i in range(M):
        a,b=map(int,raw_input().split())
        n[a-1][b-1]=1
        n[b-1][a-1]=1
arrived=[0 for i in range(N)]

arrived[0]=1
def solve(s,arrived):
        narrived=copy.deepcopy(arrived)
        global n
        global N
        op=False
        ans=0
        for i in range(N):
                arrived=copy.deepcopy(narrived)
                if(s[i]==1 and arrived[i]!=1):
                        op=True
                        arrived[i]=1
                        ans+=solve(n[i],arrived)
        
        if(sum(arrived)==N and op==False):
                return 1
        elif(op==False):
                return 0
        return ans
                        
print(solve(n[0],arrived))

Submission status: Accepted

Solution code:
import itertools
n, m = map(int, input().split())
c = []
for i in range(m):#h:高さ
    c.append([int(m) for m in input().split()])
c.sort()
d = []
for i in range(n):
    d.append([])
for i in range(m):
    for k in range(n):
        if c[i][0] == k + 1:
            d[k].append(c[i][1])
        if c[i][1] == k + 1:
            d[k].append(c[i][0])
nli = [i + 1 for i in range(1, n)]
ans = 0
for path in itertools.permutations(nli, n - 1):
    for i in range(len(path) - 1):
        if i == 0:
            if path[i] in d[0]:
                if path[i + 1] in d[path[i] - 1]:
                    pass
                    if i == len(path) - 2:
                        ans += 1
                else:
                    break
            else:
                break
        else:
            if path[i + 1] in d[path[i] - 1]:
                pass
                if i == len(path) - 2:
                    ans += 1
            else:
                break
if n == 2:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
def dfs(v, n, visited, graph):
    all_visited = True

    for i in range(n):
        if not visited[i]:
            all_visited = False

    if all_visited:
        return 1

    ret = 0

    for i in range(n):
        if not graph[v][i]:
            continue
        if visited[i]:
            continue
        visited[i] = True
        ret += dfs(i, n, visited, graph)
        visited[i] = False
    return ret


n, m = map(int, input().split())
graph = [[False for _ in range(n)] for _ 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 for _ in range(n)]
visited[0] = True
print(dfs(0, n, visited, graph))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
edges = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    edges[a] += [b]
    edges[b] += [a]
candy = [[1]]
for _ in range(N - 1):
    tmp = []
    for c in candy:
        for next in edges[c[-1]]:
            tmp += [c + [next]]
    candy = tmp
print(sum(len(set(c)) == N for c in candy))

Submission status: Accepted

Solution code:
from itertools import permutations

N, M = map(int, input().split())
edges = set()
for _ in range(M):
    a, b = map(int, input().split())
    edges.add((a, b))
    edges.add((b, a))

cnt = 0
for p in permutations(range(2, N + 1)):
    cnt += all(move in edges for move in zip((1,) + p, p))
print(cnt)

Submission status: Accepted

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

g = [[0 for _ in range(n)] for _ in range(n)]

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

#print(g)

ans = 0
visited = [0 for _ in range(n)]

def dfs(v):
    visited[v] = 1
    if all(x == 1 for x in visited):
        global ans
        ans += 1
        return

    for i in range(n):
        if g[v][i] == 1 and visited[i] == 0:
            visited[i] = 1
            dfs(i)
            visited[i] = 0

    return

dfs(0)
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
edge = [[False for j in range(n)] for i in range(n)]
for _ in range(m):
	a, b = map(int, input().split())
	edge[a-1][b-1] = edge[b-1][a-1] = True
visited = [False for _ in range(n)]
ans = 0
def dfs(v):
	visited[v] = True
	if all(x==True for x in visited):
		global ans
		ans += 1
		return
	for i in range(0, n):
		if edge[v][i]==True and visited[i]==False:
			dfs(i)
			visited[i] = False
dfs(0)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

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

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

for order in list(permutations(range(N))):
    if order[0] != 0:
        break
        
    check = 1
    for i in range(N-1):
        check *= matrix[order[i]][order[i+1]]
    ans += check
    
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations as perm
n,m = map(int,input().split())
coor = [[False]*n for _ in range(n)]
for i in range(m):
	a,b = map(int,input().split())
	a,b = a-1,b-1
	coor[a][b] = True
	coor[b][a] = True
ll = list(range(n))
res = 0
for l in perm(ll):
	if l[0]!=0:
		continue
	for (i,j) in zip(l,l[1:]):
		if not coor[i][j]:
			break
	else:
		res += 1
print(res)