Problem:


Score : 300 points

Problem Statement

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

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

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

Here, the endpoints of a path are considered visited.  

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

Figure 1: an example of an undirected graph

The following path shown in Figure 2 satisfies the condition.

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

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

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

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

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

Constraints

2≦N≦8 

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

1≦a_i<b_i≦N 

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

Input

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

N M  
a_1 b_1  
a_2 b_2
:  
a_M b_M  

Output

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

Sample Input 1

3 3
1 2
1 3
2 3

Sample Output 1

2

The given graph is shown in the following figure:

The following two paths satisfy the condition:

Sample Input 2

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

Sample Output 2

1

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



Sample input:
3 3
1 2
1 3
2 3


Sample output:
2

Submission status: Accepted

Solution code:
def perm(k,x):
    v=[]
    for i in range(x):
        c=k%x+2
        if c not in v:
            v.append(c)
            k//=x
        else:
            return []
    return v       

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

if N==2:
    ans=1 if e[1][2] else 0
else:
    ans=0
    for k in range((N-1)**(N-1)):
        v=perm(k,N-1)
        if v and e[1][v[0]]:
            f=True
            for j in range(N-2):
                if not e[v[j]][v[j+1]]:
                    f=False
                    break
                if j==N-3:
                    ans+=1

print(ans)

Submission status: Accepted

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

adj = [[] for _ in range(N)]
for a,b in ab:
    adj[a-1].append(b-1)
    adj[b-1].append(a-1)
    

def dfs(x,s,flags):
    vlist = adj[x]
    flags = list(flags)
    flags[x] = False
    flags = tuple(flags)
    if sum(flags) == 0:
        return 1
    s = 0
    for v in vlist:    
        if flags[v]:
            s += dfs(v,s,flags)
    return s        

Flag = [True] * N
Flag[0] = False
ans = dfs(0,0,tuple(Flag))
print(ans)

Submission status: Accepted

Solution code:
import itertools

n,m=map(lambda x: int(x), input().split())

path={}
for i in range(n+1):
    path[i]=[]

for _ in range(m):
    a,b=map(lambda x: int(x), input().split())
    path[a].append(b)
    path[b].append(a)

node_list=list(itertools.permutations(range(2, n+1)))
ans=0
for node_tup in node_list:
    flag=True
    if node_tup[0] not in path[1]:
        continue
    for i in range(n-2):
        if node_tup[i+1] not in path[node_tup[i]]:
            flag=False
            break
    ans+=flag
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
Branch = [list(map(int,input().split())) for i in range(M)]
Visited = [0 for i in range(N)]
Visited[0] = 1
Glaph = [[0 for i in range(N)] for i in range(N)] 
for b in Branch:
  Glaph[b[0]-1][b[1]-1] = 1; Glaph[b[1]-1][b[0]-1] = 1
def dfs(v,N,Visited):
  flag = True
  for i in range(N):
    if Visited[i] == 0:
      flag = False
  if flag:
    return 1
  
  ret = 0
  
  for i in range(N):
    if Glaph[v][i] == False: continue
    if Visited[i]: continue    
    Visited[i] = 1    
    ret+=dfs(i,N,Visited)
    Visited[i]= 0
  return ret

print(dfs(0,N,Visited ))

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())
    a,b=a-1,b-1
    g[a].append(b)
    g[b].append(a)

ed=[0]*n
ed[0]=1
ans=[0]*n

def f(x):
    if 0 not in ed:
        ans[x]+=1
        return
    for a in g[x]:
        if ed[a]==0:
            ed[a]=1
            f(a)
            ed[a]=0
f(0)
print(sum(ans))

Submission status: Accepted

Solution code:
from itertools import permutations
import sys
#input = sys.stdin.readline
sys.setrecursionlimit(10**7)
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

adjm = [[0]*N for _ in range(N)]
for abi in ab:
    adjm[abi[0]-1][abi[1]-1] = 1
    adjm[abi[1]-1][abi[0]-1] = 1

cnt = 0
order = list(range(1, N))
for v in permutations(order):
    last = 0
    for i in v:
        if adjm[last][i] == 1:
            last = i
        else:
            break
    else:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
