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 sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


# ワーシャルフロイド (任意の2頂点の対に対して最短経路を求める)
# 計算量n^3 (nは頂点の数)
def warshall_floyd(d, n):
    #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


# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定



# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
n, m = map(int, input().split())
d = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    d[a - 1].append(b - 1)
    d[b - 1].append(a - 1)
# print(d)
queue = deque([])
queue.append([0, []])
ans = 0
while queue:
    x = queue.popleft()
    now = x[0]
    visited = x[1]
    if len(visited) == n - 1:
        ans += 1
        continue
    for i in d[now]:
        if i not in visited:
            queue.append([i, visited + [now]])
print(ans)

Submission status: Accepted

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

edge=[[] for i in range(n)]

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

ans=0
def search(his,nxt):
    global ans
    newhis=his.copy()
    newhis.append(nxt)
    if len(newhis)==n:
        ans+=1
        return
    for i in edge[nxt]:
        if i in newhis:continue
        search(newhis,i)




search([],0)

print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import fractions
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

N, M = getNM()
dist = [[] for i in range(N + 1)]
for i in range(M):
    a, b = getNM()
    dist[a - 1].append(b - 1)
    dist[b - 1].append(a - 1)

cnt = 0

pos = deque([[1 << 0, 0]])

while len(pos) > 0:
    s, v = pos.popleft()
    if s == (1 << N) - 1:
        cnt += 1
    for u in dist[v]:
        if s & (1 << u):
            continue
        pos.append([s | (1 << u), u])
print(cnt)

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 p in list(permutations(range(N))):
    if p[0] != 0:
        continue
    else:
        check = 1
        for i in range(N - 1):
            check *= matrix[p[i]][p[i+1]]
        ans += check

print(ans)

Submission status: Accepted

Solution code:
N,M=list(map(int,input().split()))
color=["white"]*(N+1)
relation_list=[[] for i in range(N+1)]
count=[0]
for i in range(M):
    a,b=list(map(int,input().split()))
    relation_list[a].append(b)
    relation_list[b].append(a)

def dfs(i,j,cnt,kako):
    keiro=kako[:]
    cnt += 1
    for k in relation_list[i]:
        if k not in keiro:
            keiro.append(k)
            dfs(k,i,cnt,keiro)
            del keiro[-1]
    if cnt==N:
        count[0]+=1
dfs(1,1,0,[1])
print(count[0])

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import numpy as np
n,m = map(int,input().rstrip().split())
connection_list = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().rstrip().split())
    connection_list[a-1].append(b-1)
    connection_list[b-1].append(a-1)

count = 0
def dfs(g,p,checked):
    global count
    checked[p] = 1
    if checked.all():
        count += 1
        return
    for next in g[p]:
        if checked[next] == 1:
            continue
        dfs(g,next,checked.copy())

checked = np.zeros(n,int)
dfs(connection_list,0,checked)
print(count)

Submission status: Accepted

Solution code:
from itertools import permutations
n,m=map(int,input().split())
s=[set(map(int,input().split())) for _ in range(m)]

ans=0
x=[i for i in range(2,n+1)]
cand=permutations(x)
for i in cand:
  crnt=1
  for nxt in i:
    if set([crnt,nxt]) in s:
      crnt=nxt
    else:
      break
  else:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

# 双方向グラフで幅優先探索

def main():
    N, M = map(int, input().split())
    graph = [[] for _ in range(N)]
    #隣接リストの作成
    for i in range(M):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        graph[a].append(b)
        graph[b].append(a)

    from itertools import permutations
    L = list(permutations(range(N)))
    ret = 0
    for l in L:
        fg = 1
        if l[0]!=0:
            continue
        for k in range(N-1):
            if not l[k+1] in graph[l[k]]:
                fg = 0
                break
        if fg == 1:
            ret += fg
    print(ret)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import permutations

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

edge = [[0 for i in range(N)] for j in range(N)]

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

ans = 0
for path in permutations(range(N)):
    flag = True
    if path[0] != 0:
        flag = False
    for i in range(N-1):
        if not edge[path[i+1]][path[i]]:
            flag = False
    
    ans += int(flag)

