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())
ab=[list(map(int, input().split())) for _ in range(m)]
graph=[[False for _ in range(n)] for _ in range(n)]
visited=[False for _ in range(n)]
visited[0]=True

for x in ab:
    graph[x[0]-1][x[1]-1]=True
    graph[x[1]-1][x[0]-1]=True
def dfs(v,n,visited):
    all_visited=True
    for i in range(n):
        if visited[i]==False:
            all_visited=False
    if all_visited:
        return 1
    ret=0
    for i in range(n):
        if graph[v][i]==False:
            continue
        if visited[i]:
            continue
        visited[i]=True
        ret+=dfs(i,n,visited)
        visited[i]=False
    return ret
print(dfs(0,n,visited))

Submission status: Accepted

Solution code:
import copy
def explore(key, flags):
    flags = copy.copy(flags)
    if flags[key-1]:
        return 0
    flags[key-1] = True
    if False not in flags:
        return 1
    elif key in graph:
        value = graph[key]
        ans = 0
        for i in value:
            ans += explore(i, flags)
        return ans
    else:
        return 0

n, m = map(int, input().split())
graph = {}
for i in range(m):
    a, b = map(int, input().split())
    if a in graph:
        graph[a].append(b)
    else:
        graph[a] = [b]
    if b in graph:
        graph[b].append(a)
    else:
        graph[b] = [a]

flags = [False for i in range(n)]
ans = explore(1, flags)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Aug 26 11:59:46 2018