from sys import stdin
N = int()
memo = {}
graph = []


def dfs(e, done):
    if (1 << N) - 1 == done:
        return 1
    key = (e, done)
    if key in memo:
        return memo[key]
    ret = 0
    for s in graph[e]:
        if done >> s & 1:
            continue
        done ^= 1 << s
        ret += dfs(s, done)
        done ^= 1 << s
    memo[key] = ret
    return ret


def main():
    lines = stdin.readlines()
    global N
    N, M = map(int, lines[0].split())
    global graph
    graph = [[] for i in range(N)]
    for i in range(1, M + 1):
        a, b = map(lambda x: int(x) - 1, lines[i].split())
        # 0-based indexing
        graph[a].append(b)
        graph[b].append(a)
    print(dfs(0, 1))
    return


main()

Submission status: Accepted

Solution code:
from sys import stdin


def dfs(e, ans, done, N, graph):
    if (1 << N) - 1 == done:
        ans += 1
        return ans
    for s in graph[e]:
        if done >> s & 1:
            continue
        done ^= 1 << s
        ans = dfs(s, ans, done, N, graph)
        done ^= 1 << s
    return ans


def main():
    lines = stdin.readlines()
    N, M = map(int, lines[0].split())
    graph = [[] for i in range(N)]
    for i in range(1, M + 1):
        a, b = map(lambda x: int(x) - 1, lines[i].split())
        # 0-based indexing
        graph[a].append(b)
        graph[b].append(a)
    ans = 0
    print(dfs(0, ans, 1, N, graph))
    return


main()

Submission status: Accepted

Solution code:
from sys import stdin


def dfs(e, ans, graph, done, N):
    if sum(done) == N:
        ans += 1
        return ans
    for s in graph[e]:
        if not done[s]:
            done[s] = True
            ans = dfs(s, ans, graph, done, N)
            done[s] = False
    return ans


def main():
    lines = stdin.readlines()
    N, M = map(int, lines[0].split())
    graph = [[] for i in range(N)]
    for i in range(1, M + 1):
        a, b = map(int, lines[i].split())
        # 0-based indexing
        graph[a - 1].append(b - 1)
        graph[b - 1].append(a - 1)
    ans = 0
    done = [False] * N
    done[0] = True
    print(dfs(0, ans, graph, done, N))
    return


main()

Submission status: Accepted

Solution code:
from sys import stdin


def dfs(e, ans, graph, done, N):
    if sum(done) == N:
        ans += 1
        return ans
    for s in graph[e]:
        if not done[s]:
            done[s] = True
            ans = dfs(s, ans, graph, done, N)
            done[s] = False
    return ans


def main():
    lines = stdin.readlines()
    N, M = map(int, lines[0].split())
    graph = []
    for i in range(N):
        graph.append([])
    for i in range(1, M + 1):
        a, b = map(int, lines[i].split())
        # 0-based indexing
        graph[a - 1].append(b - 1)
        graph[b - 1].append(a - 1)
    ans = 0
    done = [False] * N
    done[0] = True
    print(dfs(0, ans, graph, done, N))
    return


main()

Submission status: Accepted

Solution code:
import itertools

n,m = map(int,input().split())
E = [list(map(int,input().split())) for i in range(m)]
G = [[] for i in range(n)]
for i in range(m):
    G[E[i][0]-1] += [E[i][1]-1]
    G[E[i][1]-1] += [E[i][0]-1]

ans = 0
for p in itertools.permutations(range(1,n)):
    if p[0] in G[0] and all([p[i] in G[p[i-1]] for i in range(1,n-1)]):
        ans += 1

print(ans)

Submission status: Accepted

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

matrix = [[0 for _ in range(N)] for _ in range(N)]

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

def func(p, l):
    '''
    count = 0
    if Pから行ける場所が探索済み:
        if 全頂点探索済み:
            count = 1
        else:
            count = 0
    else:
        foreach Pから行ける未探索頂点:
            count += func(p, l)

    '''
    count = 0
    if all(l):
        count = 1
    else:
        for np, e in enumerate(matrix[p]):
            if e == 0:
                continue
            if p == np:
                continue
            if l[np] == True:
                continue

            l[np] = True
            count += func(np, l)
            l[np] = False

    return count

