Problem:


Score : 300 points

Problem Statement

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

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

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

Here, the endpoints of a path are considered visited.  

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

Figure 1: an example of an undirected graph

The following path shown in Figure 2 satisfies the condition.

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

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

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

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

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

Constraints

2≦N≦8 

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

1≦a_i<b_i≦N 

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

Input

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

N M  
a_1 b_1  
a_2 b_2
:  
a_M b_M  

Output

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

Sample Input 1

3 3
1 2
1 3
2 3

Sample Output 1

2

The given graph is shown in the following figure:

The following two paths satisfy the condition:

Sample Input 2

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

Sample Output 2

1

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



Sample input:
3 3
1 2
1 3
2 3


Sample output:
2

Submission status: Accepted

Solution code:
import copy
class Node:
    def __init__(self):
        self.adjacentnode=[]

def search(lista,nodet):
    global count
    global n
    if len(lista)==n:
            count+=1
            return True
    for a in nodet[lista[-1]].adjacentnode:
        if a not in lista:
                newlist=copy.copy(lista)
                newlist.append(a)
                search(newlist,nodet)

n,m=map(int,input().split()) #n is node,m is edge 
count=0
listsrch=[0]
nodelist=[Node() for a in range(n)]
for t in range(m):
    a,b=map(int,input().split())
    nodelist[a-1].adjacentnode.append(b-1)
    nodelist[b-1].adjacentnode.append(a-1)
search(listsrch,nodelist)
print(count)

Submission status: Accepted

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

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

    def dfs(v: int):
        nonlocal visited
        nonlocal ans
        if all(visited):
            ans += 1
            return
        for n in edges[v]:
            if visited[n]:
                continue
            visited[n] = True
            dfs(n)
            visited[n] = False
        return

    dfs(0)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import permutations

N, M = map(int, input().split())
INF = 10**18
matrix = [[INF]*N for _ in range(N)]
for _ in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    matrix[a][b] = 1
    matrix[b][a] = 1

ans = 0


for p in permutations(range(1, N)):
    ok = True
    cur = 0
    for pi in p:
        if matrix[cur][pi] == INF:
            ok = False
            break
        cur = pi
    if ok:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys

    sys.setrecursionlimit(10 ** 7)

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

    g = tuple(set() for _ in range(N))
    for _ in range(M):
        a, b = (int(x) - 1 for x in input().split())
        g[a].add(b)
        g[b].add(a)

    def dfs(v=0, visited=1 << 0):
        if visited == (1 << N) - 1:
            return 1

        ret = 0
        for u in g[v]:
            if (visited >> u) & 1:
                continue
            ret += dfs(u, visited | (1 << u))
        return ret

    ans = dfs()
    print(ans)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Accepted

Solution code:
#最初に置いておくもの
import copy
import sys
sys.setrecursionlimit(50000000) 

#入出力関係
N, M = map(int, input().split())
l = []

for i in range(M):
    l.append(list(map(lambda x: int(x)-1 , input().split())))

lis = [[] for i in range(N)]

for i in range(M):
    lis[l[i][0]].append(l[i][1])
    lis[l[i][1]].append(l[i][0])

def dfs():
    re=0
    q1 =[[0]*N]
    q2=[0]
    while len(q1) != 0:
         
        visited=q1.pop()
        v=q2.pop()
        visited[v]=1
        if all(visited[c]==1 for c in range(N)):
            re += 1
        elif len(lis[v]) != 0:
            for i in lis[v]:
                if visited[i] == 0:
                    hoge=copy.deepcopy(visited)                    
                    q1.append(hoge)
                    q2.append(i)
    return re

print(dfs())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)


def dfs(v):
    global ans
    if all(visited[i] == 1 for i in range(n)):
        ans = ans + 1
        return
    for i in range(n):
        if gra[v][i] == 1 and visited[i] == 0:
            visited[i] = 1
            dfs(i)
            visited[i] = 0
    return


