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.

Solution (Python):

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, []))

Solution (Python):
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)
        

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

    print(cnt)


if __name__ == '__main__':
    solve()

Solution (Python):
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)

Solution (Python):

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)

Solution (Python):
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)

Solution (Python):
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))

Solution (Python):
from collections import defaultdict
from itertools import permutations

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

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

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
N,M = map(int, raw_input().split())
E = [[] for _ in range(N)]
for _ in range(M):
  a,b = map(int, raw_input().split())
  E[a-1] += [b-1]
  E[b-1] += [a-1]

def BT(p, c, V):
  if c==N-1:
    return 1
  V[p] = True
  ans = 0
  for e in E[p]:
    if not V[e]:
      ans += BT(e, c+1, V)
  V[p] = False
  return ans

print BT(0, 0, [False]*N)

Solution (Python):
from itertools import permutations

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

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

ans = 0
for p in permutations(range(1, n)):
    f = True
    pos = 0
    for i in p:
        if i in adj[pos]:
            pos = i
        else:
            f = False
            break
    if f:
        ans += 1

print ans

Solution (Python):
import sys

stdin = sys.stdin
def na(): return map(int, stdin.readline().split())
def ns(): return stdin.readline().strip()

n,m = na()
g = [[0]*n for _ in range(n)]
for i in range(m):
    x,y = na()
    g[x-1][y-1] += 1
    g[y-1][x-1] += 1

import itertools

ct = 0
for a in itertools.permutations(range(n)):
    if a[0] != 0: break
    plus = 1
    for i in range(n-1):
        plus = plus * g[a[i]][a[i+1]]
    ct += plus
print(ct)