l = [False] * N
l[0] = True


print(func(0, l))

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
G = {}
for _ in range(M):
    a,b = map(int,input().split())
    if a not in G:
        G[a] = []
    G[a].append(b)
    if b not in G:
        G[b] = []
    G[b].append(a)
hist = [0 for _ in range(N+1)]
stack = [1]
hist[1] = 1
cnt = 0
F = {}
while stack:
    cur = stack[-1]
    if cur not in F:
        F[cur] = G[cur][:]
        F[cur] = iter(F[cur])
    F1 = list(F[cur])
#     print("cur={},F1={}".format(cur,F1))
    if len(F1)>0:
        F[cur] = iter(F1)
        x = next(F[cur])
        if hist[x]==0:
            stack.append(x)
            hist[x] = 1
        else:
            if sum(hist)==N:
                cnt += 1
                hist[cur]=0
                del F[cur]
                stack.pop()
    else:
#         print("cur={}".format(cur))
#         print("stack={}".format(stack))
        if sum(hist)==N:
            cnt += 1
        hist[cur]=0
        del F[cur]
        stack.pop()
print(cnt)

Submission status: Accepted

Solution code:
import itertools
import collections

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

a = [list(sorted(map(int, input().split()))) for i in range(m)]
a.sort()

cnt = 0

for i in itertools.permutations(range(2, n + 1), (n - 1)):
    li = [1] + list(i)
    if sum(list(sorted(edge)) in a for edge in zip(li, li[1:])) == n - 1:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import sys
from collections import deque, defaultdict

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N, M = map(int, input().split())
        edges = defaultdict(set)
        for _ in range(M):
            a, b = map(int, input().split())
            edges[a].add(b)
            edges[b].add(a)

        deq = deque()
        deq.append((1, 1, {1}))

        ans = 0
        while deq:
            node = deq.popleft()
            node_num = node[0]
            cnt = node[1]
            already = node[2]

            if cnt == N:
                ans += 1
                continue

            already.add(node_num)

            for n in edges[node_num]:
                if n not in already:
                    deq.append((n, cnt + 1, already.copy()))

        print(ans)


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Accepted

Solution code:
from sys import stdin
mat = [[False] * 8 for _ in range(8)]
def dfs(point, visited):
        all_visited = True
        n = len(visited)
        for i in range(n):
            if visited[i] == False:
                all_visited = False
        if all_visited:
            return 1
        ans = 0
        for i in range(n):
            # print("point", point, "i", i)
            # print(visited)
            if mat[point][i] == True and visited[i] ==False:
                # print("passed")
                visited[i] = True
                ans += dfs(i, visited)
                visited[i] = False
        return ans
def main():
    n, m = list(map(int, input().split()))
    
    for _ in range(m):
        a, b = list(map(int, input().split()))
        a = a - 1
        b = b - 1
        mat[a][b] = True
        mat[b][a] = True
    # print(mat)
    v = [False] * n
    v[0] = True
    print(dfs(0, v))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import permutations
N,M=map(int,input().split())
l=[[] for _ in range(N)]
for _ in range(M):
  x,y=map(int,input().split())
  l[x-1].append(y-1)
  l[y-1].append(x-1)

res=0
for i in permutations(range(2,N+1)):
  s='1'
  for j in i:
    s+=str(j)
  ans=True
  for k in range(N-1):
    ss=int(s[k])-1
    st=int(s[k+1])-1
    if st not in l[ss]:
      ans=False
  if ans:
    res+=1
print(res)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import itertools
def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    all_per = itertools.permutations(range(2,N+1))
    # 隣接行列作成
    matrix = [[0]*N for _ in range(N)]

    for aa,bb in zip(a,b):
        matrix[aa-1][bb-1] = 1
        matrix[bb-1][aa-1] = 1
    answer = 0
    for per in all_per:
        if matrix[0][per[0]-1] == 0:
            continue
        for i in range(N-2):
            if matrix[per[i]-1][per[i+1]-1] == 0:
                break
        else:
            answer += 1

    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]"
    b = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, M, a, b)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a_and_b = [list(map(int, input().split())) for _ in range(m)]