if __name__ == '__main__':
    n, m = map(int, input().split())
    ans = 0
    visited = [0]*n
    gra = [[0]*n for _ in range(n)]
    visited[0] = 1
    for _ in range(m):
        a, b = map(lambda x: int(x) - 1, input().split())
        gra[a][b] = 1
        gra[b][a] = 1
    dfs(0)
    print(ans)

Submission status: Accepted

Solution code:
import itertools

n,m = [int(i) for i in input().split()]

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

ans = 0

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n,m = list(map(int,input().split()))
ab = [list(map(int,input().split())) for i in range(m)]

#逆順にしたもの追加
ab += [[b,a] for a,b in ab]

#辺id付きで、idがfrom,abi[from]=[to1,to2,...] のリスト
abi = [[] for _ in range(n+1)]
for i,(a,b) in enumerate(ab):
    abi[a].append(b)



#再起のlimitを上げる
import sys
sys.setrecursionlimit(4100000)

def dfs(idx=1,visitted=[1],cnt=1):
    ret = 0
    if cnt==n:
        return 1
    for to in abi[idx]:
        if to not in visitted:
            ret += dfs(to,visitted+[to],cnt+1)
    return ret
print(dfs())

Submission status: Accepted

Solution code:
from itertools import permutations

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

ans = 0
for comb in permutations(range(1, N), N-1):
    v = 0
    valid = True
    for i in comb:
        if i not in graph[v]:
            valid = False
            break
        v = i
    if valid:
        ans += 1

print(ans)

Submission status: Accepted

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

for a, b in ab:
    a -= 1
    b -= 1
    G[a].add(b)
    G[b].add(a)

ans = 0
for x in permutations(range(1, N)):
    if x[0] in G[0]:
        for i in range(N-1):
            if i < N-2:
                if x[i+1] in G[x[i]]:
                    continue
                else:
                    break
            else:
                ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**8)
n,m = map(int,input().split())
graph = [[]for i in range(n)]
visited = [0]*n
def all_v(visited):
    cnt = 0
    for x in visited:cnt+=x
    return cnt == n
def dfs(now):
    visited[now] = 1
    if all_v(visited):return 1
    res = 0
    for next in graph[now]:
        if visited[next]:continue
        res += dfs(next)
        visited[next] = 0
    return res
    
for i in range(m):
    a,b = map(int,input().split())
    a-=1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
print(dfs(0))

Submission status: Accepted

Solution code:
def main():
    N, M = (int(i) for i in input().split())
    edge = [set() for _ in range(N)]
    for i in range(M):
        a, b = (int(i) for i in input().split())
        edge[a-1].add(b-1)
        edge[b-1].add(a-1)
    from itertools import permutations
    ans = 0
    for p in permutations(range(1, N)):
        u = 0
        for v in p:
            if v not in edge[u]:
                break
            u = v
        else:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

input=sys.stdin.readline

n,m=map(int,input().split())
G=[[False]*n for _ in range(n)]
used=[False]*n

def dfs(now,depth):
    if used[now]:
        return 0
    if n==depth:
        return 1
    used[now]=True
    ans=0
    for i in range(n):
        if G[now][i]:
            ans+=dfs(i,depth+1)
    used[now]=False
    return ans

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

print(dfs(0,1))

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = False

def func(now, ignore):
    if len(ignore) == n:
        return 1
    res = 0
    for i in points[now]:
        if i in ignore:
            continue
        nignore = deepcopy(ignore)
        nignore.append(i)
        res += func(i, nignore)
    return res

n, m = MAP()
ab = [LIST() for _ in range(m)]
points = [[] for _ in range(n)]
for i in range(n):
    for j in range(m):
        if ab[j][0] == i + 1:
            points[i].append(ab[j][1] - 1)
        elif ab[j][1] == i + 1:
            points[i].append(ab[j][0] - 1)
    #points[i].sort()
debug(points)

ans = func(0, [0])
print(ans)

Submission status: Accepted

