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:
from collections import deque

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

# n!通りの全探索?

"""
- 頂点起点で見る
     - 全パターン書き出す
- 辺起点で見る
"""
ans = deque([[1]])

while ans:
    a = ans.popleft()
    for i in range(2, N + 1):
        if i not in a:
            ans.append(a + [i])
    if len(ans[0]) == N:
        break

cnt = 0

for a in ans:
    tmp_cnt = 0
    for i in range(len(a) - 1):
        if [a[i], a[i + 1]] in AB or [a[i + 1], a[i]] in AB:
            tmp_cnt += 1
            continue
        else:
            break
    if tmp_cnt == len(a) - 1:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import numpy as np

N, M = map(int, input().split())
edge = [[] for i in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edge[a].append(b)
    edge[b].append(a)
# print(*edge, sep='\n')

# N, M = 3, 3
# edge = [[1, 2], [0, 2], [0, 1]]


def dfs(v):
    if sum(visited) == N:
        return 1

    res = 0
    for i in edge[v]:
        if visited[i] == 1:
            continue
        visited[i] = 1
        res += dfs(i)
        visited[i] = 0
    return res


visited = [0] * N

visited[0] = 1
ans = dfs(0)

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
# dfs, check path len, count paths                                                                                                                           
# test = 2                                                                                                                                                   
n, m = map(int, input().split())
edges = [map(int, input().split()) for i in range(m)]
graph = defaultdict(list)
for k,v in edges:
    graph[k].append(v)
    graph[v].append(k)

cnt = 0
# dfs                                                                                                                                                        
def dfs(node, visited):
    global cnt
    if node in visited:
        return None
    elif len(visited) + 1 == n:
        cnt += 1
        return None
    else:
        for v in graph[node]:
            dfs(v, visited+[node])
dfs(1, [])
print(cnt)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq
from bisect import bisect_left, insort_left

def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iip_ord():
    return [ord(i) - ord("a") for i in input()]


def main():
    r = solve()
    if r is not None:
        print(r)

def solve():
    N, M = iip(True)
    lines = {}
    for i in range(N):
        lines[i] = []

    for i in range(M):
        a, b = iip(True)
        lines[a-1].append(b-1)
        lines[b-1].append(a-1)

    c = [[0]]
    for a in range(1, N):
        n = []
        for i in c:
            for j in range(N):
                if j in i:
                    continue
                ct = [k for k in i]
                ct.append(j)
                n.append(ct)
        c = n

    kh = []
    for i in c:
        for j in range(N):
            if j not in i:
                break
        else:
            kh.append(i)

    ans = 0
    for root in kh:
        for i in range(N):
            if i == N-1:
                ans += 1
                break
            else:
                if not root[i+1] in lines[root[i]]:
                    break

    print(ans)

#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
links = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(M)]
paths = 0

def search(cur, last):
    global paths
    if len(last) == 0:
        paths += 1
        return
    
    for i in list(last):
        if sorted([cur, i]) in links:
            pass_last = last.copy()
            pass_last.remove(i)
            search(i, pass_last)
    
search(0, set(range(1, N)))
print(paths)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
#グラフの連結成分を調べる
def Graph(ab):
    G=[[] for i in range(n)]
    for a,b in ab:
        G[a-1].append(b)
        G[b-1].append(a)
    return G
from collections import deque
def dfs(G,v,p,n):
    q=deque()
    q.append((v,p,1,0))
    log=[0]*n
    log[v-1]=1
    ans=0
    while q:
        V,P,cnt,S=q.pop()
        if S==0:
            #下に遷移していくときの処理
            q.append((V,P,cnt,1))
            for new_v in G[V-1]:
                if new_v==P:continue
                if log[new_v-1]:continue
                log[V-1]=1
                #print(V, new_v, cnt, q, log)
                if cnt==n-1:
                    ans+=1
                    continue
                q.append((new_v,V,cnt+1,0))

        else:
            log[V-1]=0
    return ans

n,m=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(m)]
G=Graph(ab)
#print(G)
ans=dfs(G,1,-1,n)
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(M)]
 
graph = [[False] * N for _ in range(N)]
for u, v in edges:
    graph[u - 1][v - 1] = True
    graph[v - 1][u - 1] = True
 
visited = [False] * N
visited[0] = True
 
def dfs(s):    
    if all(visited):
        return 1
 
    cnt = 0
    for i in range(N):
        if not graph[s][i]:
            continue
        
        if visited[i]:
            continue
            
        visited[i] = True
        cnt += dfs(i)
        visited[i] = False
        
    return cnt
 