print(ans)

Submission status: Accepted

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

N, M = map(int, input().split())
ab = [list(map(int, input().split())) for n in range(M)]
branch = [[False]* N for n in range(N)]

for m in range(M):
  a = ab[m][0] - 1
  b = ab[m][1] -1 
  branch[a][b] = True
  branch[b][a] = True

ans = 0
pattern = itertools.permutations(range(1, N+1),N)
for l in pattern:
  if l[0] != 1:
    continue
  for n in range(N):
    if n == N - 1:
      ans += 1
      break
    p = l[n] -1
    np = l[n+1] -1
    if not(branch[p][np]):
      break

print(ans)

Submission status: Accepted

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

def func(x, c):
    global C
    c += 1
    last = True
    for r in R[x]:
        if r in Parents[x]:
            continue
        for i in range(len(Parents[x])):
            Parents[r].append(Parents[x][i])
        Parents[r].append(x)
        last = False
        func(r, c)
        for i in range(len(Parents[x])):
            Parents[r].remove(Parents[x][i])
        Parents[r].remove(x)
    if last:
        if c == N:
            C += 1

func(0, 0)
print(C)

Submission status: Accepted

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

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    def check(path, adj):
        n = len(path)
        for i in range(n-1):
            if not adj[path[i]][path[i+1]]:
                return False
        return True

    
    n, m = mi()
    adj = [[False]*n for _ in range(n)]
    for _ in range(m):
        a, b = mi_0()
        adj[a][b] = True
        adj[b][a] = True
    
    cnt = 0
    for pattern in permutations(range(1, n)):
        if check([0]+list(pattern), adj):
            cnt += 1
    print(cnt)



if __name__ == "__main__":
    main()

Submission status: Accepted

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

from itertools import permutations

def make_aja_mtx(N, M, A, B):
    D = [[0 for _ in range(N)] for _ in range(N)]
    for i in range(M):
        D[A[i]-1][B[i]-1] = 1
        D[B[i]-1][A[i]-1] = 1
    return D

def check(p, N, D):
    len_path = 1
    for i in range(1, N):
        if D[p[i-1]-1][p[i]-1] == 1:
            len_path += 1
        else:
            break
    return len_path == N
        
def perm(perm_2):
    for p in perm_2:
        yield (1,) + p

def Main(N, M, A, B):
    ns = range(2, N+1)
    perm_2 = permutations(ns, N-1)
    ans = 0
    D = make_aja_mtx(N, M, A, B)
    for p in perm(perm_2):
        if check(p, N, D):
            ans += 1
    return ans
    
print(Main(N, M, A, B))

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
ab = [LIST() for _ in range(M)]

#連結リスト
graph = [[] for _ in range(N)]

for a, b in ab:
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)

#print(graph)
ans = 0

for x in permutations(range(1, N)):
	tmp = 0
	for i in range(N-1):
		if x[i] in graph[tmp]:
			tmp = x[i]
		else:
			break
	else:
		ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
ab = [LIST() for _ in range(M)]

#隣接行列
graph = [[0]*N for _ in range(N)]

for a, b in ab:
	graph[a-1][b-1] = 1
	graph[b-1][a-1] = 1

ans = 0
for x in permutations(range(1, N)):
	x = list(x)
	x.insert(0, 0)
	#print(x)
	for i in range(N-1):
		if graph[x[i]][x[i+1]] != 1:
			break
	else:
		ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
ab = [LIST() for _ in range(M)]

#隣接行列
contact = [[0]*N for _ in range(N)]

for a, b in ab:
	contact[a-1][b-1] = 1
	contact[b-1][a-1] = 1

A = list(x for x in range(1, N))
ans = 0

for X in permutations(A, N-1):
	#print(X)
	tmp = 0
	for y in X:
		if contact[tmp][y] == 1:
			tmp = y
		else:
			break
	else:
		#print("成功")
		ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

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

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()

graph = defaultdict(list)
for _ in range(M):
	a, b = MAP()
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)