Solution code:
def examA():
    O = SI()
    E = SI()
    ans = ""
    for i in range(len(O)+len(E)):
        if i%2==0:
            ans += O[i//2]
        else:
            ans += E[i//2]
    print(ans)
    return

def examB():
    A = LI()
    A.sort()
    ans = (A[2] - A[0]) // 2 + (A[2] - A[1]) // 2
    if (A[2]-A[0])%2==1:
        ans += 1
        if (A[2]-A[1])%2==0:
            ans += 1
    elif (A[2]-A[1])%2==1:
        ans += 2
    print(ans)
    return

def examC():
    S = SI()
    S.replace("RL","A")
    S.replace("LR","B")
    N = len(S)
    A = [0]*N
    print(S)
    l = 0; r = 0
    for i,s in enumerate(S):
        if s=="A":
            A[i] += r
        elif s=="B":
            A[i] += l
    ans = 0
    print(ans)
    return

def examD():
    def warshall_floyd(n, d):
        # d[i][j]: iからjへの最短距離
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])
        return d
    H, W = LI()
    C = [LI()for _ in range(10)]
    A = [LI()for _ in range(H)]
    C = warshall_floyd(10,C)
    ans = 0
    for i in range(H):
        for j in range(W):
            a = A[i][j]
            if a==-1:
                continue
            ans += C[a][1]
    print(ans)
    return

def examE():
    N, M = LI()
    V = [[]for _ in range(N)]
    for _ in range(M):
        a, b = LI()
        a -= 1; b -= 1
        V[a].append(b)
        V[b].append(a)

    def dfs(s,visited):
        #print(s,visited)
        res = 0
        visited.add(s)
        if len(visited)==N:
            visited.remove(s)
            return 1
        for ne in V[s]:
            if ne in visited:
                continue
            res += dfs(ne,visited)
        visited.remove(s)
        return res

    visited = set()
    ans = dfs(0,visited)
    #print(visited)
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examE()

"""

"""

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())
    path[a-1][b-1] = True
    path[b-1][a-1] = 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:
from itertools import permutations
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
connected = [[False] * (N+1) for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    connected[a][b] = connected[b][a] = True
ans = 0
for perm in permutations(list(range(2, N+1))):
    perm = (1,) + perm
    for i in range(N-1):
        u, v = perm[i], perm[i+1]
        if not connected[u][v]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations


def main():
    n, m = map(int, input().split())
    graph = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(lambda x: int(x) - 1, input().split())
        graph[a].append(b)
        graph[b].append(a)
    answer = 0
    for p in permutations([i for i in range(n)]):
        if p[0] != 0:
            continue
        if all(p[i] in graph[p[i - 1]] for i in range(1, n)):
            answer += 1
    print(answer)


if __name__ == '__main__':
    main()

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())
  a -= 1
  b -= 1
  G[a][b] = 1
  G[b][a] = 1
ans = 0
for l in permutations(range(n)):
  if l[0] != 0:
    continue
  for i in range(n-1):
    if not G[l[i]][l[i+1]]:
      break
  else:
    ans += 1
print(ans)

Submission status: Accepted

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

G = [[] for _ in range(N + 1)]
for el in ab:
    a, b = el
    G[a].append(b)
    G[b].append(a)

#print(G)
cnt = 0
seen=[False] * (N + 1)
def dfs(parent):
    global cnt
    seen[parent] = True
    if seen.count(True) == N:
        cnt += 1
    for child in G[parent]:
        if seen[child] == False:
            dfs(child)
            seen[child] = False
dfs(1)
print(cnt)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as dd
from itertools import permutations as permi
input = sys.stdin.readline
N, M = map(int, input().split())
e = dd(list)
for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)
res = 0
for p in permi([x for x in range(1, N + 1)], N):
  if p[0] != 1: continue
  go = list(p[: : -1])
  s = [go.pop()]
  while len(s):
    x = s.pop()
    if len(go) == 0: break
    for y in e[x]:
      if y == go[-1]:
        s.append(go.pop())
        break
  res += len(go) == 0

print(res)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m = inpl()
g = [set() for _ in range(n)]
for i in range(m):
    a,b = inpl()
    a -= 1; b -= 1
    g[a].add(b)
    g[b].add(a)
res = 0
for a in itertools.permutations(range(1,n)):
    a = [0] + list(a)
    for i in range(n-1):
        x = a[i]; y = a[i+1]
        if x in g[y]:
            continue
        else:
            break
    else:
        # print(a)
        res += 1