print(dfs(0))

Submission status: Accepted

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

lst=[[] for _ in range(N+1)]
for el in ab:
    lst[el[0]].append(el[1])
    lst[el[1]].append(el[0])
#print(lst)

seen=[False]*(N+1)
todo=[]


counter=0
def func(n):
    global counter
    #print(n, seen, seen.count(True), counter)
    if seen.count(True)==N:
        counter+=1
        #print(counter)

    seen[n]=True
    for val in lst[n]:
        if seen[val]==False:
            seen[val]=True
            func(val)
            seen[val]=False
func(1)
print(counter)

Submission status: Accepted

Solution code:
import itertools

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

lst=[[] for _ in range(N+1)]
for el in ab:
    lst[el[0]].append(el[1])
    lst[el[1]].append(el[0])
#print(lst)

count=0
for permu in itertools.permutations(range(1,N+1)):
    if permu[0] == 1:
        for i in range(0,N-1):
            if permu[i+1] in lst[permu[i]]:
                pass
            else:
                break
        else:
            count+=1
            #print(permu)
print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import itertools

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

p=list(itertools.permutations([i for i in range(2,N+1)]))
now=1
ans=0
for i in p:
    now=1
    frag=True
    for g in range(N-1):
        if i[g] in d[now]:
            now = i[g]
        else:
            frag=False
            break
    if frag:
        ans+=1
print(ans)

Submission status: Accepted

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

from collections import deque
from copy import copy,deepcopy
from itertools import permutations

def myinput():
    return map(int,readline().split())

def mycol(data,col):
    return [ row[col] for row in data ]

n,m = myinput()
ab = [ list(myinput()) for _ in range(m) ]

v = list(range(1,n+1))
p = list(permutations(v))
# print(p)

count = 0
for s in p:
    # print(s)
    if s[0]!=1:
        pass
    else:
        flag = True
        for j in range(n-1):
            v_tmp = s[j]
            v_next = s[j+1]
            c = [v_tmp,v_next]
            d = [v_next,v_tmp]
            if ( c in ab ) or ( d in ab ):
                pass
            else:
                flag = False

        if flag:
            count += 1
        else:
            pass
    # print(count)

print(count)

Submission status: Accepted

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

i_i = lambda: int(i_s())
i_l = lambda: list(map(int, stdin.readline().split()))
i_s = lambda: stdin.readline().rstrip()

N, M = i_l()
matrix = [[0] * N for _ in range(N)]

for i in range(M):
    a, b = i_l()
    matrix[a-1][b-1] = 1
    matrix[b-1][a-1] = 1

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

print(cnt)

Submission status: Accepted

Solution code:
import itertools

N, M = map(int, input().split())
lst = [set() for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    lst[a].add(b)
    lst[b].add(a)

ans = 0
for t in itertools.permutations(range(2, N + 1)):
    tmp = 1
    for x in t:
        if x not in lst[tmp]:
            break
        tmp = x
    else:
        ans += 1
print(ans)

Submission status: Accepted

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

import numpy as np
graph = np.zeros((n,n))
for i in range(m):
    a,b = map(int,input().split())
    graph[a-1][b-1] = graph[b-1][a-1] = 1

from itertools import permutations
nv = [i for i in range(1,n)]
def main():
    def checkroot(root,graph):
        if graph[0][root[0]] == 0:
            return 0
        for i in range(1,len(root)):
            if graph[root[i]][root[i-1]]==0:
                return 0
        return 1

    ans = 0
    for root in permutations(nv):
        if checkroot(root,graph)==1:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import copy
n,m=map(int,input().split())
ab=[]
for i in range(m):
    ab.append(list(map(int,input().split())))

ans=0
def dfs(start,finish):
    global ans
   # print(finish)
    if len(finish)==n:#全部回ってたら終了
        ans+=1
    else:
        for i in adlist[start-1]:
            if i not in finish:#通ったところに入っていないなら通れるということ   
                #print(i)
                #print(adlist)
                #print(finish,1)
                finish_1 = set([i]) | finish
                #print(finish_1,2)
                dfs(i,finish_1)#finish=だと繰り返しの時に更新されるのでダメ copyもダメ　addが使えない　和集合出ないとfinishが更新されてしまう
#finishを一回ごとに変えないといけない
adlist=[]
for h in range(n):    
    adlist.append([])
for j in range(m):
    x=ab[j][0]
    y=ab[j][1]
    adlist[x-1].append(y)
    adlist[y-1].append(x)
finish=set()
finish.add(1)
#print(adlist)
dfs(1,finish)#引数がけすノード
print(ans)

Submission status: Accepted

Solution code:
# next_permutationで解く
import itertools
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)

