UVA 539 The Settlers of Catan——回溯 DFS 求無向圖最長路徑

問題描述

無向圖 n≤25 點，m 條邊。每條邊最多用一次。求最長路徑（邊數最多）的長度。多測試用例，`0 0` 結束。

回溯 DFS

• 從每個點作為起點 DFS。
• 遞歸 `dfs(u, len)`：嘗試所有未用邊 `(u,v)`，標記用過，遞歸 `dfs(v, len+1)`，回溯取消標記。
• 維護全局 `maxLen`。
• 優化：若某點度為 1，作為起點可能更優（但 n≤25 全點起點 DFS 也極快）。

代碼實現

#include 
using namespace std;
const int MAXN = 30;
bool adj[MAXN][MAXN];
int n, m, maxLen;

void dfs(int u, int len) {
    maxLen = max(maxLen, len);
    for (int v = 0; v < n; ++v) if (adj[u][v]) {
        adj[u][v] = adj[v][u] = false;
        dfs(v, len + 1);
        adj[u][v] = adj[v][u] = true;
    }
}

int main() {
    while (cin >> n >> m, n || m) {
        memset(adj, 0, sizeof(adj));
        for (int i = 0; i < m; ++i) {
            int u, v; cin >> u >> v;
            adj[u][v] = adj[v][u] = true;
        }
        maxLen = 0;
        for (int i = 0; i < n; ++i) dfs(i, 0);
        cout << maxLen << '\n';
    }
    return 0;
}

關鍵點

• 邊用過標記：鄰接矩陣 `bool`，去邊/回邊 O(1)。
• 全點起點：n≤25，25 次 DFS 總狀態數極小（圖稀疏時更少）。
• 無向圖：`adj[u][v]=adj[v][u]` 同步更新。
• 路徑長度 = 邊數：`len` 遞增 1 對應走過一條邊。

複雜度

• 最壞 O(n!) 但 n≤25 且圖稀疏，實際極快（<0.1s）。
• 空間：O(n²) 鄰接矩陣。

總結

無向圖最長路徑（邊不重複）。回溯 DFS 遍歷所有簡單路徑，n≤25 直接暴力可行。鄰接矩陣標記邊用過/回溯，全點作起點取最大值。經典「小規模圖窮舉」模板。