print(res)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
edge=[n*[0]for _ 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
from itertools import permutations
ans=0
for i in permutations([j for j in range(1,n)],n-1):
	f=True
	t=[0]+list(i)
	for j in range(1,n):
		if edge[t[j-1]][t[j]]==0:f=False
	if f:ans+=1
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

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

for _ in range(M):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].add(to)
    edges[to].add(fr)

def existsPath(path):
    for fr, to in zip(path, path[1:]):
        if not to in  edges[fr]:
            return False
    return True

ans = 0
for path in permutations(range(1, N), r=N-1):
    if existsPath((0,) + path):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations


def is_possible_case(per):
    prv_node = 0
    for node in per:
        if node not in g[prv_node]:
            return 0
        prv_node = node
    return 1


if __name__ == '__main__':
    N, M = map(int, input().split())
    g = {i: [] for i in range(N)}
    for _ in range(M):
        a, b = map(int, input().split())
        g[a - 1].append(b - 1)
        g[b - 1].append(a - 1)

    ans = 0
    for per in permutations([i for i in range(1, N)]):
        ans += is_possible_case(per)

    print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

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

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

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 itertools

n,m=map(int, input().split()) 
ab=[list(map(int, input().split())) for _ in range(m)]
#ab=Input.split()
#d：隣接行列

d = [[] for i in range(n)]
for i in range(m):
    a = ab[i][0]
    b = ab[i][1]
    d[a-1].append(b-1)
    d[b-1].append(a-1)
    
#per：順列列挙
per= itertools.permutations(range(1,n))
ans=0
for i in per:
    cnt=1
    x = [0]+list(i)
    for j in range(1,n):
        #隣接していなければ終了
        if not x[j] in d[x[j-1]]:
            break
        else:
            cnt+=1
    if(cnt==n):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import  itertools

N,M=map(int,input().split())
graph = [[] for _ 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)

def judge(pattern):
    if pattern[0]!=0:
        return False
    else:
        flag=True
        for i in range(len(pattern)-1):
            if pattern[i+1] in graph[pattern[i]]:
                continue
            else:
                flag=False
        if flag:
            return True
        return False

nums=[]
for i in range(N):
    nums.append(i)
ans=0
for pa in itertools.permutations(nums,N):
    pas=list(pa)
    if judge(pas):
        ans+=1

print(ans)

Submission status: Accepted

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

for i in range(m):
    ai,bi=map(int,input().split())
    a.append([ai,bi])
              
ni=[0]*n
nii=[]
    
def pathm(n,a,bi,pcnt,ni):
    if n==1:
        pcnt=pcnt+1
#        print("2:","n:",n,"bi:",bi,"pcnt:",pcnt)
        return pcnt
    else:
        n=n-1
        nii.append(bi)
        for mm in range(m):
            if a[mm][0]==bi and not a[mm][1] in nii:
#            if a[mm][0]==bi :
                ni[a[mm][1]-1]=1
#                print("1:","n:",n,"mm:",mm,"a[mm][1]:",a[mm][1],"pcnt:",pcnt)
                pcnt=pathm(n,a,a[mm][1],pcnt,ni)
            if a[mm][1]==bi and not a[mm][0] in nii:
#            if a[mm][1]==bi  and ni[a[mm][0]-1]==0 :
                ni[a[mm][0]-1]=1
#                ni[mm]=1
#                print("1:","n:",n,"mm:",mm,"a[mm][0]:",a[mm][0],"pcnt:",pcnt)
                pcnt=pathm(n,a,a[mm][0],pcnt,ni)
        nii.pop()
        return pcnt       
                
pcnt=0
pcnt1=pathm(n,a,1,pcnt,ni)
print(pcnt1)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
data = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    data[a-1].append(b-1)
    data[b-1].append(a-1)
ans = 0
def search(passed):
    if len(passed)==n:
        global ans
        ans += 1
    else:
        for i in data[passed[-1]]:
            if i in passed:
                continue
            else:
                search(passed+[i])