point = [[] for _ in range(n)]
reached = [False for _ in range(n)]
answer = 0
for i in range(m):
    for j in range(n):
        if a_and_b[i][0] == j+1:
            point[j].append(a_and_b[i][1])
        if a_and_b[i][1] == j+1:
            point[j].append(a_and_b[i][0])


def dfs(start_point=0):
    global answer
    if not (False in reached):
        answer += 1
    for k in point[start_point]:
        if reached[k-1] is False:
            reached[k-1] = True
            dfs(start_point=k-1)
            reached[k-1] = False


reached[0] = True
dfs(start_point=0)
print(answer)

Submission status: Accepted

Solution code:
def slove():
    import sys
    import bisect
    import collections
    import copy
    import fractions
    import heapq
    input = sys.stdin.readline
    n, m = list(map(int, input().rstrip('\n').split()))
    d = collections.defaultdict(list)
    for i in range(m):
        a, b = list(map(int, input().rstrip('\n').split()))
        d[a-1] += [b-1]
        d[b-1] += [a-1]

    ql = collections.deque()
    ql.append([0, [0]])
    cnt = 0
    while True:
        if len(ql) != 0:
            qp, ls = ql.popleft()
            for v in d[qp]:
                if v not in ls:
                    tls = copy.deepcopy(ls)
                    tls.append(v)
                    if len(tls) < n:
                        ql.append([v, tls])
                    else:
                        cnt += 1
        else:
            break
    print(cnt)


if __name__ == '__main__':
    slove()

Submission status: Accepted

Solution code:
# Python program to print all paths from a source to destination. 
cnt=0 
ans=0 
from collections import defaultdict 
from collections import Counter 
def check(arr): 
    c=Counter(arr)
    for i in range(n):
        if c[i]!=1:
            return 0 
    return 1 
#This class represents a directed graph 
# using adjacency list representation 
class Graph: 

	def __init__(self,vertices): 
		#No. of vertices 
		self.V= vertices 
		
		# default dictionary to store graph 
		self.graph = defaultdict(list) 

	# function to add an edge to graph 
	def addEdge(self,u,v): 
		self.graph[u].append(v) 
	def printAllPathsUtil(self, u, d, visited, path):
	   
		# Mark the current node as visited and store in path 
		visited[u]= True
		path.append(u) 
		global ans 
		# If current vertex is same as destination, then print 
		# current path[] 
		if u ==d: 
		   # print(path)
		    if check(path): 
		        ans+=1 
		else: 
			# If current vertex is not destination 
			#Recur for all the vertices adjacent to this vertex 
			for i in self.graph[u]: 
				if visited[i]==False: 
					self.printAllPathsUtil(i, d, visited, path) 
					
		# Remove current vertex from path[] and mark it as unvisited 
		path.pop() 
		visited[u]= False


	# Prints all paths from 's' to 'd' 
	def printAllPaths(self,s, d): 

		# Mark all the vertices as not visited 
		visited =[False]*(self.V) 

		# Create an array to store paths 
		path = [] 

		# Call the recursive helper function to print all paths 
		self.printAllPathsUtil(s, d,visited, path) 



# Create a graph given in the above diagram 
n,m=map(int,input().split())
g = Graph(n)
for i in range(m): 
    a,b=map(int,input().split())
    g.addEdge(a-1,b-1)
    g.addEdge(b-1,a-1)
s = 2 ; d = 3
s=0 
for d in range(0,n): 
    g.printAllPaths(s, d) 
print(ans)

Submission status: Accepted

