Problem:


Score : 300 points

Problem Statement

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

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

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

Here, the endpoints of a path are considered visited.  

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

Figure 1: an example of an undirected graph

The following path shown in Figure 2 satisfies the condition.

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

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

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

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

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

Constraints

2≦N≦8 

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

1≦a_i<b_i≦N 

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

Input

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

N M  
a_1 b_1  
a_2 b_2
:  
a_M b_M  

Output

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

Sample Input 1

3 3
1 2
1 3
2 3

Sample Output 1

2

The given graph is shown in the following figure:

The following two paths satisfy the condition:

Sample Input 2

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

Sample Output 2

1

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



Sample input:
3 3
1 2
1 3
2 3


Sample output:
2

Submission status: Accepted

Solution code:
import sys
from itertools import permutations

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def do_dp(N, Adj):
    univ = 2**N - 1
    dp = [[0]*N for i in range(univ + 1)]
    dp[1][0] = 1

    for S in range(2, univ + 1):
        for v in range(N):
            S2 = S & (univ ^ (1 << v))
            for u in range(N):
                if ((1 << u) & S2) and Adj[u][v]:
                    dp[S][v] += dp[S2][u]

    # debug(dp, locals())
    ans = sum(dp[univ][u] for u in range(1, N))

    return ans

def solve():
    N, M = map(int, input().split())
    Adj = [[0]*N for i in range(N)]

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

    ans = do_dp(N, Adj)

    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
from itertools import permutations

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

cnt = 0

def dfs(N, Adj, p, pos, mask):
    global cnt

    if pos == N:
        for i in range(N - 1):
            if not Adj[p[i]][p[i + 1]]:
                break
        else:
            cnt += 1

        return None

    for i in range(N):
        if mask & (1 << i):
            p[pos] = i
            dfs(N, Adj, p, pos + 1, (mask ^ (1 << i)))

    return None

def solve():
    global cnt
    cnt = 0

    N, M = map(int, input().split())
    Adj = [[0]*N for i in range(N)]

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

    p = list(range(N))
    dfs(N, Adj, p, 1, (2 << N) - 1 - 1)

    print(cnt)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import itertools
N, M = list(map(int, input().split()))
path = [[0 for i in range(N)] for j in range(N)]
for i in range(M):
    a, b = list(map(int, input().split()))
    path[a-1][b-1] = 1
    path[b-1][a-1] = 1

count = 0

for p in itertools.permutations(range(N)):
    if p[0] != 0:
        break
    check = 1
    for search in range(N-1):
        check = check * path[p[search]][p[search+1]]
    count += check

print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import permutations


def main():
    N, M = map(int, input().split())
    graph = defaultdict(list)
    for _ in range(M):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)

    ans = 0
    for route in permutations(range(2, N + 1), N - 1):
        ok = True
        now = 1
        for node in route:
            if node in graph[now]:
                now = node
            else:
                ok = False
        ans += ok

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import repeat, permutations


if __name__ == '__main__':
    n, m = map(int, input().split())    # 2≦N≦8    nが小さいので列挙でもいけるか?
    # 0≦M≦N(N−1)⁄2    全ての頂点が結ばれている場合もあり得る。
    edges = [list(repeat(False, n)) for i in range(n)]
    for i in range(m):
        a, b = map(int, input().split())
        a -= 1      # 0オリジン
        b -= 1
        edges[a][b] = True
        edges[b][a] = True
    # print(edges)
    # 末端(1本しか道のない頂点)の数で分類すれば高速化するが、
    # 末端のないケースが通るなら場合分けしなくてもTLEしないはず。
    result = 0      # 結果格納用
    # 出発は頂点1(コード内の番号は0)なので、それ以外についてリストする。
    for order_iterable in permutations(range(1, n)):
        order = [0] + list(order_iterable)
        # orderの隣同士の間に辺が存在することが、到達可能の条件
        if all([edges[order[i - 1]][order[i]] for i in range(1, n)]):
            result += 1     # 計数
    print(result)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()


