UVA 539 卡坦島的殖民者：最長道路問題的 DFS 解法

UVA 539「卡坦島的殖民者」要求在無向圖中尋找不重複邊的最長路徑（節點可重複訪問）。節點度數 ≤ 3，邊長均為 1。本文介紹基於深度優先搜索（DFS）的暴力回溯解法，利用圖的稀疏性高效求解。

問題建模

• 給定 n 個節點（0 ~ n-1），m 條無向邊。
• 尋找最長路徑，邊不可重複使用，節點可重複訪問。
• 圖不一定連通，n ≤ 25，m ≤ 25（度數 ≤ 3 隱含）。

DFS 回溯策略

由於邊數較少（≤ 25），可從每條邊作為起點，嘗試所有可能的路徑延伸：

1. 維護訪問標記 vis[u][v] 表示邊 (u,v) 是否已用。
2. 從每條邊 (u,v) 開始，標記已用，遞歸從 v 繼續延伸。
3. 遞歸函數 DFS(cur, len)：遍歷 cur 的所有鄰居 next，若邊 (cur,next) 未用，標記後遞歸 DFS(next, len+1)，回溯時取消標記。
4. 全局記錄最大長度 ans。

關鍵優化

• 從每條邊雙向嘗試：對每條邊 (u,v)，分別以 u 和 v 為起點調用 DFS，確保覆蓋所有路徑起點。
• 度數限制天然剪枝：節點度數 ≤ 3，分支因子極小，搜索空間可控。
• 無需記憶化：狀態包含當前節點和已用邊集合，狀態數過大，直接回溯更簡潔。

代碼實現（C++）

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

const int MAXN = 30;
int g[MAXN][MAXN];
int vis[MAXN][MAXN];
int n, m, ans;

void DFS(int u, int len) {
    for (int v = 0; v < n; ++v) {
        if (g[u][v] && !vis[u][v]) {
            vis[u][v] = vis[v][u] = 1;
            DFS(v, len + 1);
            vis[u][v] = vis[v][u] = 0;
        }
    }
    if (len > ans) ans = len;
}

int main() {
    while (scanf("%d%d", &n, &m) == 2 && (n || m)) {
        memset(g, 0, sizeof(g));
        memset(vis, 0, sizeof(vis));
        for (int i = 0; i < m; ++i) {
            int a, b;
            scanf("%d%d", &a, &b);
            g[a][b] = g[b][a] = 1;
        }
        ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (g[i][j]) {
                    vis[i][j] = vis[j][i] = 1;
                    DFS(i, 1);
                    vis[i][j] = vis[j][i] = 0;
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

複雜度分析

最壞情況每條邊作為起點，DFS 探索所有歐拉路徑變體。邊數 m ≤ 25，度數 ≤ 3，實際運行極快。時間複雜度約 O(m × 2^m) 但常數極小，完全在限制內。

總結

本題是「圖中最長路徑（邊不重複）」的經典應用。利用題目約束（稀疏圖、低度數），簡單的 DFS 回溯即可高效求解，無需複雜的動態規劃或狀態壓縮。這體現了「根據數據範圍選擇算法」的實用原則。