Solution code:
class Graph:
    def __init__(self):
        n, m = map(int, input().split())

        self.adj = [[] for _ in range(n)]
        for _ in range(m):
            a, b = map(int, input().split())
            a -= 1
            b -= 1
            self.adj[a].append(b)
            self.adj[b].append(a)

        self.cnt = 0
        self.depth = 0
        self.ds = [-1] * n

    def solve(self, u):
        self.ds[u] = self.depth
        if self.ds.count(-1) == 0:
            self.cnt += 1
            return

        self.depth += 1
        for v in self.adj[u]:
            if self.ds[v] == -1:
                self.solve(v)
                self.ds[v] = -1
        self.depth -= 1


def main():
    graph = Graph()
    graph.solve(0)
    print(graph.cnt)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class Graph:
    def __init__(self, n, adj):
        self.adj = adj
        self.cnt = 0
        self.depth = 0
        self.ds = [-1] * n

    def solve(self, u):
        self.ds[u] = self.depth
        if self.ds.count(-1) == 0:
            self.cnt += 1
            return

        self.depth += 1
        for v in self.adj[u]:
            if self.ds[v] == -1:
                self.solve(v)
                self.ds[v] = -1
        self.depth -= 1


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

    graph = Graph(n, adj)
    graph.solve(0)
    print(graph.cnt)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from copy import deepcopy

cnt = 0
depth = 0


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

    def f(u, d):
        global cnt, depth
        cp = deepcopy(d)
        cp[u] = depth
        if cp.count(-1) == 0:
            cnt += 1
        else:
            vs = adj[u]
            depth += 1
            for v in vs:
                if cp[v] == -1:
                    f(v, cp)
            depth -= 1

    f(0, [-1] * n)

    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import permutations

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

cnt=0
for i in permutations(range(1,n)):
    if i[0] in tree[0]:
        t_cnt=1
        for j in range(1,len(i)):
            if i[j] in tree[i[j-1]]:
                t_cnt+=1
            else:
                break
        if t_cnt==n-1:
            cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
def dfs(curr, visit_state, adj_list, count, num_vertex):
    if count == num_vertex:
        return 1
    if all(visit_state[i] for i in adj_list[curr]) and count != num_vertex:
        return 0
    result = 0
    for nb in adj_list[curr]:
        if not visit_state[nb]:
            visit_state[nb] = True
            result += dfs(nb, visit_state, adj_list, count + 1, num_vertex)
            visit_state[nb] = False
    return result


n, m = map(int, input().split())
adj = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    adj[a - 1].append(b - 1)
    adj[b - 1].append(a - 1)
visited = [False] * n
visited[0] = True
print(dfs(0, visited, adj, 1, n))

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
c=[[0]*N for i in range(N)]
for a,b in AB:
    c[a-1][b-1]=c[b-1][a-1]=1
from itertools import permutations
r=0
for n in permutations(range(1,N)):
    n=[0]+list(n)
    x=1
    for i in range(N-1):
        if not c[n[i]][n[i+1]]:
            x=0
    r+=x
print(r)

Submission status: Accepted

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

Graph = [[0]*N for _ in range(N)]
for i in range(M):
  a,b = map(int,input().split())
  Graph[a-1][b-1] = 1 
  Graph[b-1][a-1] = 1
  
A = []
for i in range(1,N): A.append(i)

ans = 0
Comb = list(itertools.permutations(A))
for i in range(len(Comb)):
  tmp = list(Comb[i])
  #print(tmp)
  judge = 1
  for j in range(len(tmp)):
    if(j == 0): judge = judge*Graph[0][tmp[j]]
    else: judge = judge*Graph[tmp[j-1]][tmp[j]]
  if(judge == 1): ans += 1
 
print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(m)]
p=list(itertools.permutations(list(range(2,n+1))))
ans=0
for i in p:
    tmp=1
    for j in range(n-1):
        if [tmp,i[j]] in l or [i[j],tmp] in l:
            tmp=i[j]
        else:break
        if j==n-2:ans+=1
print(ans)

Submission status: Accepted

Solution code:
import copy

N,M = map(int,input().split())
t_dict = dict()
for _ in range(M):
    a,b = map(int,input().split())
    try:
        t_dict[a] += [b]
    except KeyError:
        t_dict[a] = [b]
        
    try:
        t_dict[b] += [a]
    except KeyError:
        t_dict[b] = [a]
        

