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:
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())
r=[False]*n
r[0]=True
c=0
def sol(x):
    global c
    if all(r):c+=1;
    else:
        for i in range(m):
            if a[i]==x and r[b[i]-1]==False:
                r[b[i]-1]=True
                sol(b[i])
                r[b[i]-1]=False
            if b[i]==x and r[a[i]-1]==False:
                r[a[i]-1]=True
                sol(a[i])
                r[a[i]-1]=False
sol(1)
print(c)

Submission status: Accepted

Solution code:
def dfs(v, N, visited, ret, route):
    if sum(visited) == N:
        return ret + 1
    
    visitable = []
    for pair in route:
        if v in pair:
            if visited[pair[0]] == 0:
                visitable.append(pair[0])
            elif visited[pair[1]] == 0:
                visitable.append(pair[1])
    
    for v in visitable:
        visited[v] = 1
        ret = dfs(v, N, visited, ret, route)
        visited[v] = 0
    
    return ret

N, M = map(int, input().split())
route = []
for i in range(M):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    route.append([a, b])
visited = [0] * N
visited[0] = 1
ret = dfs(0, N, visited, 0, route)
print(ret)

Submission status: Accepted

Solution code:
import sys
import copy

sys.setrecursionlimit(1000)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def LIST(): return [int(x) for x in input().split()]
MOD = 10**9 + 7

N, M = LIST()

A = [[0]*(N+1) for _ in range(N+1)]

for _ in range(M):
    a, b = LIST()
    A[a][b] = A[b][a] = 1



def check(current, tovisit):
    if tovisit == []:
        return 1
    
    count = 0

    for i in tovisit:
        if A[current][i] == 1:
            tmp = copy.deepcopy(tovisit)
            tmp.remove(i)
            count += check(i, tmp)

    return count

print(check(1, list(range(2, N+1))))

Submission status: Accepted

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

C=[[] for i in range(nn)]
C.insert(0,"niku")

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

ans=0    

def tansa(n,path,app):
    new_path=path[:]
    new_path.append(app)
    #print(str(n)+"+",new_path,path)
    if len(new_path)==nn:
        global ans
        ans+=1
        return 1

    for num in C[n]:
        if not num in new_path:
            tansa(num,new_path,num)

            
tansa(1,[],1)

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b = LI()
    a -= 2
    b -= 2
    a %= 13
    b %= 13
    if a > b:
        print("Alice")
    elif a < b:
        print("Bob")
    else:
        print("Draw")
    return

#B
def B():
    n, m = LI()
    a = SR(n)
    b = SR(m)
    if a == b:
        print("Yes")
        return
    for y in range(n - m):
        for x in range(n - m):
            if a[y][x] == b[0][0]:
                flg = 0
                for yi in range(m):
                    for xi in range(m):
                        if b[yi][xi] == a[y + yi][x + xi]:
                            continue
                        flg = 1
                        break
                    if flg:
                        break
                if flg:
                    continue
                print("Yes")
                return
    print("No")
    return

#C
def C():
    n, m = LI()
    edg = [[] for i in range(n)]
    for _ in range(m):
        a, b = LI_()
        edg[a].append(b)
        edg[b].append(a)
    def dfs(i, c):
        res = 0
        c[i] = False
        if not (True in c):
            c[i] = True
            return 1
        for e in edg[i]:
            if c[e]:
                res += dfs(e, c)
        c[i] = True
        return res
    print(dfs(0, [True] * n))
    return

#D
def D():
    return

#Solve
if __name__ == '__main__':
    C()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b = LI()
    a -= 2
    b -= 2
    a %= 13
    b %= 13
    if a > b:
        print("Alice")
    elif a < b:
        print("Bob")
    else:
        print("Draw")
    return

#B
def B():
    n, m = LI()
    a = SR(n)
    b = SR(m)
    if a == b:
        print("Yes")
        return
    for y in range(n - m):
        for x in range(n - m):
            if a[y][x] == b[0][0]:
                flg = 0
                for yi in range(m):
                    for xi in range(m):
                        if b[yi][xi] == a[y + yi][x + xi]:
                            continue
                        flg = 1
                        break
                    if flg:
                        break
                if flg:
                    continue
                print("Yes")
                return
    print("No")
    return

#C
def C():
    n, m = LI()
    edg = [[] for i in range(n)]
    for _ in range(m):
        a, b = LI_()
        edg[a].append(b)
        edg[b].append(a)
    def dfs(i, c):
        res = 0
        c[i] = False
        if not (True in c):
            return 1
        for e in edg[i]:
            if c[e]:
                c[e] = False
                res += dfs(e, c)
                c[e] = True
        return res
    print(dfs(0, [True] * n))
    return