def main():
    n,m = LI()
    r = 0
    d = collections.defaultdict(set)
    for _ in range(m):
        a,b = LI()
        d[a].add(b)
        d[b].add(a)
    for a in itertools.permutations(range(2,n+1)):
        if a[0] not in d[1]:
            continue
        f = True
        for i in range(len(a)-1):
            if a[i] not in d[a[i+1]]:
                f = False
                break
        if f:
            r += 1

    return r


print(main())

Submission status: Accepted

Solution code:
import itertools

s = input()
l = s.split()
N = int(l[0])
M = int(l[1])

a = list()
b = list()
edges = set()
for i in range(1, M + 1):
    s = input()
    l = s.split()
    u = int(l[0])
    v = int(l[1])
    a.append(u)
    b.append(v)
    edges.add((u, v))
    edges.add((v, u))
#print(edges)

t = range(1, N + 1)
res = 0
for p in itertools.permutations(t):
    if p[0] != 1:
        break
    c = 0
    for j in range(0, N - 1):
        if (p[j], p[j + 1]) in edges:
            c += 1
    if c == N - 1:
        res += 1
print(res)

Submission status: Accepted

Solution code:
import numpy as np

class Node:
    def __init__(self, id):
        self.id = id
        self.nexts = []
        self.visited = False

    def add_next(self, node):
        self.nexts.append(node)

def saiki(node, count, judge):
    node.visited = True
    judge[node.id] = True
    if(all(judge)):
        count[0]+=1

    for next in node.nexts:
        if(not next.visited):
            saiki(next, count, judge)
    node.visited = False
    judge[node.id] = False

if __name__=="__main__":
    inputs = lambda : input().replace("\n", "").split(" ")
    N, M = [int(number) for number in inputs()]

    nodes = [Node(i) for i in range(N)]
    for i in range(M):
        x, y = [int(number)-1 for number in inputs()]
        nodes[x].add_next(nodes[y])
        nodes[y].add_next(nodes[x])

    judge = [False]*N
    count = [0]
    saiki(nodes[0], count , judge)
    print(count[0])

Submission status: Accepted

Solution code:
n,m=map(int,raw_input().split())
graph=[[] for i in xrange(n)]
while m>0:
	m-=1
	a,b=map(int,raw_input().split())
	a-=1
	b-=1
	graph[a].append(b)
	graph[b].append(a)
# print graph
pathcount=0

def dfs(source,l=[]):
	global pathcount
	for i in (graph[source]):
		# print source,graph[source]
		if i not in l:
			l.append(source)
			if len(l)==n:
				pathcount+=1
			# print "exploring ",source," to ",i
			dfs(i,l)
			l.remove(source)
			# print "completed ",source
		# else:
			# print i,"is alrready explored"
	

			
dfs(0,[0])
print pathcount

Submission status: Accepted

Solution code:
import itertools
N, M = map(int, input().split())
E = set([tuple(sorted(map(int, input().split()))) for x in range(M)])
cnt = 0
for i in itertools.permutations(range(2,N+1), N-1):
    l = [1]+list(i)
    if sum(1 for x in range(N-1) if tuple(sorted(l[x:x+2])) in E) == N-1:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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


# paths = [0] * (n+1)
# paths[1] = 1
# for i in range(1, n+1):
#     for j in graph[i]:
#         paths[j] += paths[i]
# print(paths[n])

def find_all_paths(graph, start, rest, path=[]):
    path = path + [start]
    rest2 = rest.copy()
    rest2.remove(start)
    if len(rest2) == 0:
        return [path]
    if start not in graph:
        return []
    paths = []
    for node in graph[start]:
        if node not in path:
            newpaths = find_all_paths(graph, node, rest2, path)
            for newpath in newpaths:
                paths.append(newpath)
    return paths

paths = find_all_paths(graph, 1, set(graph.keys()))
print(len(paths))

Submission status: Accepted