origin = [1]
new_origin = []
for one in t_dict[1]:
    new_origin.append(origin+[one])

for _ in range(N-2):
    origin = copy.deepcopy(new_origin)
    new_origin = []
    for one in origin:
        for two in t_dict[one[-1]]:
            if two  in one :
                pass
            else:
                new_origin.append(one+[two])
                
print(len(new_origin))

Submission status: Accepted

Solution code:
from collections import defaultdict


def c():
    n, m = map(int, input().split())
    graph = defaultdict(list)
    for i in range(m):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
    stack = []
    count = 0

    stack.append((1, set()))

    while stack:
        val, visited = stack.pop()
        visited.add(val)
        if len(visited) == n:
            count += 1
            continue

        for g in graph[val]:
            if g not in visited:
                stack.append((g, set(visited)))

    print(count)


if __name__ == '__main__':
    c()

Submission status: Accepted

Solution code:
import itertools

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

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

per = list(itertools.permutations(range(N)))

count = 0

for x in per:
    if x[0] != 0:
        continue
    det = 0
    for k in range(N-1):
        if x[k+1] in con[x[k]]:
            continue
        else:
            det = -1
            break
    if det == 0:
        count += 1

print(count)

Submission status: Accepted

Solution code:
def dfs(visited, s):
    visited = visited[:]  # このような渡し方をすることで、もしそのルートが不正解だった時に分岐まで戻ることができる
    global ans
    visited[s] = True
    for t in graph[s]:  # startとtarget
        if not visited[t]:  # 未訪問なら
            dfs(visited, t)

    # 自身から伸びているノードが全て訪問済みなら以下の処理をする
    if all(visited):
        ans += 1


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

graph = [[] for _ in range(N)]
visited = [False]*N

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

ans = 0
dfs(visited, 0)

print(ans)

Submission status: Accepted

Solution code:
def dfs(visited, s):
    visited = visited[:]
    global ans
    visited[s] = True
    for t in graph[s]:
        if not visited[t]:
            dfs(visited, t)
    if all(visited):
        ans += 1


N, M = map(int, input().split())  # N頂点, M辺存在する

graph = [[] for _ in range(N)]
visited = [False] * N

for _ in range(M):  # M辺を受け取る
    a, b = map(lambda x: int(x)-1, input().split())
    graph[a].append(b)
    graph[b].append(a)


ans = 0
dfs(visited, 0)

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
lis=[[0 for i in range(n)] for _ in range(n)]
for i in range(m):
	x,y=map(int,input().split())
	lis[x-1][y-1]=1
	lis[y-1][x-1]=1
s=""
k=[]
import itertools
for i in range(n):
	s+=str(i)
for i in itertools.permutations(s):
	k.append(i)
ans=0
for i in range(len(k)):
	if k[i][0]!="0":
		continue
	for j in range(n-1):
		if lis[int(k[i][j])][int(k[i][j+1])]==0:
			break
		elif j==n-2:
			ans+=1
print(ans)

Submission status: Accepted

Solution code:
def dfs(visited, s):  #
    global ans
    visited[s] = True
    for t in graph[s]:
        if not visited[t]:
            dfs(visited[:], t)
    if all(visited):
        ans += 1


N, M = map(int, input().split())  # N頂点, M辺存在する

graph = [[] for _ in range(N)]
visited = [False] * N

for _ in range(M):  # M辺を受け取る
    a, b = map(lambda x: int(x)-1, input().split())
    graph[a].append(b)
    graph[b].append(a)


ans = 0
dfs(visited, 0)

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
N, M = map(int, input().split())
T=[[]*N for _ in range(N)]
for _ in range(M):
  i ,j = map(int,input().split())
  T[i-1].append(j-1)
  T[j-1].append(i-1)

def main():
  ans = 0
  for p in permutations(range(1,N)): 
    c=0
    for n in p:
      if n not in T[c]:
        break
      c=n
    else:
      ans += 1
  print(ans)

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import itertools

N,M=map(int,input().split())
a=[0]*N
b=[0]*N
C=[[0 for _ in range(N+1)] for _ in range(N+1)]