#D
def D():
    return

#Solve
if __name__ == '__main__':
    C()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
grp = []
for i in range(0, N):
	grp.append([])
for i in range(0, M):
	A, B = map(lambda v: int(v)-1, input().split())
	grp[A].append(B)
	grp[B].append(A)
memo = []
for i in range(0, N):
	memo.append(True)
memo[0] = False
cnt = 0
stack = [[0, memo]]
while stack != []:
	now = stack.pop(-1)
	if True not in now[1]:
		cnt += 1
	else:
		for i in range(0, len(grp[now[0]])):
			next = grp[now[0]][i]
			if now[1][next]:
				nextmemo = now[1][:next] + [False]
				if next != N-1:
					nextmemo = nextmemo + now[1][next+1:]
				stack.append([next, nextmemo])
print(cnt)

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
lis = [0 for i in range(m)]
for i in range(m):
    lis[i] = list(map(int,input().split()))
    
seen = []
count = 0
visited = [0 for i in range(n)]
def route(x=1):
    visited[x-1] = 1
    if [1]*n == visited:
        global count
        count +=1
        return
    for i in range(m):
        if lis[i][0] == x and visited[lis[i][1]-1] == 0:
            route(lis[i][1])
            visited[lis[i][1]-1] = 0
        elif lis[i][1] == x and visited[lis[i][0]-1] == 0:
            route(lis[i][0])
            visited[lis[i][0]-1] = 0
    return
            
        
route(1)
print(count)

Submission status: Accepted

Solution code:
#### import ####
import sys
sys.setrecursionlimit(10**7)
import math
from collections import defaultdict

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

N,M = II()
a,b = Line(M)

can_visit = defaultdict(list)
for i in range(M):
  can_visit[a[i]-1].append(b[i]-1)
  can_visit[b[i]-1].append(a[i]-1)
from itertools import permutations
road = list(permutations([i for i in range(N)]))
counter = 0
for r in road:
  if r[0]!=0:
    continue
  temp = 0
  check_visited = [False]*N
  check_visited[0] = True
  for i in r[1:]:
    if (i in can_visit[temp]) and (check_visited[i]==False):
      temp = i
      check_visited[i] = True
      if check_visited == [True]*N:
        counter += 1
        break
    else:
      break
print(counter)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys

def solve(N,M,E):
    def dfs(v, visited = set()):
        nonlocal cnt
        if len(visited) + 1 == N:
            cnt += 1
        for u in E[v]:
            if not u in visited:
                dfs(u, visited | {v})

    stack = [1]
    cnt = 0
    dfs(1)
    print(cnt)

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ls = [[int(x) for x in input().split()] for _ in range(m)]
can = [int(x) for x in range(2,n+1)]

import itertools
ans = 0 
for ls_can in list(itertools.permutations(can)):
    ls_can = [1]+list(ls_can)
    flg = 0
    for i in range(n-1):
        if [ls_can[i],ls_can[i+1]] in ls or [ls_can[i+1],ls_can[i]] in ls :
            flg +=1
        else:
            break
        if flg == n-1:
            ans +=1
print(ans)

Submission status: Accepted

Solution code:
import math
import itertools

INF = 10**9+7
PRIME_NUM = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]

def main():
	n,m = map(int,input().split())
	ab = []
	for i in range(m):
		ab.append(list(map(int,input().split())))
	link = []
	for i in range(n+1):
		link.append([])
	for i in ab:
		link[i[0]].append(i[1])
		link[i[1]].append(i[0])
	tmp = [i for i in range(2,n+1)]
	ans=0
	for i in itertools.permutations(tmp):
		flag =  True
		array = [1] + list(i)
		for j in range(0,n-1):
			if(link[array[j]].count(array[j+1])==0): flag = False
		if flag:
			ans+=1
	print(ans)

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

ans = 0
def calc(G, E, s):
    global ans
    E.append(s)
    for v in G[s]:
        if v in E:
            continue
        if len(E) == N - 1 and v not in E:
            ans += 1
            return
        calc(G, E, v)
        E.remove(v)

calc(G, [], 0)
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
pat = [[int(i) for i in input().split()] for _ in range(M)]
Graph = [[0 for i in range(N)] for _ in range(N)]
for i,j in pat:
    Graph[i-1][j-1] = 1
    Graph[j-1][i-1] = 1

