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: Runtime Error

Solution code:
import itertools

def path(n):
    l = len(n)
    i = 0
    while i < l - 1:
        a = n[i]
        b = n[i + 1]

        if a < b:
            c = (a, b)
        else:
            c = (b, a)

        for m in C:
            if m == c:
                break
        else:
            return False
        i += 1
    return True

N, M = map(int, input().split())
C = []
i = 0
while i < N:
    C += [tuple(map(int, input().split()))]
    i += 1

i = 0
l = range(1, N + 1)
for n in itertools.permutations(l, N):
    if n[0] != 1:
        break
    if path(n) == True:
        i += 1
print(str(i))

Submission status: Runtime Error

Solution code:
import itertools

def path(n):
    l = len(n)
    i = 0
    while i < l - 1:
        a = n[i]
        b = n[i + 1]

        if a < b:
            c = (a, b)
        else:
            c = (b, a)

        for m in C:
            if m == c:
                break
        else:
            return False
        i += 1
    return True

N, M = map(int, input().split())
C = []
i = 0
while i < N:
    C += [tuple(map(int, input().split()))]
    i += 1

i = 0
l = range(1, N + 1)
for n in itertools.permutations(l, N):
    print(n)
    if n[0] != 1:
        break
    if path(n) == True:
        i += 1
print(str(i))

Submission status: Runtime Error

Solution code:
import itertools

def path(n):
    l = len(n)
    i = 0
    while i < l - 1:
        a = n[i]
        b = n[i + 1]

        if a < b:
            c = (a, b)
        else:
            c = (b, a)

        for m in C:
            if m == c:
                break
        else:
            return False
        i += 1
    return True

N, M = map(int, input().split())
C = []
i = 0
while i < N:
    C += [tuple(map(int, input().split()))]
    i += 1

i = 0
l = range(1, N + 1)
for n in itertools.permutations(l, N):
    if n[0] != 1:
        break
    if path(n) == True:
        i += 1
print(i)

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
const int INF = 2000000000;
using namespace std;

int n;
int ans = 0;

void dfs(int c, int u, vector<bool> used, bool M[10][10]){
    if(u == n - 1){
        ans++;
        return;
    }
    rep(i,n){
        if(M[c][i] == 1 && used[i] == false){
            used[c] = true;
            dfs(i,u + 1,used,M);
        }
    }
}