search([0])
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
from fractions import gcd

NN = 202020
MOD = 10**9+7
INF = float("inf")

n, m = map(int, input().split())
Edge = [list(map(int, input().split())) for i in range(m)]
graph = [set() for _ in range(n)]

for e in Edge:
    graph[e[0]-1].add(e[1]-1)
    graph[e[1]-1].add(e[0]-1)


def next_node(idx, A):
    if idx == n-1:
        return True
    if A[idx+1] in graph[A[idx]]:
        return next_node(idx+1, A)
    else:
        return False


count = 0
for li in itertools.permutations([i+1 for i in range(n-1)]):
    count += next_node(0, [0]+list(li))
    # if next_node(0, [0]+list(li)):
    #     print([0]+list(li))

print(count)

Submission status: Accepted

Solution code:
import itertools

count = 0
N, M = map(int, input().split())
listN = [i for i in range(2, N + 1, 1)]
listM = []
for j in range(M):
    new_keiro = list(map(int, input().split()))
    listM.append(new_keiro)
    listM.append(new_keiro[::-1])

all_listN = list(itertools.permutations(listN))

for now_listN in all_listN:
    judge = True
    if [1 ,now_listN[0]] in listM:
        x = 0
    else:
        judge = False
    for k in range(len(now_listN) - 1):
        if [now_listN[k],now_listN[k + 1]] in listM:
            x = 0
        else:
            judge = False
    count += judge

print(count)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
G=[[False]*N for i in range(N)]
for i in range(M):
  a,b=map(int,input().split())
  G[a-1][b-1]=G[b-1][a-1]=True
V=[False]*N
V[0]=True

def dfs(v):
  if not False in V: return 1
  ret=0
  for i in range(N):
    if not G[v][i]: continue
    if V[i]: continue
    V[i]=True
    ret+=dfs(i)
    V[i]=False
  return ret

print(dfs(0))

Submission status: Accepted

Solution code:
from collections import defaultdict

N,M = map(int,input().split())
edges = [list(map(int,input().split())) for _ in range(M)]
G = defaultdict(list)

is_visited1 = [False] * N

for frm,to in edges:
    G[frm].append(to)
    G[to].append(frm)

def hamilton(node,is_visited,ans):
    #print(is_visited)
    #print(node) 
    is_visited[node-1] =True
    if not False in is_visited:
        ans += 1
        return ans
    for no in G[node]:
        if is_visited[no-1]:
            continue
        ans = hamilton(no,is_visited,ans)
        is_visited[no-1] =False
    #is_visited[node-1] =False        
    return ans
print(hamilton(1,is_visited1,0))

Submission status: Accepted

Solution code:
graph=[[False for _ in range(8)] for _ in range(8)]
visited=[False for _ in range(8)]

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

    if(all_visited):
        return 1

    ret=0

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


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

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

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
from collections import Counter, deque
import itertools
#from scipy.misc import comb

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

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

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

ans = 0
for v in itertools.permutations(l, N-1):
    tmp = 0
    a = 0
    for b in v:
        if b in G[a]: tmp += 1
        a = b

    if tmp == N-1: ans += 1

print(ans)

Submission status: Accepted

Solution code:
from   itertools import   permutations

N,M = map(int, input().split())
L = [list(map(int,input().split())) for _ in range(M)]
graph = [[False] * (N + 1) for _ in range(N + 1)]
#%%

for i in L:
    graph[i[0]][i[1]] = True
    graph[i[1]][i[0]] = True

graph[0][1] = True
graph[1][0] = True
#%%
ans = 0
for i in permutations(range(1, N + 1)):
    if i[0] != 1:
        continue
    for j in range(1, N):
        if not graph[i[j - 1]][i[j]]:
            break
    else:
       ans += 1 

print(ans)

Submission status: Accepted

Solution code:
import itertools
N,M=map(int,input().split())
a=[]
b=[]
for i in range(M):
  a1,b1=map(int,input().split())
  a.append(a1)
  b.append(b1)

count=0

