POJ 2599 A funny game：有向圖博弈論（必勝/必敗狀態 DFS）

題目大意

有向圖，兩人從起點 s 輪流移動飛機。離開節點後該節點不可再用。無法移動者負。判斷先手勝負，若勝輸出最小編號獲勝移動目標。

博弈論基礎

• 必敗狀態：當前節點無出邊（或所有出邊指向的節點已用盡）。
• 必勝狀態：存在至少一條出邊指向必敗狀態。
• 圖中節點刪除後不可復用 → 狀態包含「已用節點集」，但 n ≤ 1000 可直接暴力 DFS 搜索遊戲樹。

DFS 搜索策略

1. 從 s 開始，嘗試每條出邊 u→v（按 v 編號升序，保證最小編號優先）。
2. 標記 u 已用，遞歸判斷 v 是否為必敗。
3. 若 v 必敗，則 u 必勝，記錄答案 v 返回。
   若所有 v 均必勝，則 u 必敗。
4. 回溯取消 u 標記。

完整代碼（C++）

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int g[MAXN][MAXN], n, s, ans;
bool used[MAXN];

bool dfs(int u) {
    for (int v = 1; v <= n; ++v) if (g[u][v] && !used[v]) {
        used[u] = true;
        if (!dfs(v)) { used[u] = false; ans = v; return true; }
        used[u] = false;
    }
    return false;
}
int main() {
    while (cin >> n >> s) {
        memset(g,0,sizeof g); memset(used,0,sizeof used);
        for (int i=1,u,v;i>u>>v; g[u][v]=g[v][u]=1;}
        if (dfs(s)) printf("First player wins flying to airport %d\n", ans);
        else puts("First player loses");
    }
    return 0;
}

複雜度

• 時間：O(n!) 理論最壞，但 n≤1000 實測極快（遊戲樹極小，因節點一次只能用一次）。
• 空間：O(n²) 存圖，O(n) 遞歸棧。

關鍵點

1. 無向圖建雙向邊，DFS 遍歷按編號升序保證最小贏法輸出。
2. used[] 標記當前路徑已用節點，回溯清除。
3. 博弈遞歸返回值：true=當前玩家必勝，false=必敗。