Problem: 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

Submission attempts (in order):
def read_input():
    n, m = map(int, input().split())

    edges = []
    nodes = list(range(1, n + 1))

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


    edges_dic = {}
    for i in range(n):
        edges_dic[i + 1] = []

    for edge in edges:
        edges_dic[edge[0]].append(edge[1])
        edges_dic[edge[1]].append(edge[0])

    return n, m, nodes, edges_dic



def check_path(curr_node, rest_nodes, edges_dic, through):
    
    if not rest_nodes:
        return 1

    
    next_nodes = edges_dic[curr_node]
    targets = []
    for n in next_nodes:
        if n in rest_nodes:
            targets.append(n)

    
    if not targets:
        return 0

    
    count = 0
    for t in targets:
        new_rest = [r for r in rest_nodes if r != t]
        new_through = through + [curr_node]
        count += check_path(t, new_rest, edges_dic, new_through)

    return count



def submit():
    n, m, nodes, edges_dic = read_input()

    rest_nodes = [r for r in nodes if r != 1]
    print(check_path(1, rest_nodes, edges_dic, []))





def read_input():
    n, m = map(int, input().split())

    edges = []
    nodes = list(range(1, n + 1))

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


    edges_dic = {}
    for i in range(n):
        edges_dic[i + 1] = []

    for edge in edges:
        edges_dic[edge[0]].append(edge[1])
        edges_dic[edge[1]].append(edge[0])

    return n, m, nodes, edges_dic



def check_path(curr_node, rest_nodes, edges_dic, through):
    
    if not rest_nodes:
        return 1

    
    next_nodes = edges_dic[curr_node]
    targets = []
    for n in next_nodes:
        if n in rest_nodes:
            targets.append(n)

    
    if not targets:
        return 0

    
    count = 0
    for t in targets:
        new_rest = [r for r in rest_nodes if r != t]
        new_through = through + [curr_node]
        count += check_path(t, new_rest, edges_dic, new_through)

    return count


def submit():
    n, m, nodes, edges_dic = read_input()

    rest_nodes = [r for r in nodes if r != 1]
    paths = check_path(1, rest_nodes, edges_dic, [])
    print(paths)


if __name__ == '__main__':
    submit()


Verdicts: Wrong Answer

Accepted