#print(graph)

ans = 0
A = list(range(1, N))

for x in permutations(A, N-1):
	#print(x)
	y = [0]
	tmp = graph[0]
	for i in range(N-1):
		if x[i] in tmp and not x[i] in y:
			y.append(x[i])
			tmp = graph[x[i]]
		else:
			break
	else:
		ans += 1
		#print("成功")

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

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

t = [num for num in range(1, n+1)]
ans = 0
for per in itertools.permutations(t):
  if per[0] != 1:
    continue
  for i in range(n-1):
    start = per[i]
    end = per[i+1]
    if not end in g[start]:
      break
  else:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
e=[[0 for _ in range(n)] for i in range(n)]
for i in range(m):
    a,s=map(int,input().split())
    e[a-1][s-1]=1;e[s-1][a-1]=1
ans=0
from itertools import permutations as pe
for i in pe(range(1,n),r=None):
    #rは長さ、Noneでiteraterの長さ
    pre=0
    for a in i:
        if e[pre][a]!=1:break
        pre=a
    else:ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque, Counter, defaultdict
from itertools import permutations
import heapq


def resolve():
    N, M = map(int, sys.stdin.readline().strip().split())
    adj_mat = [[False] * N for _ in range(N)]
    for _ in range(M):
        a, b = tuple(map(int, sys.stdin.readline().strip().split()))
        adj_mat[a-1][b-1] = True
        adj_mat[b-1][a-1] = True
    ans = 0
    for perm in permutations(range(N)):
        if perm[0] != 0:
            break
        cur = 0
        while cur < N - 1:
            if not adj_mat[perm[cur]][perm[cur+1]]:
                break
            cur += 1
        else:
            ans += 1

    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import itertools

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

sides = []

for _ in range(M):
    temp_a, temp_b = map(int, input().split())
    sides.append(set([temp_a, temp_b]))



#print(sides)
counter = 0
for i in itertools.permutations(range(1, N+1)):
    if i[0] != 1:
        continue

    for j in range(0,N-1):
        if set([i[j],i[j+1]]) in sides:
            continue
        else:
            break
    else:
        counter += 1
        continue
    


print(counter)

Submission status: Accepted

Solution code:
import sys
import math
import numpy as np
from collections import Counter, defaultdict, deque
import itertools

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


def S():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return map(int, input().split())


inf = float("inf")
mod = 10 ** 9 + 7

n, m = MI()
d = defaultdict(set)
for _ in range(m):
    a, b = MI()
    d[a].add(b)
    d[b].add(a)

li = list(range(2, n + 1))

ans = 0
for l in itertools.permutations(li):
    now = 1
    for i, next in enumerate(l):
        if next in d[now]:
            now = next
            if i == n - 2:
                ans += 1
        else:
            break

print(ans)

Submission status: Accepted

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

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

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

def dfs(v, visited):
    if 0 not in visited:
        return 1

    ans = 0
    for i in G[v]:
        if visited[i] == 0:
            visited[i] = 1
            ans += dfs(i, visited)
            visited[i] = 0

    return ans

print(dfs(0, visited))

Submission status: Accepted