@author: maezawa
"""

n, m = list(map(int, input().split()))
array = [[0]*n for _ in range(n)]
for i in range(m):
    ai, bi = list(map(int, input().split()))
    array[ai-1][bi-1] = 1
    array[bi-1][ai-1] = 1

#print(array)
#dp = [[-1]*n for _ in range(n)]
done = []

def f(i,done):
    if i in done:
        return 0
    if len(done) == n-1:
        return 1
    if sum(array[i]) == 1 and i != 0:
        return 0
    #if dp[i][j] != -1:
    #    return dp[i][j]
    donecopy = done + [i]
    #print(donecopy)
    ans = sum([f(bi,donecopy) for bi in range(n) if array[i][bi] != 0])
    return ans

print(f(0,done))

Submission status: Accepted

Solution code:
#ABC054C
import itertools
N, M=map(int,input().split())
a=[0]*0
b=[0]*0
order=list(itertools.permutations(range(N-1) ) )#0～N-2のN-1個の順列ができる。2を足すと、2～Nの配列。
c_patern=0
for i in range(M):
    a_tmp, b_tmp=map(int,input().split())
    a.append(a_tmp)
    b.append(b_tmp)
for i in range(len(order)):
    for j in range(N-1):
        flg = False
        if j==0:
            for k in range(M):
                if (a[k]==1 and b[k]==order[i][0]+2):
                    flg=True
                    break
        else:
            for k in range(M):
                if (a[k]==order[i][j-1]+2 and b[k]==order[i][j]+2) or (a[k]==order[i][j]+2 and b[k]==order[i][j-1]+2):
                    flg=True
                    break
        if flg==False:
            break
    if flg==True:
        c_patern+=1
print(c_patern)

Submission status: Accepted

Solution code:
from itertools import permutations 

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

answer = 0 
for path in permutations(range(2, N+1)):
    path = [1] + list(path)
    found = True 
    for i in range(1, len(path)):
        if not [path[i], path[i-1]] in a and not [path[i-1], path[i]] in a:
            found = False
            break
    if found:
        answer += 1
print(answer)

Submission status: Accepted

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

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

visit = [True] + [False] * (n-1)
print(dfs(0,visit))

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N,M = inpl()
lines = defaultdict(set)
for _ in range(M):
	a,b = inpl()
	a,b = a-1,b-1
	lines[a].add(b)
	lines[b].add(a)

ans = 0

def search(s,ed,num):
	global ans

	if num == N:
		ans += 1
	else:
		for t in lines[s]:
			if not ed & (1<<t):
				search(t,ed+(1<<t),num+1)


search(0,1,1)
print(ans)

Submission status: Accepted

Solution code:
def search(node):
    global ans

    if sum(is_visit) == n:
        ans += 1

    for i in range(n):
        if is_neighbor[node][i]:
            if not is_visit[i]:
                is_visit[i] = True
                search(i)
                is_visit[i] = False

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

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

is_visit = [False for _ in range(n)]

ans = 0

is_visit[0] = True
search(0)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
from itertools import permutations as pe

d=dd(list)
n,m=map(int,input().split())

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

c=0

for i in pe(range(2,n+1)):
  a=d[1]
  f=True
  for j in i:
    if not j in a:
      f=False
      break
    else:
      a=d[j]
  if f:c+=1

print(c)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def ary(r, c, v): return [[v for _ in range(c)] for _ in range(r)]
n, m = map(int, input().split())
e = ary(n, n, False)
for i in range(m):
    a, b = map(int, input().split())
    #頂点を0-indexedに変換
    a -= 1
    b -= 1
    e[a][b] = True
    e[b][a] = True
ps = set()
ps.add('0')

for cnt in range(1, n):
    t = set()
    for p in ps:
        for i in map(str, range(1, n)):
            if not(i in p):
                t.add(p + i)
    ps = t.copy()

ans = 0
for p in ps:
    flg = True
    for i in range(n - 1):
        a = int(p[i])
        b = int(p[i + 1])
        if not e[a][b]:
            flg = False
            break
    if flg:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

N,M = map(int, input().split())
AB = set()
for i in range(M):
    A,B = map(int, input().split())
    AB.add((A-1,B-1))

s = ""
for i in range(1,N):
    s = s + str(i)
    
paths = permutations(s,N-1)
paths = list(paths)

ans = 0
for path in paths:
    path = [0] + [int(i) for i in path]

    for i in range(N-1):
        if (not (path[i],path[i+1]) in AB) and (not (path[i+1], path[i]) in AB):
            break
        
        if i == N-2:
            ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
def na(): return map(int, input().split())
n, m = na()
edges = [[False for _ in range(n)] for _ in range(n)]
for i in range(m):
    a, b = na()
    a -= 1
    b -= 1
    edges[a][b] = True
    edges[b][a] = True

pathes = {'0'}#permutationで求めたpath
for i in range(n-1):
    buf = set()
    for pre_path in pathes:
        for v in map(str, range(1, n)):
            if not(v in pre_path):
                buf.add(pre_path + v)
    pathes = buf.copy()
##print(pathes)
##print(edges)

ans = 0
for path in pathes:
    flg = True
    for i in range(1, n):
        a, b = map(int, [path[i-1], path[i]])
##        print(a, b, edges[a][b])
        if not edges[a][b]:
            flg = False
            break
    if flg:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
N, M = map(int, input().split())
g = [[0] * N for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    g[a][b] = g[b][a] = 1

cnt = 0
for e in permutations(range(1, N)):
    for a, b in zip([0] + list(e[:-1]), e):
        if not g[a][b]:
            break
    else:
        cnt += 1
print(cnt)

Submission status: Accepted

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

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

flag = [False] * (n+1)
flag[0] = True
cnt = 0

def dfs(i, flag):
    flag[i] = True
    for b in A[i]:
        if not flag[b]:
            dfs(b, flag[:])
    if all(flag) == True:
        global cnt
        cnt += 1

dfs(1, flag[:])
print(cnt)

Submission status: Accepted

Solution code:
n, m = [int(i) for i in input().split()]
A = [[] for i in range(n+1)]
B = [[] for i in range(n+1)]

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

flag = [False] * (n+1)
flag[0] = True
cnt = 0

def dfs(i, flag):
    flag[i] = True
    for b in A[i]+B[i]:
        if not flag[b]:
            dfs(b, flag[:])
    if all(flag) == True:
        global cnt
        cnt += 1

dfs(1, flag[:])
print(cnt)

Submission status: Accepted

Solution code:
n, m = [int(i) for i in input().split()]
A = [[] for i in range(n+1)]
B = [[] for i in range(n+1)]

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

flag = [False] * (n+1)
flag[0] = True
cnt = 0

def dfs(i, flag):
    flag[i] = True
    for b in A[i]:
        if not flag[b]:
            dfs(b, flag[:])
    for b in B[i]:
        if not flag[b]:
            dfs(b, flag[:])
    if all(flag) == True:
        global cnt
        cnt += 1

dfs(1, flag[:])
print(cnt)

Submission status: Accepted

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

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

def dfs(start, edges, path):
    path.append(start)
    if len(path) == N:
        path.pop()
        return 1
    ans = 0
    for u in edges[start]:
        if u in path:
            continue
        ans += dfs(u, edges, path)
    path.pop()
    return ans    

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

Submission status: Accepted

Solution code:
from itertools import permutations
N, M = map( int, input().split())
edges = [[] for _ in range(N)]
for i in range(M):
    a, b = map( int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
ans = 0
for X in permutations(range(N),N):
    if X[0] != 0:
        continue
    Flag = True
    for i in range(1,N):
        if X[i] in edges[X[i-1]]:
            pass
        else:
            Flag = False
            break
    if Flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n, m = map(int, input().split())

ans = 0
G = defaultdict(list)
vis = [0] * n
for i in range(m):
    a, b = map(int, input().split())
    G[a - 1].append(b - 1)
    G[b - 1].append(a - 1)


def dfs(k, cnt):
    global ans

    vis[k] = 1

    if cnt == n - 1:
        ans += 1
    else:
        for i in G[k]:
            if vis[i] == 0:
                dfs(i, cnt + 1)

    vis[k] = 0


dfs(0, 0)
print(ans)

Submission status: Accepted

Solution code:
def dfs(v, path):
    path.append(v)
    if len(path) == n:
        path.pop()
        return 1
    ans = 0
    for u in links[v]:
        if u in path:
            continue
        ans += dfs(u, path)
    path.pop()
    return ans


n, m = map(int, input().split())
links = [set() for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
print(dfs(0, []))

Submission status: Accepted

Solution code:
from copy import deepcopy

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

edges = {}
for i in range(m):
    a, b = list(map(int, input().split()))
    if not a in edges.keys():
        edges[a] = [b]
    else:
        edges[a].append(b)
    if not b in edges.keys():
        edges[b] = [a]
    else:
        edges[b].append(a)

ans = 0

nodes = edges[1]
visited = [1] + [0]*(n-1)
nodes_visited = [(node, visited) for node in nodes]
while len(nodes_visited) > 0:

    # print(nodes_visited)
    node, vstd = nodes_visited[0]
    vstd = deepcopy(vstd)
    nodes_visited = nodes_visited[1:]

    vstd[node-1] = 1
    if min(vstd) > 0:
        ans += 1
        continue

    for node_next in edges[node]:
        if vstd[node_next-1] == 1:
            continue
        else:
            nodes_visited.append((node_next, vstd))

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

# DFSでやる版

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

# 入力値の頂点ペア(辺)を格納する配列
a = [0] * M
b = [0] * M

# 頂点ペアが隣接しているかどうかを格納する配列
graph = [[False for i in range(N)] for j in range(N)]

# 入力値の頂点ペア(辺)を格納していくループ
for i in range(M):
    a[i], b[i] = map(int, input().split())
    # 添字に合わせて入力値から1減らしておく
    a[i] -= 1
    b[i] -= 1
    # 入力値の内容に合わせて、隣接していることを記録
    graph[a[i]][b[i]] = True
    graph[b[i]][a[i]] = True

cnt = 0
p = [0] * N
def dfs(pos, mask):
    # 関数内で更新して外部で参照する変数のglobal宣言
    global cnt
    # 最後まで到達できた時はここを通る
    if pos == N:
        # 前提としてスタート地点(添字0)が0かどうか確認
        if p[0] == 0:
            for i in range(N-1):
                # 各辺が存在(各頂点ペアが隣接)しているか確認していく
                if graph[p[i]][p[i+1]] == False:
                    break
                # 全て存在すれば条件を満たすのでカウント+1
                if i == N-2:
                    cnt += 1
        return
    for i in range(N):
        # 残っている数の中にiがまだ残っている場合
        # (maskの中に(1<<i)のビットがまだ残っていればTrueを返す)
        if mask & (1<<i):
            p[pos] = i
            # 残っている数からiを取り除く
            # (排他的論理和XORで重複部分が0になる)
            dfs(pos+1, mask^(1<<i))
# 0からN-1までの数の集合
dfs(0, (1<<N)-1)
print(cnt)

# 参考：2進数の1を左へ3ビット移動(1→8)
# (1 << 3)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import itertools

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

# 入力値の頂点ペア(辺)を格納する配列
a = [0] * M
b = [0] * M

# 頂点ペアが隣接しているかどうかを格納する配列
graph = [[False for i in range(N)] for j in range(N)]

# 入力値の頂点ペア(辺)を格納していくループ
for i in range(M):
    a[i], b[i] = map(int, input().split())
    # 添字に合わせて入力値から1減らしておく
    a[i] -= 1
    b[i] -= 1
    # 入力値の内容に合わせて、隣接していることを記録
    graph[a[i]][b[i]] = True
    graph[b[i]][a[i]] = True

# 頂点をつなぐ全組み合わせ(順列)
# Nが少なければこれでいけるんだね…
perm_list = list(itertools.permutations(range(N)))

cnt = 0
for i in range(len(perm_list)):
    # 今回は出発点が1(添字0)と決まっているので、それ以外はbreak
    if perm_list[i][0] != 0:
        break
    for j in range(len(perm_list[i])-1):
        # 各辺が存在(各頂点ペアが隣接)しているか確認していく
        if graph[perm_list[i][j]][perm_list[i][j+1]] == False:
            break
        # 全て存在すれば条件を満たすのでカウント+1
        if j == len(perm_list[i])-2:
            cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
# time complexity: O(N*N!) (本当はO(N!))
# space complexity: O(M)
from itertools import permutations


N, M = [int(elem) for elem in input().split(' ')]
edge_set = set([tuple([int(elem) - 1 for elem in input().split(' ')]) for _ in range(M)])
edge_set |= {(edge[1], edge[0]) for edge in edge_set}
assert len(edge_set) == 2 * M

num_possible_path = 0
for permutation in permutations(range(1, N), N-1):
    permutation = [0] + list(permutation)
    for i in range(N - 1):
        if tuple(permutation[i:i+2]) not in edge_set:
            break
        else:
            continue
    else:
        num_possible_path += 1

print(num_possible_path)

Submission status: Accepted

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

import itertools

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

dests = [[] for _ in range(n)]

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

res = 0
p =  list(itertools.permutations(range(n)))

for l in p:
    if l[0] != 0: continue
    flg = True
    for i in range(n-1):
        if not(l[i+1] in dests[l[i]]):
            flg = False
            break

    if flg == True: res += 1

print(res)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)

def memoize(function):
    def _memoize(*args, _cache={}):
        if args in _cache:
            return _cache[args]
        result = function(*args)
        _cache[args] = result
        return result
    return _memoize


class Union_find():

    def __init__(self, num):
        self.num = num
        self.par = list(range(num))
        self.rank = [0]*num

    def find(self, x):
        px = self.par[x]
        if px == x:
            return x
        else:
            rx = self.find(px)
            self.par[x] = rx
            return rx

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] > self.rank[y]:
                self.par[y] = x
            else:
                self.par[x] = y
                if self.rank[x] == self.rank[y]:
                    self.rank[y] = self.rank[y] + 1
        return self

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

    def group_num(self):
        l = set()
        for i in range(self.num):
            l.add(self.find(i))
        return len(l)


class Adjlist():

    def __init__(self, nodes, edges = None):
        self.nodes = nodes
        lis = [set() for i in range(nodes)]
        if edges is not None:
            for edge in edges:
                lis[edge[0]].add(edge[1])
        self.edges = lis

    def add_edge(self, edge):
        self.edges[edge[0]].add(edge[1])
        return self

    def discard_edge(self, edge):
        self.edges[edge[0]].discard(edge[1])
        return self

    def next_set(self, x):
        return self.edges[x]

    def include_edge(self, x, y):
        return y in self.next_set(x)

class Adjlist_weighted():

    def __init__(self, nodes, edges = None):
        self.nodes = nodes
        lis = [{} for i in range(nodes)]
        if edges is not None:
            for edge in edges:
                lis[edge[0]][edge[1]] = edge[2]
        self.edges = lis

    def add_edge(self, edge):
        self.edges[edge[0]][edge[1]] = edge[2]
        return self

    def discard_edge(self, edge):
        del self.edges[edge[0]][edge[1]]
        return self

    def next_set(self, x):
        return self.edges[x].keys()

    def include_edge(self, x, y):
        return y in self.next_set(x)

    def weight_edge(self, x, y):
        return self.edge[x][y]

class Adjmat():

    def __init__(self, nodes, edges = None):
        self.nodes = nodes
        mat = [[0]*nodes for i in range(nodes)]
        if edges is not None:
            for edge in edges:
                mat[edge[0]][edge[1]] = 1
        self.edges = mat

    def add_edge(self, edge):
        self.edges[edge[0]][edge[1]] = 1
        return self

    def discard_edge(self, edge):
        self.edges[edge[0]][edge[1]] = 0
        return self

    def include_edge(self, x, y):
        return self.edge[x][y] == 1

    def next_set(self, x):
        set = set()
        for y in range(nodes):
            if self.include_edge(x, y):
                set.add(y)
        return set


class Adjmat_weighted():

    def __init__(self, nodes, edges = None):
        self.nodes = nodes
        mat = [[None]*nodes for i in range(nodes)]
        if edges is not None:
            for edge in edges:
                mat[edge[0]][edge[1]] = edge[2]
        self.edges = mat

    def add_edge(self, edge):
        self.edges[edge[0]][edge[1]] = edge[2]
        return self

    def discard_edge(self, edge):
        self.edges[edge[0]][edge[1]] = None
        return self

    def include_edge(self, x, y):
        return self.edges[x][y] is not None

    def next_set(self, x):
        set = set()
        for y in range(nodes):
            if self.include_edge(x, y):
                set.add(y)
        return set

    def weight_edge(self, x, y):
        return self.edge[x][y]


class Graph():

    def __init__(self, nodes, adj_mat = True, weighted = False, directed = False, edges = None):
        self.nodes = nodes
        self.adj_mat = adj_mat
        self.directed = directed
        self.weighted = weighted
        if weighted:
            if not(directed):
                if edges is not None:
                    for edge in edges:
                        edges.add((edge[1], edge[0], edge[2]))
            if adj_mat:
                edges = Adjmat_weighted(nodes, edges)
            else:
                edges = Adjlist_weighted(nodes, edges)
        else:
            if not(directed):
                if edges is not None:
                    for edge in edges:
                        edges.add((edge[1], edge[0]))
            if adj_mat:
                edges = Adjmat(nodes, edges)
            else:
                edges = Adjlist(nodes, edges)
        self.edges = edges

    def add_edge(self, edge):
        self.edges.add_edge(edge)
        if not(self.directed):
            if self.weighted:
                self.edges.add_edge((edge[1], edge[0], edge[2]))
            else:
                self.edges.add_edge((edge[1], edge[0]))
        return self

    def discard_edge(self, edge):
        self.edges.discard_edge(edge)
        if not(self.directed):
            self.edges.discard_edge((edge[1], edge[0]))
        return self

    def include_edge(self, x, y):
        return self.edges.include_edge(x, y)

    def next_set(self, x):
        return self.edges.next_set(x)

    def weight_edge(self, x, y):
        if self.weighted:
            return self.edges.weight_edge(x, y)
        elif self.adj_mat:
            return self.edges[x][y]
        else:
            if self.include_edge(x, y):
                return 1
            else:
                return 0

    def union_find(self):
        uf = Union_find(self.nodes)
        if self.adj_mat:
            for i in range(self.nodes):
                for j in range(self.nodes):
                    if self.edges.include_edge(i, j):
                        uf.union(i, j)
        else:
            for i in range(self.nodes):
                for j in self.edges.next_set():
                    uf.union(i, j)
        return uf

(N, M) = tuple(map(int, input().split(" ")))
g = Graph(N, False)
for i in range(M):
    g.add_edge(tuple(map(lambda x:int(x)-1, input().split(" "))))

@memoize
def one_path(point, path=(), remin = N-1):
    if remin != 0:
        s = set(path)
        s.add(point)
        d = g.next_set(point) - s
        sum = 0
        for n in d:
            sum += one_path(n, tuple(s), remin - 1)
        return sum
    else:
        return 1

print(one_path(0))

Submission status: Accepted

Solution code:
import itertools
n,m = map(int,raw_input().split())

permutations = list(itertools.permutations(range(1,n)))


arr = [[-1 for i in range(n)] for j in range(n)]


for i in range(m):
	f,t = map(int,raw_input().split())
	f -= 1
	t -= 1
	arr[f][t] = 1
	arr[t][f] = 1


ans = 0
for p in permutations :
	count = 0
	if arr[0][p[0]] == 1 :
		count += 1
	else:
		next

	for i in range(0,len(p)-1):
		if arr[p[i]][p[i+1]] == 1 :
			count += 1

		else:
			break

	if count == n-1 :
		ans += 1
print ans

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a, b = [], []

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

zero_mask = "".join(['0' for x in range(N)])
full_mask = "".join(['1' for x in range(N)])
paths_cnt = 0
paths_set = set()

def do_mask(m, idx) :
    newmask = m[:idx] + '1' + m[idx + 1:]
    return newmask

def dfs(m, idx) :
    global paths_cnt
    
    # print("DBG, do dfs with : ", m, idx)
    # do mask for current idx
    newmask = do_mask(m, idx)
    
    if newmask == full_mask :
        paths_cnt += 1
    else :
        for i in range(N) :
            # print("DBG2 : ", idx != i, newmask[i] != '1', (idx, i) in paths_set, (idx, i))
            if idx != i and newmask[i] != '1' and (idx, i) in paths_set:
                dfs(newmask, i)
# generate map
for i in range(M) :
    paths_set.add((a[i], b[i]))
    paths_set.add((b[i], a[i]))
    
dfs(zero_mask, 0)
print(paths_cnt)

Submission status: Accepted

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

for i in range(M) :
    _f, _t = map(int, input().split())
    paths.add((_f - 1, _t - 1))
    paths.add((_t - 1, _f - 1))

zeromask = "".join(['0' for x in range(N)])
fullmask = "".join(['1' for x in range(N)])
cnt = 0

def do_mask(m, idx) :
    return m[:idx] + '1' + m[idx + 1:]

def dfs(m, idx) :
    global cnt
    new_mask = do_mask(m, idx)
    
    if new_mask == fullmask :
        cnt += 1
    else :
        for i in range(N) :
            if i != idx and m[idx] != '1' and (idx, i) in paths:
                dfs(new_mask, i)
            
dfs(zeromask, 0)
print(cnt)

Submission status: Accepted

Solution code:
import numpy as np

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

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

for i in range(len(arr)):
    arr[i].sort


def dfs(array,point,cnt):
    
    if(array[point]==[]):
        return cnt

    tmparr = array.copy()
    ps = tmparr[point]
    tmparr[point] = []
    
    if sum(map(len,tmparr)) == 0:
        return cnt+1
    
    for p in ps:
        #print(tmparr, p)
        cnt = dfs(tmparr,p,cnt)
    
    return cnt

print(dfs(arr,0,0))

Submission status: Accepted

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

zero_mask = "".join(["0" for x in range(n)])
full_mask = "".join(["1" for x in range(n)])

paths_cnt = 0

for i in range(m) :
    _a, _b = map(int, input().split())
    paths.add((_a - 1, _b - 1))
    paths.add((_b - 1, _a - 1))

def mask_idx(s, idx) :
    newmask = s[:idx] + "1" + s[idx + 1:] 
    return newmask 

def dfs(cur_idx, mask) :
    
    global paths_cnt
    new_mask = mask_idx(mask, cur_idx)
    # print("DBG : ", cur_idx, new_mask, full_mask)
    
    if new_mask == full_mask :
        paths_cnt += 1
    for i in range(n) : 
        if i != cur_idx and new_mask[i] != '1' and (cur_idx, i) in paths:
            dfs(i, new_mask)
            
dfs(0, zero_mask)
print(paths_cnt)

Submission status: Accepted

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

for i in range(m) :
    _a, _b = map(int, input().split())
    paths.add((_a - 1, _b - 1))
    paths.add((_b - 1, _a - 1))

full_mask = "".join(["1" for x in range(n)])
zero_mask = "".join(["0" for x in range(n)])
p_cnt = 0

def dfs(cur_idx, mask) :
    global p_cnt
    
    # set mask and do traverse
    new_mask = list(mask)
    new_mask[cur_idx] = "1"
    new_mask = "".join(new_mask)

    # print("DBG : ", cur_idx, new_mask, full_mask, new_mask == full_mask)
    
    if new_mask == full_mask :
        p_cnt += 1
    else :
        for i in range(n) :
            # if cur_idx -> i in set and i not traversed yet..
            if (cur_idx, i) in paths and mask[i] != "1" :
                dfs(i, new_mask)

dfs(0, zero_mask)
print(p_cnt)

Submission status: Accepted

Solution code:
from itertools import permutations

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

for i in range(m) :
    _a, _b = map(int, input().split())
    paths.add((_a, _b))
    paths.add((_b, _a))
    
print(sum(all(s in paths for s in zip((1,) + p, p)) for p in permutations(range(2, n + 1))))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
e=[[]for _ in[0]*-~n]
for _ in[0]*m:
    a,b=map(int,input().split())
    e[a]+=[b]
    e[b]+=[a]
candy=[[1]]
for _ in[0]*~-n:
    tmp=[]
    for c in candy:
        for next in e[c[-1]]:
            tmp+=[c+[next]]
    candy=tmp
print(sum(c==set(range(1,n+1))for c in map(set,candy)))

Submission status: Accepted

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

ans = 0

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

def dfs(v):
    global ans, used
    if len(used) == N:
        ans += 1
        return
    else:
        for next_v in vertex_list[v]:
            if next_v not in used:
                used.add(next_v)
                dfs(next_v)
                used.remove(next_v)
        return

used = set([1])
dfs(1)

print(ans)

Submission status: Accepted

Solution code:
import copy

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

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

temp = []

def trace(p, route):
    hoge = copy.deepcopy(route)
    hoge.append(p)
    ret = 0
    for i in range(n):
        if i not in hoge and x[p][i] == 1:
            if len(hoge) == n - 1:
                return 1
            else:
                ret += trace(i, hoge)
    return ret

print(trace(0, temp))

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import permutations
import sys
sys.setrecursionlimit(10000)
N,M=list(map(int,input().split()))
links=defaultdict(set)
for i in range(M):
    a,b=list(map(int, input().split()))
    links[a].add(b)
    links[b].add(a)
ct=0
for pts in permutations(range(2,N+1),N-1):
    current=1
    for p in pts:
        if  p not in links[current]:
            break
        else:
            current=p
    else:
        ct+=1
print(ct)