The naive dynamic programming approach for Hamiltonian path and circuit problems typically runs in O(n!) time, or O(2ⁿ n³) using standard bitmask DP. We will optimize this bitmask DP framework to achieve O(2ⁿ n) time complexity and O(2ⁿ) space complexity.

The baseline bitmask DP uses the state dp[S][u][v], which denotes whether a path exists from node u to node v that visits exactly the set of nodes represented by bitmask S. This state is highly redundant, so we can apply a bitset-based optimizatoin: collapse the v dimension into a bitmask, resulting in the state dp[S][u], where dp[S][u] is a bitmask of all valid end nodes v such that a path starting at u, covering exactly the nodes in S, exists. We precompute an adjacency bitmask array adj where adj[v] has the i-th bit set if there is an undirected edge between nodes v and i. The transition condition simplifies to checking if (adj[v] & dp[S][u]) != 0, reducing the time complexity to O(2ⁿ n²) and space complexity to O(2ⁿ n).

Route 1: Circuit-Focused Optimization

This approach targets Hamiltonian circuit problems, with a key optimization to eliminate the starting node dimension entirely. We fix the starting node as the smallest index present in the current bitmask S, which removes the need to track the starting node u in the DP state. The revised DP state is now just dp[S], a bitmask of valid end nodes for paths starting at the minimal node in S and covering exactly S.

For path reconstruction, we avoid the O(n) extra space cost of storing predecessor pointers for every state. Instead, we use bitwise operations and __builtin_ctz (count trailing zeros) to trace back the path on demand during output.

Sample Implementation

#include <bits/stdc++.h>
#define FAST_IO ios::sync_with_stdio(false); cin.tie(nullptr)
using namespace std;

template<typename T = int>
T read() {
    char c = getchar(); T x = 0;
    while (c < '0' || c > '9') c = getchar();
    do x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    while (c >= '0' && c <= '9');
    return x;
}

int main() {
    FAST_IO;
    int total_nodes = read(), edge_count = read();
    vector<int> adj_mask(total_nodes, 0);
    for (int i = 0; i < edge_count; ++i) {
        int u = read() - 1, v = read() - 1;
        adj_mask[u] |= 1 << v;
        adj_mask[v] |= 1 << u;
    }

    vector<int> dp(1 << total_nodes, 0);
    for (int i = 0; i < total_nodes; ++i) {
        dp[1 << i] = 1 << i;
    }

    for (int mask = 1; mask < (1 << total_nodes); ++mask) {
        int start_node = __builtin_ctz(mask);
        for (int curr = start_node + 1; curr < total_nodes; ++curr) {
            if (!(mask & (1 << curr))) continue;
            if (dp[mask] & adj_mask[curr]) {
                dp[mask | (1 << curr)] |= 1 << curr;
            }
        }

        if (dp[mask] & adj_mask[start_node]) {
            bool valid_circuit = true;
            for (int i = 0; i < total_nodes; ++i) {
                if (mask & (1 << i)) continue;
                if (adj_mask[i] & mask) continue;
                valid_circuit = false;
                break;
            }
            if (valid_circuit) {
                cout << "Yes\n";
                vector<int> path(total_nodes);
                vector<int> trace_stack;
                int curr = __builtin_ctz(dp[mask] & adj_mask[start_node]);
                int temp_mask = mask;
                while (temp_mask ^= 1 << curr) {
                    trace_stack.push_back(curr);
                    curr = __builtin_ctz(dp[temp_mask] & adj_mask[curr]);
                }
                trace_stack.push_back(curr);
                for (int i = 1; i < trace_stack.size(); ++i) {
                    path[trace_stack[i-1]] = trace_stack[i];
                }
                path[trace_stack.back()] = trace_stack[0];
                for (int i = 0; i < total_nodes; ++i) {
                    cout << path[i] + 1 << " ";
                }
                cout << "\n";
                return 0;
            }
        }
    }
    cout << "No\n";
    return 0;
}

This approach is optimized specifically for Hamiltonian circuits, and is less straightforward to adapt for general Hamiltonian path problems. The following Route 2 offers a more general solution that works for both path and circuit cases.

Route 2: General-Purpose Optimization

This approach works for both Hamiltonian path and circuit problems, avoiding the overhead of running a separate DP for each starting node. We only run the DP once, starting from node 0, storing start0_dp[S] as a bitmask of valid end nodes for paths strating at 0 and covering exactly the nodes in S.

To check all valid u-v Hamiltonian paths, we split the full node mask into two disjoint subsets: one subset containing 0 and u, the other containing 0 and v, such that their union is all nodes and their intersection is exactly {0}. Enumerating these subsets allows us to compute a matrix indicating whether a valid Hamiltonian path exists between any pair of nodes.

Sample Implementation

#include <cstdio>
#include <vector>
using namespace std;

int main() {
    int total_nodes;
    scanf("%d", &total_nodes);
    vector<int> adj_mask(total_nodes, 0);
    char buffer[30];
    for (int i = 0; i < total_nodes; ++i) {
        scanf("%s", buffer);
        for (int j = 0; j < total_nodes; ++j) {
            adj_mask[i] |= (buffer[j] == '1') << j;
        }
    }

    vector<int> start0_dp(1 << total_nodes, 0);
    start0_dp[1] = 1;
    for (int mask = 1; mask < (1 << total_nodes); mask += 2) {
        if (!start0_dp[mask]) continue;
        for (int curr = 1; curr < total_nodes; ++curr) {
            if (mask & (1 << curr)) continue;
            if (start0_dp[mask] & adj_mask[curr]) {
                start0_dp[mask | (1 << curr)] |= 1 << curr;
            }
        }
    }

    vector<int> path_matrix(total_nodes, 0);
    const int full_mask = (1 << total_nodes) - 1;
    for (int mask = 1; mask < (1 << total_nodes); mask += 2) {
        if (!start0_dp[mask]) continue;
        int complement = full_mask ^ mask;
        for (int u = 0; u < total_nodes; ++u) {
            if (start0_dp[mask] & (1 << u)) {
                path_matrix[u] |= start0_dp[complement];
            }
        }
    }

    for (int u = 0; u < total_nodes; ++u) {
        for (int v = 0; v < total_nodes; ++v) {
            putchar((path_matrix[u] & (1 << v)) ? '1' : '0');
        }
        putchar('\n');
    }
    return 0;
}