def dfs(v,N,visit_list):

    all_visit = True

    for i in range(N):
        if visit_list[i] == False:
            all_visit = False
    
    if all_visit:
        return 1

    ret = 0

    for k in range(N):
        if Graph[v][k] == False:
            continue
        if visit_list[k] :
            continue
        
        visit_list[k] = True
        ret += dfs(k,N,visit_list)
        visit_list[k] = False
    return ret

visit_list = [False for i in range(N)]
visit_list[0] = True
print(dfs(0,N,visit_list))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4100000)

from itertools import permutations


def resolve():
    N_vertex, M_edge = [int(x) for x in sys.stdin.readline().split()]
    edge_set = set([
        tuple(int(x) for x in sys.stdin.readline().split())
        for _ in range(M_edge)
    ])
    # print(edge_set)

    count = 0
    for p in permutations(range(1, N_vertex + 1)):
        # print(p)
        if p[0] != 1:
            continue
        is_broken = False
        for i in range(N_vertex - 1):
            if (p[i], p[i + 1]) in edge_set or (p[i + 1], p[i]) in edge_set:
                pass
            else:
                is_broken = True
                break
        if not is_broken:
            count += 1

    print(count)


if __name__ == "__main__":
    resolve()

# AtCoder Unit Test で自動生成できる, 最後のunittest.main は消す
# python -m unittest template/template.py で実行できる
# pypy3 -m unittest template/template.py で実行できる

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 3
1 2
1 3
2 3"""
        output = """2"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """7 7