# 次の状態に遷移できるかどうかをしてbreakせず最後まで行けたらansをインクリメントする
ans = 0
for x in itertools.permutations(range(N)):
    now = 0
    if x[0] == 0:
        # 始点ノードが0のもののみ試す
        for e in x[1:]:
            if e not in graph[now]:
                break
            now = e
        else:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

def check(adj, pat):
    pos = 1
    for p in pat:
        if p not in adj[pos]:
            return 0
        else:
            pos = p
    return 1

def main():
    n, m = [int(i) for i in input().split()]
    adj = {i+1:[] for i in range(n)}
    for _ in range(m):
        a, b = [int(i) for i in input().split()]
        adj[a].append(b)
        adj[b].append(a)

    res = 0
    for t in permutations(range(2, n+1)):
        res += check(adj, t)
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

n, m = map(int, input().split())
graph = {i + 1 : set() for i in range(n)}
for i in range(m):
    a, b = map(int, input().split())
    graph[a] |= set([b])
    graph[b] |= set([a])
count = 0
node = [i + 2 for i in range(n - 1)]
for i in itertools.permutations(node):
    route = [1] + list(i)
    flag = True
    for j in range(n - 1):
        if route[j + 1] not in graph[route[j]]:
            flag = False
            break
    if flag == True:
        count += 1
print(count)

Submission status: Accepted

Solution code:
from itertools import permutations
import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    link = [[False] * N for i in range(N)]
    for i in range(M):
        a, b = map(int, input().split())
        link[a-1][b-1] = True
        link[b-1][a-1] = True
    
    ans = 0
    for p in permutations(range(1, N)):
        # print(0, p)
        pre = 0
        ok = True
        for t in p:
            if not link[pre][t]:
                ok = False
                break
            pre = t
        if ok:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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



def dfs(x, y, l):
    if y == n - 1:
        return 1
    else:
        ans = 0
        for i in range(len(g[x])):
            if not g[x][i] in l:
                l2 = l + [g[x][i]]
                ans += dfs(g[x][i], y + 1, l2)
        return ans

print(dfs(0, 0, [0]))

Submission status: Accepted

Solution code:
import itertools

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

node = [i for i in range(2,n+1)]
permutations_node = itertools.permutations(node)
ans = 0

for one_node in permutations_node:
    start = 1
    memo = []
    for x in one_node:
        for edge_x, edge_y in edges:
            if edge_x == start and edge_y == x and x not in memo:
                memo.append(x)
                start = x
            if edge_x == x and edge_y == start and x not in memo:
                memo.append(x)
                start = x
                
    if len(memo) == n-1:
        ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations


class Graph():
    def __init__(self):
        self.adjacency_dict = {}

    def add_vertex(self, v):
        self.adjacency_dict[v] = []

    def add_edge(self, v1, v2):
        self.adjacency_dict[v1].append(v2)
        self.adjacency_dict[v2].append(v1)

    def exists(self, path):
        for i in range(len(path)-1):
            if not path[i+1] in self.adjacency_dict[path[i]]:
                return False
        return True


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

    graph = Graph()
    for v in range(1, N+1):
        graph.add_vertex(v)
    for e in edges:
        graph.add_edge(e[0], e[1])

    count = 0
    for path in permutations(range(2, N+1)):
        path = list(path)
        path.insert(0, 1)
        if graph.exists(path):
            count += 1
    print(count)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
import copy
from copy import deepcopy
import sys
import fractions
# import numpy as np
from functools import reduce
# import statistics
import decimal
import heapq
import collections
import itertools
from operator import mul

sys.setrecursionlimit(100001)


# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) - 1 for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

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

d = getSomeInputListInt(m)

path = []
for p in itertools.permutations(range(1, n), n-1):
    tmp = (0,) + p
    path.append(tmp)


def pathsearch(a, b):
    flga = False
    for tmp_d in d:
        if a in tmp_d and b in tmp_d:
            flga = True
            break

    return flga


ans = 0
for p in path:
    flg = True
    for i in range(1, n, 1):
        tmp = pathsearch(p[i - 1], p[i])
        if not tmp:
            flg = False
            break

    if flg:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m=map(int,input().split())