s=[i for i in range(1,N+1)]
x=list(itertools.permutations(s))
for i in x:
  if(i[0]!=1):
    break
  else:
    #print(i)
    flag=0
    for j in range(N-1):
      for k in range(len(a)):
        if((a[k]==i[j] and b[k]==i[j+1])or(b[k]==i[j] and a[k]==i[j+1])):
          flag+=1
          break
    if(flag==N-1):
      count+=1
print(count)

Submission status: Accepted

Solution code:
import itertools
n,m = list(map(int,input().split()))
A = [list(map(int,input().split())) for _ in range(m)]
a = [0]*n
for x,y in A:
  a[x-1] |= 1<<(y-1)
  a[y-1] |= 1<<(x-1)

def bitdp(n, a):
  dp = [[0]*n for _ in range(1<<n)]
  dp[1][0] = 1
  
  for bit in range(1<<n):
    for v in range(n):
      if bit & 1<<v:
        sub = bit ^ (1<<v)
        
        for u in range(n):
          if (sub & 1<<u) and (a[v] & 1<<u):
            dp[bit][v] += dp[sub][u]
  ans = sum(dp[(1<<n)-1][u] for u in range(1,n))
  return ans

ans = bitdp(n,a)
print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m = map(int,input().split())
perm = []
for j in range(n):
	perm.append(j)
perm_list = list(itertools.permutations(perm))
	
net_arr = [[0 for _ in range(n)] for _ in range(n)]
for i in range(0,m):
	a,b = map(int,input().split())
	a -= 1
	b -= 1
	net_arr[a][b] = 1
	net_arr[b][a] = 1
def check_path(path,net):
	for i in range(len(path)-1):
		if not net_arr[path[i]][path[i+1]] == 1:
			return False
	return True
	
ans = 0
for path in perm_list:
	if not path[0] == 0:
		break
	if check_path(path,net_arr):
		ans += 1	
print(ans)

Submission status: Accepted

Solution code:
from itertools import *
n,m = map(int,input().split())
path = [set() for _ in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    path[a-1].add(b-1)
    path[b-1].add(a-1)
ans = 0

for r in permutations(list(range(1,n))):
    p = 0
    flag = True
    for i in r:
        if not i in path[p]:
            flag = False
        p = i
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

def dfs(G, visited, s, n, ans):
  # すべての頂点を訪れた場合の処理
  if all(visited) :
    ans += 1
    return ans
  #　次の頂点の探索
  for i in range(n) :
    if visited[i] == False and (G[s][i] == 1 or G[i][s] == 1) :
      visited[i] = True
      ans = dfs(G, visited, i, n, ans)
      visited[i] = False
  return ans

#　グラフGの入力
n,m = map(int,input().split())
G = [[0 for i in range(n)] for j in range(n)]
for i in range(m) :
  a,b = map(int,input().split())
  G[a-1][b-1] = 1
  G[b-1][a-1] = 1
  

visited = [False for i in range(n)]
visited[0] = True
ans = 0
print(dfs(G, visited, 0, n, ans))

Submission status: Accepted

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

#頂点の番号はindex+1
for i in range(M):
    a, b = map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

visited = []
for i in range(N):
    visited.append(0)
visited[0] = 1

#print(graph)

ans = 0

#jを訪れたときはvisited[j]が1になる

def dfs(v):
    global ans
    global visited
    kita = 0
    for k in visited:
        if k == 1:
            kita += 1
        
    if kita == N:
        ans += 1
    

    for j in graph[v]:
        #print(j)
        if visited[j] == 1:
            continue
        visited[j] = 1
        dfs(j)
        visited[j] = 0


dfs(0)

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

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

dic=defaultdict(list)
for i in range(m):
    a,b=ab[i]
    dic[a-1].append(b-1)
    dic[b-1].append(a-1)
# print(dic)

d=deque([[0,0]])

ans=0
while d:
    now,itta=d.popleft()
    ikeru=dic[now]
    itta+=pow(2,now)
    # print(ans,now,itta)
    if itta==pow(2,n)-1:
        ans+=1
    for i in ikeru:
        if itta&pow(2,i)==0:
            d.append([i,itta])
            # print(d)
print(ans)