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 bit_dp(N, Adj):
    dp = [[0]*N for i in range(1 << N)]
    #dp[{0},0] = 1

    dp[1][0] = 1

    for S in range(1 << N):
        for v in range(N):
            
            if (S & (1 << v)) == 0:
                continue

            
            sub = S ^ (1 << v)

            for u in range(N):
                
                if (sub & (1 << u)) and (Adj[u][v]):
                    dp[S][v] += dp[sub][u]
        ans = sum(dp[(1 << N) - 1][u] for u in range(1, N))
        return ans


def main():
    N, M = map(int, input().split())
    Adj = [[False]*N for _ in range(N)]

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

    print(ans)


if __name__ == '__main__':
    main()


def bit_dp(N, Adj):
    dp = [[0]*N for i in range(1 << N)]
    #dp[{0},0] = 1

    dp[1][0] = 1

    for S in range(1 << N):
        for v in range(N):
            
            if (S & (1 << v)) == 0:
                continue

            
            sub = S ^ (1 << v)

            for u in range(N):
                
                if (sub & (1 << u)) and Adj[u][v]:
                    dp[S][v] += dp[sub][u]
        ans = sum(dp[(1 << N) - 1][u] for u in range(1, N))
        return ans


def main():
    N, M = map(int, input().split())
    Adj = [[False]*N for _ in range(N)]

    for _ in range(M):
        a, b = map(int, input().split())
        Adj[a-1][b-1] = True
        Adj[b-1][a-1] = True
    ans = bit_dp(N, Adj)

    print(ans)


if __name__ == '__main__':
    main()


def bit_dp(N, Adj):
    dp = [[0]*N for i in range(1 << N)]
    #dp[{0},0] = 1

    dp[1][0] = 1

    for S in range(1 << N):
        for v in range(N):
            
            if (S & (1 << v)) == 0:
                continue

            
            sub = S ^ (1 << v)

            for u in range(N):
                
                if (sub & (1 << u)) and (Adj[u][v]):
                    dp[S][v] += dp[sub][u]
    ans = sum(dp[(1 << N) - 1][u] for u in range(1, N))
    return ans


def main():
    N, M = map(int, input().split())
    Adj = [[False]*N for _ in range(N)]

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

    print(ans)


if __name__ == '__main__':
    main()


Verdicts: Wrong Answer

Wrong Answer

Accepted