graph=[[False for h in range(n)] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1;b-=1
    graph[a][b]=True
    graph[b][a]=True
l=[i for i in range(1,n)]
ans=0
if n==2:
    print(m)
    exit()
for v in itertools.permutations(l):
    flag=1
    if graph[0][v[0]]==False:continue
    else:
        c=v[0]
        for j in v[1:]:
            if graph[c][j]==False:
                flag=0
                break
            c=j
        ans+=flag
print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m=map(int,input().split())
G=[[0]*n for i 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
S=""
for i in range(1,n):
  S=S+str(i)
ans=0
for x in itertools.permutations(S):
  a=0
  if G[0][int(x[0])]==0:
    a=1
  for i in range(n-2):
    if G[int(x[i])][int(x[i+1])]==0:
      a=1
  if a==0:
    ans=ans+1
print(ans)

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
n,m=f()
g=[set() for _ in range(n)]
for i in range(m):
  a,b=f()
  g[a-1].add(b-1)
  g[b-1].add(a-1)
import itertools as it
c=0
for t in it.permutations(range(1,n)):
  p=0
  for q in t:
    if q not in g[p]: break
    p=q
  else: c+=1
print(c)

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
n,m=f()
g=[[0]*n for _ in range(n)]
for i in range(m):
  a,b=f(); g[a-1][b-1]=g[b-1][a-1]=1
import itertools as it
c=0
for t in it.permutations(range(1,n)):
  p=0
  for q in t:
    if g[p][q]<1: break
    p=q
  else: c+=1
print(c)

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
n,m=f()
g=[[0]*n for _ in range(n)]
for i in range(m):
  a,b=f(); g[a-1][b-1]=g[b-1][a-1]=1
import itertools as it
c=0
for t in it.permutations(range(1,n)):
  p,d=0,1
  for q in t: d*=g[p][q]; p=q
  c+=d
print(c)

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
n,m=map(int,input().split())
g=[[0]*n for _ in range(n)]
for i in range(m):
  a,b=f()
  g[a-1][b-1]=1
  g[b-1][a-1]=1
import itertools as it
c=0
for t in it.permutations(range(1,n)):
  p=0
  for q in t:
    if g[p][q]<1: break
    p=q
  else: c+=1
print(c)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(m)]
import itertools
ans=0
l = [i for i in range(1,n+1)]
p = itertools.permutations(l, n)
for v in p:
  v=list(v)
  if v[0]!=1:
    continue
  x=0
  for i in range(n-1):
    w=v[i:i+2]
    w.sort()
    if w not in ab:
      x=1
      break
  if x==0:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
import  itertools 
n,m=map(int,input().split())
edges=[[0]*n  for i in range(n)]
#print(edges)
for _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    edges[a][b]=1
    edges[b][a]=1
#print(edges)
#generate all permutations
l=[i for i in range(n)]
p_obj=itertools.permutations(l)
ans=0
for i in p_obj:
    #print(i)
    if i[0]>0:
        break
    flag=True
    for j in range(1,n):
        if edges[i[j-1]][i[j]]==0:
            flag=False
            break
    if flag:
        ans+=1
print(ans)

Submission status: Accepted

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

n, m = list(map(int, input().split()))
data = [[] for _ 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 dfs(pos, cnt, his):
    global ans
    his[pos] = 1
    if cnt == n:
        if sum(his) == n:
            ans += 1
        return

    for next in data[pos]:
        dfs(next, cnt+1, his[:])


dfs(0, 1, [0]*n)
print(ans)

Submission status: Accepted

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

adjl=[[0 for i in range(n)] for j in range(n)]

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

import itertools
l=[i for i in range(1,n+1)]
ans=0
#p = itertools.permutations(l)
for v in itertools.permutations(l):
    #tupleで返ってくる
    #print(v[0])
    flag=True
    if v[0]!=1 :
        continue
    for i in range(n-1):
        if adjl[v[i]-1][v[i+1]-1]==0:
            flag=False
            break
    if flag:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys 
sys.setrecursionlimit(1000000)
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] += [b]
  graph[b] += [a]

used = [0]*n
global ans 
ans = 0
def dfs(u):
  global ans
  used[u] = 1
  if sum(used) == n:
    ans += 1
    return 
  
  for v in graph[u]:
    if used[v] == 0:
      used[v] = 1
      dfs(v)
      used[v] = 0 

  return 

dfs(0)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

n, m = map(int, input().split())
graph = np.zeros((n, n), dtype=np.int8)
for _ in range(m):
    a, b = map(int, input().split())
    graph[a-1, b-1] = 1
    graph[b-1, a-1] = 1

def dfs(node, visited):
    if sum(visited) == n:
        return 1
    res = 0
    for i in range(n):
        if graph[node, i] and not visited[i]:
            visited[i] = 1
            res += dfs(i, visited)
            visited[i] = 0
    return res

print(dfs(0, [1] + [0] * (n - 1)))

Submission status: Accepted

Solution code:
from collections import defaultdict
N, M = list(map(int, input().split()))

edge_dict = defaultdict(set)
for i in range(M):
    a, b = list(map(int, input().split()))
    edge_dict[a].add(b)
    edge_dict[b].add(a)

def search(node: int, visited: set):
    visited.add(node)
    if len(visited) == N:
        return 1

    ans = 0
    for next_node in edge_dict[node]:
        if not next_node in visited:
            ans += search(next_node, visited.copy())
    return ans

visited = set()
node = 1
print(search(node, visited))

Submission status: Accepted

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

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

count = 0
visited = [0]*n
def dfs(initial,graph,visited):
    global count
    all_visited = True
    visited[initial] = 1
    for i in visited:
        if i == 0:
            all_visited = False 
            
    if all_visited == True:
        count += 1
        return 0
    
    for i in range(n):
        if graph[initial][i] ==1:
            if visited[i] == 0:
                visited[i] = 1
                dfs(i,graph  ,visited)
                visited[i] = 0
    return count


print(dfs(0 ,graph , visited ))

Submission status: Accepted

Solution code:
import itertools

n, m = map(int, input().split())
path = [[False] * 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

#print(path)
ans = 0
x = list(itertools.permutations(range(1,n)))
for i in range(len(x)):
    u = list(x[i])
    w = [0] + u
    ok = 0
    for j in range(n-1):
        if path[w[j]][w[j+1]]:
            ok += 1
        else:
            break

    if ok == n-1:
        #print(w)
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
# Author: cr4zjh0bp
# Created: Tue Mar 24 00:01:43 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from itertools import permutations

n, m = na()
ab = nan(m)
g = [[] for _ in range(n)]
for i in range(m):
    a, b = ab[i]
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

def dfs(i, c, p):
    if p[c] == i:
        if c == n - 1:
            return 1
    else:
        return 0
    res = 0
    for j in g[i]:
        res = max(res, dfs(j, c + 1, p))
    return res

ans = 0
for p in permutations(range(n)):
    if p[0] == 0:
        ans += dfs(0, 0, p)

print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
hen=[[] for i in range(0,N)]
for i in range(0,M):
    a,b=map(int,input().split())
    hen[a-1].append(b-1)
    hen[b-1].append(a-1)

def onestrokepath(start,visited=[]):
    flag=0
    count=0
    for next in hen[start]:
        if not next in visited:
            flag=1
            count+=onestrokepath(next,visited+[next])
    if flag==0:
        check=[i for i in range(0,N)]
        visited.sort()
        if check==visited:
            return 1
        else:
            return 0
    return count

print(onestrokepath(0,[0]))

Submission status: Accepted

Solution code:
import copy
from collections import deque
cnt = 0
def dfs(G,s,n,seen):
    global cnt
    li = copy.copy(seen)
    li.append(s)
    if len(li) == n:
        cnt += 1
        return 0
    for x in G[s]:
        if x in li:
            continue
        dfs(G,x,n,li)

N,m = map(int,input().split())
seen = []
G = [[] for _ in range(N)]
for i in range(m):
    a,b = map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
dfs(G,0,N,seen)
print(cnt)

Submission status: Accepted

Solution code:
import copy
from collections import deque
cnt=0
def dfs(G,s,N,seen):
    global cnt
    li=copy.copy(seen)
    li.append(s)
    if(len(li)==N):
        cnt+=1
        return 0
    for x in G[s]:
        if x in li:
            continue
        dfs(G,x,N,li)
        
N,M=map(int,input().split())
seen=[]
G=[[] for i in range(N)]
for i in range(M):
    a,b=map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
dfs(G,0,N,seen)
print(cnt)

Submission status: Accepted

Solution code:
from itertools import permutations
def check(i,j):
    if j==N-2 and x[j] in G[i]:
        return True
    if x[j] in G[i]:
        return check(x[j],j+1)
    return False
    
N,M = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
cnt = 0
for x in permutations(range(2,N+1),N-1):
    if check(1,0):
        cnt += 1
print(cnt)