for i in range(M):
  a,b=map(int,input().split())
  C[a][b]=1
  C[b][a]=1
#print(C)
  
L=[i for i in range(1,N+1)]
#print(L)
ans=0
for v in itertools.permutations(L,len(L)):
  sw=1
  #print(v)
  if v[0]!=1:
    continue
  for i in range(len(v)-1):
    if C[v[i]][v[i+1]]==0:
      sw=0
      break
  if sw==1:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
def main():
    N, M = (int(i) for i in input().split())
    G = [set() for _ in range(N+1)]
    for m in range(M):
        a, b = (int(i) for i in input().split())
        G[a].add(b)
        G[b].add(a)
    
    from itertools import permutations
    trial_path = (p for p in permutations(range(2,N+1),N-1))

    def exist_path(st,path):
        for p in path:
            if p in G[st]: st = p
            else: return False
        else: 
            return True

    ans = 0
    for path in trial_path:
        if exist_path(1,path):
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M = tuple(map(int,input().split()))
from collections import defaultdict
graph = defaultdict(list)
for i in range(M):
  a,b = tuple(map(int,input().split()))
  graph[a].append(b)
  graph[b].append(a)
  
# pathを運んで，その中で
queue = [(1,set())]
res = 0
while queue:
  now,prevs = queue.pop()
  
  if len(prevs) == N-1:
      res += 1
      continue
  for next_node in graph[now]:
    #print("{}: {}->{} {}".format(prevs,now,next_node,"o" if next_node not in prevs else "x"))
    if next_node not in prevs:
      queue.append((next_node, prevs|{now}))
print(res)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ns = lambda : stdin.readline().rstrip()
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))

sys.setrecursionlimit(10**6)

def main():
  n, m = na()
  graph = [[] for _ in range(n + 1)]
  for _ in range(m):
    a, b = na()
    graph[a] += [b]
    graph[b] += [a]
  
  def dfs(e, reach):
    if all(reach):
      return True

    ret = 0
    for e in graph[e]:
      if reach[e - 1]:
        continue
      reach[e - 1] = True
      ret += dfs(e, reach)
      reach[e - 1] = False
    return ret

  reach = [False] * n
  reach[0] = True
  print(dfs(1, reach))

main()

Submission status: Accepted

Solution code:
def bfs(u):
  if used.count(True) == N:
    res[0] += 1
    return
  for v in adj[u]:
    if used[v]:
      continue
    used[v] = True
    bfs(v)
    used[v] = False

N, M = map(int, input().split())
adj = [[] for i in range(N)]
for i in range(M):
  u, v = map(lambda x: int(x)-1, input().split())
  adj[u].append(v)
  adj[v].append(u)

used = [False for i in range(N)]
used[0] = True
res = [0]
bfs(0)

print(res[0])

Submission status: Accepted

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

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

ver = [[] for _ in range(N)]
# 頂点xから移動できる頂点を格納する

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

ans = 0

for i in permutations(range(1, N)):
    here = 0
    for j in i:
        if j not in ver[here]:
            break
        here = j
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
n, m = map(int, input().split())
d = [[] for _ in range(n)]
ans = 0
for i in range(m):
  a, b = map(int, input().split())
  d[a - 1].append(b - 1)
  d[b - 1].append(a - 1)
l = permutations(range(1, n))
for i in l:
  pre = 0
  c = 0
  for j in i:
    if not j in d[pre]:
      break
    c += 1
    pre = j
  if c == n-1:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
def dfs(v,N,visited):
  if sum(visited) == len(visited):
    return 1
  
  ret =0
  for i in range(N):
    if graph[v][i] == 0:
      continue
    if visited[i]:
      continue
    
    visited[i] = 1
    ret += dfs(i,N,visited)
    visited[i] = 0
    
  return ret


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

for mi in range(m):
  a,b = map(int,input().split())
  graph[a-1][b-1] = 1
  graph[b-1][a-1] = 1
  
visited = [0]*n
visited[0]= 1
print(dfs(0,n,visited))