Solution code:
class Path:
    def __init__(self):
        self.a = -1
        self.b = -1

    def getA(self):
        return self.a
    def setA(self, aa):
        self.a = aa
    def getB(self):
        return self.b
    def setB(self, bb):
        self.b = bb

def trace_path(ps, s, cnt, num):
    res = 0
    
    s2 = []
    ps2 = []
    for i in range(0, len(ps)):
        p = ps[i]
        if p.getA() == s or p.getB() == s:
            s2.append(p)
        else:
            ps2.append(p)
    if len(ps2) == 0:
        if cnt == num:
            res += 1
    else:
        for i in range(0, len(s2)):
            p = s2[i]
            if p.a == s:
                res += trace_path(ps2, p.getB(), cnt+1, num)
            else:
                res += trace_path(ps2, p.getA(), cnt+1, num)
    return res

in1 = input().split()
n = int(in1[0])
m = int(in1[1])

ps = []
for i in range(0, m):
    in2 = input().split()
    p = Path()
    p.a = int(in2[0])
    p.b = int(in2[1])
    ps.append(p)
                       
res = trace_path(ps, 1, 1, n-1)

print(str(res))

Submission status: Accepted

Solution code:
from itertools import permutations
n, m = map(int, input().split())
edge = set()

ans = 0
for _ in range(m):
    a, b = map(int, input().split())
    edge.add((a, b))

is_used = set([])
for per in permutations(range(2, n + 1)):
    flag = True
    if (1, per[0]) not in edge:
        continue
    for i in range(n - 2):
        if (per[i], per[i + 1]) not in edge and (per[i + 1], per[i]) not in edge:
            flag = False
            break
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy as dcopy
def main():
    global count,N,M,edges,stack
    N, M = map(int, input().split())
    edges = [[0]*N for n in range(N)]
    for m in range(M):
        a,b = map(lambda x:int(x)-1,input().split())
        edges[a][b] = 1
        edges[b][a] = 1

    count = 0
    stack = [[[0], [0]]]
    while len(stack) != 0:
        tansaku = stack.pop()
        next_list = [n for n,v in enumerate(edges[tansaku[0][-1]]) if v == 1]
        search(tansaku, next_list)
    print(count)

def search(tansaku, next_list):
    global count, stack
    for node in next_list:
        tmp_tansaku = dcopy(tansaku)
        tmp_node = tmp_tansaku[0]
        houmonzumi = tmp_tansaku[1]
        if node in houmonzumi:
            pass
        else:
            houmonzumi.append(node)
            if len(houmonzumi) == N:
                count += 1
            else:
                tmp_node.append(node)
                stack.append([tmp_node, houmonzumi])

if __name__ == "__main__":# {{{
    try:
        import test
        test.test()
    except:
        main()# }}}

Submission status: Accepted

Solution code:
from copy import deepcopy

def wfs(tree, root, node_num):
    lost_list = [root]

    def _wfs(tree, root, lost_list) -> int:
        if len(lost_list) == node_num:
            return 1
        counter = 0
        for i in tree[root]:
            if i not in lost_list:
                tmp = deepcopy(lost_list)
                tmp.append(i)
                counter += _wfs(tree, i, tmp)
        return counter

    return _wfs(tree, 0, lost_list)


n, m = input().rstrip().split()
n, m = int(n), int(m)
v = [list() for i in range(n)]
for _ in range(m):
    line = [int(i) - 1 for i in input().rstrip().split()]
    v[line[0]].append(line[1])
    v[line[1]].append(line[0])

print(wfs(v, 0, n))

Submission status: Accepted

Solution code:
from itertools import permutations

n,m=map(int,input().split())
es=set()
for _ in range(m):
    u,v=map(int,input().split())
    es|={(u-1,v-1),(v-1,u-1)}

print(sum(all((u,v) in es for u,v in zip(p,p[1:]))
          for p in permutations(range(n)) if p[0]==0))

Submission status: Accepted

Solution code:
import collections