1 3
2 7
3 4
4 5
4 6
5 6
6 7"""
        output = """1"""
        self.assertIO(input, output)

Submission status: Accepted

Solution code:
n, m = map(int, input().split(' '))
graph = []
for i in range(n):
    graph.append([0] * n)
for i in range(m):
    a, b = map(int, input().split(' '))
    graph[a-1][b-1] = 1
    graph[b-1][a-1] = 1


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

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

    if all_visited:
        return 1

    ret = 0

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

    return ret

def main():
    visited = []
    for i in range(n):
        visited.append(0)
    visited[0] =1
    print((dfs(0,n,visited)))



if __name__ == '__main__':
    main()

Submission status: Accepted

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

import sys
sys.setrecursionlimit(10000000)
from itertools import permutations

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)
s = [i for i in range(n)]
t = list(permutations(s))
ans = 0
for i in t:
    if i[0] == 0:
        for j in range(n-1):
            if i[j+1] not in G[i[j]]:
                break
        else:
            ans += 1
print(ans)

Submission status: Accepted

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

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

def bfs(cur, l) :
    if all(visited) :
        return 1
        
    ret = 0
    for nex in vec[cur] :
        if not visited[nex] :
            visited[nex] = True
            ret += bfs(nex, l + 1)
            visited[nex] = False
            
    return ret

visited[0] = True    
print(bfs(0, 0))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    conn = [[] * N for _ in range(N)]
    for i in range(M):
        conn[a[i] - 1].append(b[i] - 1)
        conn[b[i] - 1].append(a[i] - 1)
    def dfs(idx, visited):
        last = True
        for v in visited:
            if not v:
                last = False
                break
        if last:
            return 1
        ret = 0
        for nex in conn[idx]:
            if not visited[nex]:
                visited[nex] = True
                ret += dfs(nex, visited)
                visited[nex] = False
        return ret
    visited = [False] * N
    visited[0] = True
    count = dfs(0, visited)
    print(count)
    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())
lis = []
path = ["1"]

for i in range(M):

    a,b = map(int,input().split())
    lis.append([a,b])

for i in range(N-1):

    i += 1

    npath = []

    for p in path:


        for j in lis:

            if j[0] == int(p[-1]) and str(j[1]) not in p:

                npath.append(p + str(j[1]))

            if j[1] == int(p[-1]) and str(j[0]) not in p:

                npath.append(p + str(j[0]))

    path = npath.copy()


print (len(path))

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
inp=[list(map(int,input().split())) for _ in range(M)]
g=[[] for _ in range(N)]
[g[a-1].append(b-1) for a,b in inp]
[g[b-1].append(a-1) for a,b in inp]
 
from itertools import permutations
seq=[i for i in range(N)]
test=list(permutations(seq))
cnt=0
for t in test:
    if t[0]==0:
        for i in range(N-1):
            if t[i+1] not in g[t[i]]:
                break
        else:
            cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
import itertools

b_lis = []
j_lis = []
N,M = map(int,input().split())
for i in range(M):
    b_lis.append(list(map(int,input().split())))
    
n_lis =list(range(2,N+1))
#print(n_lis)
count = 0
for i in itertools.permutations(n_lis):
    frag = 1
    #print(i)
    l = [1]
    l.extend(i)
    
    for k in range(N-1):
        if [l[k],l[k+1]] in b_lis or [l[k+1],l[k]] in b_lis:
            pass
            #print(k,b_lis,[l[k+1],l[k]])
        else:
            frag = 0
            break
    if frag == 1:
        count += 1
        #print(l)

print(count)

Submission status: Accepted

Solution code:
import math
from collections import defaultdict
import itertools
def input_as_int():
    return tuple(map(int,input().split()))

N,M  = input_as_int()

path = defaultdict(lambda  :defaultdict(lambda :False))
for i in range(M):
    a,b = input_as_int()
    path[a][b] = path[b][a] = True

ans = 0
roots = itertools.permutations(list(range(2,N+1)))
for root in roots:
    fr = 1
    flag = True
    for to in root:
        if path[fr][to]:
            fr = to
        else:
            flag = False
            break
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

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

d = [[False for i in range(N)] for i in range(N)]
visited = [False] * N

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

def dfs(now, depth):
    if visited[now]:
        return 0
    if depth == N - 1:
        return 1
    
    ret = 0
    visited[now] = True

    for i in range(N):
        if d[now][i]:
            ret += dfs(i, depth + 1)
    
    visited[now] = False

    return ret

print(dfs(0,0))

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
C = [[] for i in range(N)]
for i in range(M):
  a,b = map(int, input().split())
  a -= 1
  b -= 1
  C[a].append(b)
  C[b].append(a)
visited = [0]*N
ans = 0
def dfs(x):
  global ans
  visited[x] = 1  
  if all(visited):
    ans += 1
    return
  for i in C[x]:
    if visited[i] == 0:
      dfs(i)
      visited[i] = 0
  return
dfs(0)
print(ans)

Submission status: Accepted

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

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

s = [0]
p = 0
cnt = 0
h = -1
while True:
    if 1 in g[p][h+1:]:
        q = g[p].index(1, h+1)
        if q not in s:
            p = q
            h = -1
            s.append(p)
        else:
            h = q
    else:
        if len(s) == n:
            cnt += 1
        elif len(s) == 1:
            break
        h = p
        s.pop()
        p = s[-1]

print(cnt)

Submission status: Accepted

Solution code:
import bisect
import heapq
import itertools
import math
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = list(map(int, sys.stdin.readline().split()))
A, B = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(M)]))

graph = np.zeros((N, N), dtype=bool)
for a, b in zip(A, B):
    graph[a - 1][b - 1] = True
    graph[b - 1][a - 1] = True

cnt = 0
for order in itertools.permutations(range(1, N)):
    ok = graph[0][order[0]]
    for v, u in zip(order[:-1], order[1:]):
        ok &= graph[v][u]
    cnt += ok
print(cnt)

Submission status: Accepted

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

g = [[] for _ in range(N)]
for a, b in AB:
	a, b = a - 1, b - 1
	g[a] += [b]
	g[b] += [a]

def dfs(v, visited):
	#print(visited)
	if v in visited:
		return False
	if N - 1 == len(visited):
		return True
	count = 0
	for n in g[v]:
		count += dfs(n, visited | {v})
	return count

print(dfs(0, set()))

Submission status: Accepted

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

v = []

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

conn = []
for _ in range(N):
    conn.append([False] * N)

visited = [False] * N

for start, end in v:
    conn[start][end] = conn[end][start] = True

def dfs(now, depth):
    if visited[now]:
        return 0
    if depth == N - 1:
        return 1

    visited[now] = True
    ret = 0

    for i in range(N):
        if conn[now][i]:
            ret += dfs(i, depth + 1)
    
    visited[now] = False

    return ret

print(dfs(0,0))

Submission status: Accepted

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

def ok(l1, now, next):
    # print([l1])
    # print([now, next])
    l=l1[:]
    count=0
    if [now,next] in path or [next, now] in path:
        l.remove(next)
        if len(l)==0:
            return 1
        for i in range(len(l)):
            count+=ok(l, next, l[i])
        return count
    else:
        return 0

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

now=1
tmp=li[:]
count=0
for i in range(len(tmp)):
    count+=ok(tmp, now, tmp[i])
print(count)

Submission status: Accepted

Solution code:
# 頂点および辺の数を入力
N, M = map(int, input().split())
# 辺のリストを作成
list_edge = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    list_edge[a].append(b)
    list_edge[b].append(a)

# パスの数を返す関数を定義
def count_path(node, path, list_edge, N):
    # パスの数を初期化
    count = 0
    # 全ての頂点を訪問した場合、、
    if len(path) == N:
        # パスの数に1を加える
        count += 1
    # 全ての頂点を訪問していない場合、、
    else:
        # 現在の頂点から訪問できる各頂点について、、
        for next_node in list_edge[node]:
            # その頂点にまだ訪問していない場合、、
            if next_node not in path:
                # 再帰
                count += count_path(next_node, path + [next_node], list_edge, N)
    # パスの本数を返す
    return count
# パスの本数を出力する
print(count_path(1, [1], list_edge, N))

Submission status: Accepted

Solution code:
# 頂点および辺の数を入力
N, M = map(int, input().split())
# 辺のリストを作成
list_edge = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    list_edge[a].append(b)
    list_edge[b].append(a)
# パス（リスト）のリストを初期化
list_path = [[1]]
# パスが存在する、かつパスの長さが頂点の数未満である場合に繰り返し
while list_path != [] and len(list_path[0]) < N:
    # パスのリストから先頭のパスを取り出す
    path = list_path.pop(0)
    # パスの最後尾の頂点から訪問可能な頂点について、、
    for node in list_edge[path[-1]]:
        # その頂点にまだ訪問していない場合、、
        if node not in path:
            # パスのリストに新たなパスを加える
            list_path.append(path + [node])
# パスの数を出力する
print(len(list_path))

Submission status: Accepted

Solution code:
import itertools

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

ans = 0
for i in itertools.permutations(range(n), n):
    if i[0] == 0:
        flag = True
        for j in range(n-1):
            if not i[j+1] in path[i[j]]:
                flag = False
        if flag:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools

n, m = map(int, input().split())
path = [[False] * n for _ 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):
    if i[0] == 0:
        for j in range(n):
            if j == n-1:
                ans += 1
                break

            if not path[i[j]][i[j+1]]:
                break
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
if M == 0:
    print(0)
else:
    l = [[0 for _ in range(N)] for _ in range(N)]
    for _ in range(M):
        a,b = map(int,input().split())
        l[a-1][b-1] = 1
        l[b-1][a-1] = 1
    g = 0
    def dfs(a,route):
        global g
        if len(route) == N:g += 1
        else:
            for i in range(N):
                if a == i:pass
                else:
                    if l[a][i] == 1 and (not i in route):
                        dfs(i,route+[i])
    dfs(0,[0])
print(g)

Submission status: Accepted

Solution code:
def DFS(n):
    global ans
    stack.append(n)
    for i in range(M):
        if graf[i][0] ==n:
            if graf[i][1] not in stack:DFS(graf[i][1])
        if graf[i][1]==n:
            if graf[i][0] not in stack:DFS(graf[i][0])
    if len(stack)==N:ans+=1
    stack.pop()

N,M=map(int,input().split())
graf,stack,ans=[],[],0
for _ in range(M):
    graf.append(list(map(int,input().split())))
DFS(1)
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
c=[[] for i in range(n)]
for i in range(m):
	a,b=map(int,input().split())
	c[a-1].append(b-1)
	c[b-1].append(a-1)
cnt=[0]
def dfs(z,s):
	z[s]=1
	if sum(z)==n:
		cnt[0]+=1
	else:
		for i in c[s]:
			if z[i]==0:
				dfs(z[:i]+[1]+z[i+1:],i)
dfs([0]*n,0)
print(cnt[0])

Submission status: Accepted

Solution code:
from itertools import permutations
N,M = map(int,input().split())
ab = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]
c = permutations(range(N)[1:])
ans = 0
for per in c:
    per = [0] + list(per)
    flag = True
    for i in range(N-1):
        p1 = min(per[i],per[i+1])
        p2 = max(per[i],per[i+1])
        if (p1,p2) in ab:
            continue
        else:
            flag=False
    if flag:
        ans+=1
print(ans)

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

ans = 0
def dfs(cur, rem):
    global ans
    if len(rem) == 0:
        ans += 1
        return
    for cand in G[cur]:
        if cand in rem:
            i = rem.index(cand)
            dfs(cand, rem[:i] + rem[i+1:])

dfs(0, list(range(1, N)))

print(ans)