int main(){
    int m;
    vector<bool> used(10);
    bool M[10][10] = {0};
    cin >> n >> m;
    rep(i,m){
        int a,b;
        cin >> a >> b;
        a--; b--;
        M[a][b] = M[b][a] = 1;
    }
    dfs(0,0,used,M);
    cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
const int INF = 2000000000;
using namespace std;

int n;
int ans = 0;
bool M[10][10] = {0};

void dfs(int c, int u, vector<bool> used){
    if(u == n - 1) ans++;
    rep(i,n){
        if(M[c][i] == 1 && used[i] == false){
            used[c] = true;
            dfs(i,u + 1,used);
        }
    }
}

int main(){
    int m;
    vector<bool> used(10);
    cin >> n >> m;
    rep(i,m){
        int a,b;
        cin >> a >> b;
        a--; b--;
        M[a][b] = M[b][a] = 1;
    }
    dfs(0,0,used);
    cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
const int INF = 2000000000;
using namespace std;

int n,M[10][10];
int ans = 0;

void dfs(int c, int u, vector<bool> used){
    if(u == n - 1) ans++;
    rep(i,n){
        if(M[c][i] == 1 && used[i] == false){
            used[c] = true;
            dfs(i,u + 1,used);
        }
    }
}

int main(){
    int m;
    vector<bool> used(10);
    cin >> n >> m;
    rep(i,m){
        int a,b;
        cin >> a >> b;
        a--; b--;
        M[a][b] = M[b][a] = 1;
    }
    dfs(0,0,used);
    cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
from itertools import permutations as perm

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

path = [[False] * n for _ in range(n)]
for i in range(n):
    path[i][i] = True

for _ in range(n):
    ai, bi = map(int, input().split())
    a, b = ai - 1, bi -1
    path[a][b] = True
    path[b][a] = True

ans = 0
for ps in perm(range(1, n)):
    fst = ps[0]
    if not path[0][fst]:
        continue
    check = [path[i][j] for (i, j) in zip(ps, ps[1:])]
    if all(check):
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
_N,_M=input().split()
N = int(_N)
M = int(_M)
l = []
for i in range(0,M):
    _p, _q = input().split()
    l.append((int(_p),int(_q)))
_A,_B=zip(l)

A=_A+_B
B=_B+_A


def gen_get_to(_fr):
    global A
    global B
    global nodes
    global step
    for itr in range(0,len(A)):
        if A[itr]==_fr:
            if not B[itr] in nodes[0:step]:
                yield B[itr]

def move(): #returns whether "move" succeeded or not
    global nodes
    global possible_memo
    global step
    global counter
    global N
    global end_flag
    try:
        _=next(possible_memo[step])
        nodes[step+1]=_
        step+=1
        #print("success move to {}".format(nodes[step]))
        #print("map: {}".format(nodes[0:step+1]))
        #print("I am at {}th node".format(step+1))
        if step==N-1:
            counter+=1
            #print('REACHED GOAL!!!')
        possible_memo[step]=gen_get_to(nodes[step])
    except StopIteration:
        step-=1
        #print("failed to move")
        if not step==-1:
            pass#print("map: {}".format(nodes[0:step+1]))
            #print("I am at {}th node".format(step+1))
        if step==-1:
            #print("I fell from the first node")
            end_flag=True

nodes=[0]*N
possible_memo=[0]*N
counter=0
step=0
nodes[step]=1
possible_memo[step]=gen_get_to(nodes[0])
end_flag=False

while not end_flag:
    move()


print(counter)

Submission status: Runtime Error

Solution code:
_N,_M=input().split()
N = int(_N)
M = int(_M)
l = []
for i in range(0,M):
    _p, _q = input().split
    l.append((int(_p),int(_q)))
_A,_B=zip(l)

A=_A+_B
B=_B+_A


def gen_get_to(_fr):
    global A
    global B
    global nodes
    global step
    for itr in range(0,len(A)):
        if A[itr]==_fr:
            if not B[itr] in nodes[0:step]:
                yield B[itr]

def move(): #returns whether "move" succeeded or not
    global nodes
    global possible_memo
    global step
    global counter
    global N
    global end_flag
    try:
        _=next(possible_memo[step])
        nodes[step+1]=_
        step+=1
        #print("success move to {}".format(nodes[step]))
        #print("map: {}".format(nodes[0:step+1]))
        #print("I am at {}th node".format(step+1))
        if step==N-1:
            counter+=1
            #print('REACHED GOAL!!!')
        possible_memo[step]=gen_get_to(nodes[step])
    except StopIteration:
        step-=1
        #print("failed to move")
        if not step==-1:
            pass#print("map: {}".format(nodes[0:step+1]))
            #print("I am at {}th node".format(step+1))
        if step==-1:
            #print("I fell from the first node")
            end_flag=True

nodes=[0]*N
possible_memo=[0]*N
counter=0
step=0
nodes[step]=1
possible_memo[step]=gen_get_to(nodes[0])
end_flag=False

while not end_flag:
    move()


print(counter)

Submission status: Runtime Error

Solution code:
N,M=input().split()
l = []
for i in range(0,M):
    l.append(input())
_A,_B=zip(l)

A=_A+_B
B=_B+_A


def gen_get_to(_fr):
    global A
    global B
    global nodes
    global step
    for itr in range(0,len(A)):
        if A[itr]==_fr:
            if not B[itr] in nodes[0:step]:
                yield B[itr]

def move(): #returns whether "move" succeeded or not
    global nodes
    global possible_memo
    global step
    global counter
    global N
    global end_flag
    try:
        _=next(possible_memo[step])
        nodes[step+1]=_
        step+=1
        #print("success move to {}".format(nodes[step]))
        #print("map: {}".format(nodes[0:step+1]))
        #print("I am at {}th node".format(step+1))
        if step==N-1:
            counter+=1
            #print('REACHED GOAL!!!')
        possible_memo[step]=gen_get_to(nodes[step])
    except StopIteration:
        step-=1
        #print("failed to move")
        if not step==-1:
            pass#print("map: {}".format(nodes[0:step+1]))
            #print("I am at {}th node".format(step+1))
        if step==-1:
            #print("I fell from the first node")
            end_flag=True

nodes=[0]*N
possible_memo=[0]*N
counter=0
step=0
nodes[step]=1
possible_memo[step]=gen_get_to(nodes[0])
end_flag=False

while not end_flag:
    move()


print(counter)

Submission status: Runtime Error

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(m-2):
            if a[i] not in d[a[i+1]]:
                f = False
                break
        if f:
            r += 1

    return r


print(main())

Submission status: Runtime Error

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


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: Runtime Error

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(m)]
    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()