if __name__ == '__main__':
    n, m = map(int, input().split())
    
    ht = collections.defaultdict(list)
    for _ in range(m):
        a, b = [int(token) - 1 for token in input().split()]
        ht[a].append(b)
        ht[b].append(a)

    stack = [(0, 0)]
    cnt = 0
    while stack:
        position, history = stack.pop()
        if history | (1 << position) == 2 ** n - 1: cnt += 1

        for next_position in ht[position]:
            if history & (1 << next_position) == 0: stack.append((next_position, history | (1 << position)))
        
    print(cnt)

Submission status: Accepted

Solution code:
import copy
N,M=map(int,raw_input().split())
v=[False for _ in range(N+1)]
v[0]=True
s=[map(int,raw_input().split()) for _ in range(M)]

def recursion(V,p):
    m=0
    for a,b in s:
        if p==a :
            if V[b]:
                continue
            else:
                tmp=copy.deepcopy(V)
                tmp[b]=True
                if all(tmp):
                    m+=1
                else:
                    m+=recursion(tmp,b)
        elif p==b :
            if V[a]:
                continue
            else:
                tmp=copy.deepcopy(V)
                tmp[a]=True
                if all(tmp):
                    m+=1
                else:
                    m+=recursion(tmp,a)
    return m

v[1]=True
print recursion(v,1)

Submission status: Accepted

Solution code:
n,m = input().split()
n = int(n)
m = int(m)
mat = []
for i in range(n):
  mat.append([])
  for j in range(n):
    mat[-1].append(False)

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

def count(ar, s):
  if len(ar) == 1:
    return 1 if mat[s][ar[0]] else 0
  num = 0
  for s_next in ar:
    if mat[s][s_next]:
      num += count([x for x in ar if x != s_next], s_next)
  return num

total = 0
for i in range(n):
  ar = [j for j in range(n) if j != i]
  total += count(ar, i)
  break
print(total)

Submission status: Accepted

Solution code:
import itertools

n,m=map(int,input().split())
path={i+1:[] for i in range(n)}
for i in range(m):
    u,v=map(int,input().split())
    path[u].append(v)
    path[v].append(u)
chk=[i for i in range(2,n+1)]
ans=0
for way in list(itertools.permutations(chk)):
    now=1
    if way[0] in path[now]:
        f=1
        for j in way:
            if j in path[now]:
                now=j
                f+=1
            else:
                break
        if f==n: ans+=1
print(ans)

Submission status: Accepted

Solution code:
import copy

data = raw_input()

n,m = map(int,data.split(" "))

db = []
ans = 0

def search(pos,vis):
  global db
  global ans
  global n,m
  if len(vis) == n:
    ans = ans + 1
    return
  for x in db:
    if x[0] == pos:
      if x[1] not in vis:
        vis2 = copy.deepcopy(vis)
        vis2.append(x[1])
        search(x[1],vis2)

    if x[1] == pos:
      if x[0] not in vis and x[0] != 1:
        vis2 = copy.deepcopy(vis)
        vis2.append(x[0])
        search(x[0],vis2)


for x in range(m):
  data = raw_input()
  a,b = map(int,data.split(" "))
  db.append([a,b])

for x in db:
  if x[0] == 1:
    search(x[1],[1,x[1]])

print ans

Submission status: Accepted

Solution code:
n,m = list(map(int,input().split()))
V=[[] for _ in range(n)]
for _ in range(m):
    a,b=list(map(int,input().split()))
    V[a-1].append(b-1)
    V[b-1].append(a-1)

def solve(path,i,cnt):
    if cnt==n:return 1
    path=list(path)
    path[i]=True
    ans=0
    for v in V[i]:
        if path[v]:continue        
        ans+=solve(tuple(path),v,cnt+1)
    return ans

print(solve([False]*n,0,1))

Submission status: Accepted

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

s = []
past = [1]
for i, a in enumerate(A):
    if a == past[-1] and not B[i] in past:
        s.append(past+[B[i]])
for i, b in enumerate(B):
    if b == past[-1] and not A[i] in past:
        s.append(past+[A[i]])