Solution code:
import copy
n,m=map(int,input().split())
g=[set([]) for _ in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    g[a].add(b)
    g[b].add(a)

ans=0
def dfs(v,used):
    usedi=copy.deepcopy(used)
    usedi[v]=True

    nexti=g[v]
    for i in nexti:
        if(usedi[i]):
            continue
        else:
            dfs(i,usedi)

    if(usedi[1:].count(True) == n):
        global ans
        ans+=1

dfs(1,[False for _ in range(n+1)])
print(ans)

Submission status: Accepted

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

B = list()

def update(current=[1], rest=A, count = 0):
    next = list(filter(lambda x: x[0] == current[count], rest))
    if len(current) < n:
        for ne in next:
            l = copy.deepcopy(current)
            l.append(ne[1])
            nRest = list(filter(lambda x: x[0] != current[count] and x[1] != current[count] and x[1] != ne[1], rest))
            update(l, nRest, count + 1)
    else:
        B.append(current)

update()
print(len(B))

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import permutations

N, M = map(int, input().split(' '))
graph = defaultdict(set)
for _ in range(M):
    a, b = map(int, input().split(' '))
    graph[a].add(b)
    graph[b].add(a)

count = 0
for path in permutations(range(2, N + 1)):
    if path[0] not in graph[1]:
        continue

    for n1, n2 in zip(path, path[1:]):
        if n2 not in graph[n1]:
            break
    else:
        count += 1

print(count)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
def dfs(i, j):
    global cnt, vis
    if len(set(vis)) == 1:
        cnt += 1
        return None
    for k in l[j]:
        if not vis[k] == 1:
            vis[k] = 1
            dfs(i + 1, k)
            vis[k] = 0
n, m = map(int, input().split())
l = [[] for i in range(n)]
vis = [0] * n
vis[0] = 1
cnt = 0
for i in range(m):
    a, b = map(int, input().split())
    l[a - 1].append(b - 1)
    l[b - 1].append(a - 1)
dfs(0, 0)
print(cnt)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

N, M = map(int, input().split())
X = [[] for _ in range(M)]
for i in range(M):
    X[i] = list(map(int, input().split()))
permutations_list = list(itertools.permutations([i for i in range(N-1)]))

count = 0
for i in range(len(permutations_list)):
    x = np.argsort(permutations_list[i])
    if [1, x[0]+2] not in X and [x[0]+2, 1] not in X:
        count += 1
        continue
    for j in range(N-2):
        pair = [x[j]+2, x[j+1]+2]
        reverse = list(reversed(pair))
        if pair not in X and reverse not in X:
            count += 1
            break
print(len(permutations_list) -count)

Submission status: Accepted

Solution code:
import itertools

N, M = map(int, input().split())
array = [" -> ".join(input().split()) for _ in range(M)]

permutation_list = itertools.permutations([x + 1 for x in range(N)])

count = 0
flg = True
for data in permutation_list:
    # print(data)
    if data[0] != 1:
        continue
    for i in range(1, len(data)):
        param = "{} -> {}".format(data[i - 1], data[i])
        param2 = "{} -> {}".format(data[i], data[i - 1])
        if array.count(param) > 0 or array.count(param2) > 0:
            pass
            # print("あった " + param)
        else:
            # print("なかった NG")
            flg = False
            break
    if flg is False:
        flg = True
        continue
    # print(data)
    count += 1

print(count)

Submission status: Accepted

Solution code:
import itertools
import math

n, m = [int(i) for i in input().split()]
town = [[0 for _ in range(n+1)] for _ in range(n+1)]

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

lis =[i for i in range(1,n+1)]
permutations_lis = itertools.permutations(lis)

count = 0
for one_case in permutations_lis:
    if (one_case[0] == 1):
        flag = 1
    else:
        flag = 0

    for i in range(n-1):
        if(town[one_case[i]][one_case[i+1]] == 0):
            flag = 0
    if(flag == 1):
        count += 1

print(count)

Submission status: Accepted

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

# 隣接リスト
# node iとつながってるnodeはnei_L[i - 1]に入ってる
nei_L = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    nei_L[a - 1].append(b - 1)
    nei_L[b - 1].append(a - 1)

ans = 0
visited = [0] * N

def dfs(now=0):
    global visited, ans
    visited[now] = 1
    if all(visited):
        ans += 1
        # visited = [0] * N
    else:
        cand = nei_L[now]
        for c in cand:
            if not visited[c]:
                dfs(c)
    visited[now] = 0

dfs()
print(ans)

Submission status: Accepted

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

from collections import deque

d = deque([[0]]) #(頂点、長さ)
from copy import copy
ans = 0
while len(d):
    vs = d.popleft()
    for w in edge[vs[-1]]:
        if w not in vs:
            vs_copy = copy(vs)
            vs_copy.append(w)
            if len(vs_copy)==N:
                ans += 1
            else:
                d.append(vs_copy)
print(ans)