HDU 2181 哈密頓繞行世界問題：DFS 找所有哈密頓回路

問題描述

正十二面體 20 頂點對應 20 城市，每頂點度為 3。給定鄰接表，從城市 m 出發，經過每城市恰好一次回到 m，輸出所有路徑（字典序）。

解題思路

標準 DFS 回溯：

• 圖固定 20 點，每點度 3，搜索空間極小。
• 遞歸參數：當前城市 o、已走步數 n、起點 q。
• 到達第 19 步且下一鄰接點為起點時，輸出路徑。
• 鄰接表輸入順序即字典序，直接按輸入順序遍歷鄰接點即可保證輸出字典序。

代碼實現

#include 
#include 
using namespace std;
int mat[25][3], a[25], vis[25], m, cnt;

void dfs(int o, int n, int q) {
    a[n] = o; vis[o] = 1;
    for (int i = 0; i < 3; ++i) {
        int s = mat[o][i];
        if (n == 19 && s == q) {
            printf("%d: ", ++cnt);
            for (int j = 0; j < 20; ++j) printf("%d ", a[j]);
            printf("%d\n", m);
        }
        if (!vis[s]) dfs(s, n+1, q);
    }
    vis[o] = 0;
}

int main() {
    for (int i = 1; i <= 20; ++i) scanf("%d%d%d", &mat[i][0], &mat[i][1], &mat[i][2]);
    while (scanf("%d", &m) && m) {
        cnt = 0; memset(vis, 0, sizeof(vis));
        dfs(m, 0, m);
    }
    return 0;
}

關鍵點

• 輸入以 0 結束，多組測試數據。
• 路徑長度固定 21（含首尾相同起點）。
• 無需額外排序，輸入鄰接順序即字典序。
• 時間限制寬鬆，純 DFS 即可 AC。