num_paths = 0
while s:
    past = s.pop()
    if len(past) == N:
        num_paths += 1
        continue
    for i, a in enumerate(A):
        if a == past[-1] and not B[i] in past:
            s.append(past+[B[i]])
    for i, b in enumerate(B):
        if b == past[-1] and not A[i] in past:
            s.append(past+[A[i]])

print(num_paths)

Submission status: Accepted

Solution code:
def dfs(now,vis,G):
    if sum(vis) == len(vis):
        return 1

    ret = 0
    for nx in G[now]:
        if vis[nx] == 0:
            nvis = vis[:]
            nvis[nx] = 1
            ret += dfs(nx,nvis,G)

    return ret

def main():
    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)

    vis = [0 for _ in range(n)]
    vis[0]=1
    return dfs(0,vis,G)

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
import itertools
N, M = [int(n) for n in input().split()]
path = [[False for i in range(N)]for j in range(N)]


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


res = 0
for way in itertools.permutations(range(1,N), N-1):
    exist = True
    if path[0][way[0]] == False:
        exist = False
    for n in range(N-2):
        if path[way[n]][way[n+1]] == False:
            exist = False
    if exist == True:
        res += 1

print(res)

Submission status: Accepted

Solution code:
def read():
    return int(input())

def reads(sep=None):
    return list(map(int, input().split(sep)))

def main():
    n, m = reads();
    g = [set() for _ in range(n+1)]
    for _ in range(m):
        a, b = reads()
        g[a - 1].add(b - 1)
        g[b - 1].add(a - 1)
    
    count = 0
    q = [(0, [])]
    while q:
        i, p = q.pop(0)
        if len(p) == (n-1):
            count += 1
        for e in g[i]:
            if e in p:
                continue
            pp = p[:]
            pp.append(i)
            q.append((e, pp))
    print(count)
 
main()

Submission status: Accepted

Solution code:
import itertools

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

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

ans = 0
for order in itertools.permutations(list(range(1,n))):
    ok = True
    now = 0
    for to in order:
        if to not in connect[now]:
            ok = False
            break
        now = to

    if ok:
        ans += 1

print(ans)

Submission status: Accepted

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

road = [[] for _ in range(N)]

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

counter = 0
    
def search(pointStack):
    global counter
    if len(pointStack) == N:
        counter += 1
        pointStack.pop()
        return
    
    currentNode = pointStack[-1]
    for nextNode in road[currentNode]:
        if nextNode in pointStack:
            continue
        pointStack.append(nextNode)
        search(pointStack)

    pointStack.pop()

search([0])

print(counter)

Submission status: Accepted

Solution code:
n,m=map(int,raw_input().split())
g=[[] for _ in xrange(n)]
for i in xrange(m):
    a,b=map(int,raw_input().split())
    a-=1;b-=1
    g[a].append(b)
    g[b].append(a)
dp=[[0]*(1<<n) for _ in xrange(n)]
dp[0][1]=1
for j in xrange(1<<n):
    for i in xrange(n):
        if j>>i&1:
            for k in g[i]:
                if j>>k&1:
                    continue
                dp[k][j|(1<<k)]+=dp[i][j]
ans=0
for i in xrange(1,n):
    ans+=dp[i][(1<<n)-1]
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
g = [[False]*N for _ in range(N)]
for _ in range(M):
	a, b = map(int, input().split())
	g[a-1][b-1] = True
	g[b-1][a-1] = True

stack = [[0,[1]+[0]*(N-1)]]
ans = 0
while stack:
	cur, passed = stack.pop()
	if passed == [1]*N:
		ans += 1
	else:
		for i, j in enumerate(g[cur]):
			if j and not passed[i]:
				t = passed.copy()
				t[i] = 1
				stack.append([i, t])
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, raw_input().split())
way = {}
for _ in xrange(M):
    a, b = map(int, raw_input().split())
    if a not in way:
        way[a] = set()
    if b not in way:
        way[b] = set()
    way[a].add(b)
    way[b].add(a)

counter = 0
states = deque([({1}, 1)])
while states:
    passed, current = states.popleft()
    if len(passed) == N:
        counter += 1
        continue
    for next_index in way.get(current, []):
        if next_index not in passed:
            states.append((passed | {next_index}, next_index))
print counter

Submission status: Accepted

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

visited = [0 for i in range(n)]


def dfs(src):
    global ans
    if sum(visited) == n: ans += 1
    for dst in range(n):
        if src == dst: continue
        if visited[dst] or A[src][dst] != 1: continue
        visited[dst] = 1
        dfs(dst)
        visited[dst] = 0


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

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

Submission status: Accepted

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

import itertools


def count_paths(n, adj_list):
    res = 0
    for vs in itertools.permutations(range(n)):
        if vs[0] != 0:
            continue
        for i in range(n - 1):
            if vs[i] not in adj_list[vs[i + 1]]:
                break
        else:
            res += 1
    return res


def main():
    n, m = (int(x) for x in input().split())
    adj_list = [set() for _ in range(n)]
    for _ in range(m):
        a, b = (int(y) - 1 for y in input().split())
        adj_list[a].add(b)
        adj_list[b].add(a)
    print(count_paths(n, adj_list))


if __name__ == '__main__':
    main()

Submission status: Accepted

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


memo = {}
all_use = (1 << N) - 1


def rec(v, use):
    if use == all_use:
        return 1

    key = (v, use)
    if key in memo:
        return memo[key]

    res = 0
    for u in g[v]:
        if (use >> u) & 1 == 1:
            continue

        use = use ^ (1 << u)
        res += rec(u, use)
        use = use ^ (1 << u)

    memo[key] = res
    return res


print(rec(0, 1))

Submission status: Accepted

Solution code:
from itertools import permutations

n,m=map(int,input().split())
es=set()
for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    es|={(u,v),(v,u)}

res=0
for p in permutations(range(n)):
    if p[0]!=0: continue
    if all((p[i],p[i+1]) in es for i in range(n-1)):
        res+=1
print(res)

Submission status: Accepted

Solution code:
from collections import defaultdict

N, M = map(int, raw_input().split())
X = [map(int, raw_input().split()) for _ in range(M)]

D = defaultdict(list)
for a, b in X:
    D[a].append(b)
    D[b].append(a)


def dfs(now, p):
    cnt = 0
    if set(now) == set(range(1, N+1)):
        return 1
    for k in D[p]:
        if k in now:
            continue
        cnt += dfs(now + [k], k)
    return cnt

print dfs([1], 1)

Submission status: Accepted

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

from fractions import gcd

def readln():
    _res = list(map(int,str(input()).split(' ')))
    return _res

def dfs(deep,now,v):
    if deep == n:
        return 1
    res = 0
    for i in range(1,n+1):
        if v[i] == 0 and e[now][i] == 1:
            v[i] = 1
            res = res + dfs(deep+1, i, v)
            v[i] = 0
    return res


a = readln()
n,m = a[0],a[1]
e = [[0 for i in range(0,n+1)] for j in range(0,n+1)]
for i in range(0,m):
    a = readln()
    e[a[0]][a[1]] = 1
    e[a[1]][a[0]] = 1
v = [0 for i in range(0,n+1)]
v[1] = 1
print(dfs(1,1,v))

Submission status: Accepted

Solution code:
from itertools import permutations

def f(n, m, uu, vv):
    a = [[0] *n for _ in range(n)]
    for u, v in zip(uu, vv):
        a[u][v] = 1
        a[v][u] = 1
    res = 0
    for p in permutations(range(n)):
        if p[0] != 0:
            break
        ok = True
        for i in range(n - 1):
            if a[p[i]][p[i+1]] == 0:
                ok = False
                break
        if ok:
            res += 1
    return res

n , m = map(int, input().split())
a = []
b = []
for k in range(m):
    _a, _b = map(int, input().split())
    _a -= 1
    _b -= 1
    a.append(_a)
    b.append(_b)
print(f(n, m, a, b))

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

setrecursionlimit(1000000)

(N, M) = reads()

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

for _ in range(M):
  (a, b) = reads()
  (a, b) = (a-1, b-1)
  conn[a][b] = conn[b][a] = True

count = 0

for p in permutations(range(1, N)):
  if conn[0][p[0]] and all(conn[p[i]][p[i+1]] for i in range(N-2)):
    count += 1

print(count)

Submission status: Accepted

Solution code:
def dfs(now,vis,G):
    visit_all = True
    for tf in vis:
        if not tf:
            visit_all = False
    if visit_all:
        return 1

    ret = 0
    for nx in G[now]:
        if vis[nx] == 0:
            nvis = vis[:]
            nvis[nx] = 1
            ret += dfs(nx,nvis,G)

    return ret

def main():
    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)

    vis = [0 for _ in range(n)]
    vis[0]=1
    return dfs(0,vis,G)

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:

N, M = [int(_) for _ in input().split()]
T = [[int(_) - 1 for _ in input().split()] for i in range(M)]

graph = [[] for i in range(N)]
for a, b in T:
    graph[a].append(b)
    graph[b].append(a)


def dfs(node, prev, visited):
    visited.append(node)
    if len(visited) == N:
        return 1

    res = 0
    for edge in graph[node]:
        if edge == prev:
            continue
        if edge in visited:
            continue

        res += dfs(edge, prev, visited[:])

    return res

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

Submission status: Accepted

Solution code:
import sys
from itertools import permutations

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    N, M = map(int, input().split())
    Adj = [[0]*N for i in range(N)]

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

    cnt = 0

    for line in permutations(range(1, N)):
        path = [0] + list(line)
        # debug(path, locals())

        for i in range(N - 1):
            if not Adj[path[i]][path[i + 1]]:
                break
        else:
            cnt += 1

    print(cnt)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import itertools
n,m = map(int, input().split())
g = [[] for i in range(n)]
for i in range(m):
    a,b = map(lambda x:int(x)-1, input().split())
    g[a].append(b)
    g[b].append(a)
cnt = 0
if n == 2:
    if 1 in g[0]:
        print(1)
    else:
        print(0)
    exit()
for p in itertools.permutations(range(1,n)):
    if p[0] in g[0]:
        flag = True
        for i in range(n-2):
            if p[i+1] not in g[p[i]]:
                flag = False
                break
        if flag:
            cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys,copy,math,heapq,itertools as it,fractions,re,bisect,collections as coll

def solve(k, cnt):
    if cnt == N: return 1
    used[k] = True
    res = 0
    for i in xrange(N):
        if used[i]: continue
        if G[k][i] == 0: continue
        res += solve(i, cnt + 1)
    used[k] = False
    return res

N, M = map(int, raw_input().split())
used = [False]*N
G = [[0]*N for i in xrange(N)]
for i in xrange(M):
    a, b = map(int, raw_input().split())
    a -= 1; b -= 1;
    G[a][b] = G[b][a] = 1

print solve(0, 1)

Submission status: Accepted

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

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

vis = [False] * N
ans = 0
def f(v, d):
  global vis, ans
  if d == N:
    ans += 1
    return
  for nxt in range(N):
    if g[v][nxt] and not vis[nxt]:
      vis[nxt] = True
      f(nxt, d + 1)
      vis[nxt] = False

vis[0] = True
f(0, 1)
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, raw_input().split())
E = [[0]*n for i in xrange(n)]

for i in xrange(m):
    a, b = map(int, raw_input().split())
    E[a-1][b-1] = E[b-1][a-1] = 1

memo = {}
def dfs(state, v):
    if state == 0:
        return v == 0
    if (state, v) in memo:
        return memo[state, v]
    res = 0
    for i in xrange(n):
        if E[v][i] and (state >> i) & 1 == 1:
            res += dfs(state ^ (1 << i), i)
    memo[state, v] = res
    return res

print sum(dfs((2**n-1) ^ (1 << i), i) for i in xrange(n))