HDU 1524 A Chess Game：有向無環圖上的 SG 函數博弈

題目背景

N 個位置構成有向無環圖（DAG），M 枚棋子分佈在各位置。雙方輪流移動一枚棋子沿有向邊到後繼位置。無法移動者負。多枚棋子獨立，屬於組合遊戲，需用 SG 函數（Sprague-Grundy） 求解。

核心理論

• SG 函數定義： `sg(u) = mex{ sg(v) | (u,v) 是邊 }`，mex 為最小未出現非負整數。
• 和遊戲定理： 多獨立子遊戲組合，先手必勝 ⟺ 所有子遊戲 SG 值異或和 ≠ 0。
• DAG 上計算 SG： 拓撲序逆序 DP，或帶備忘錄的 DFS。

算法實現 (C++)

#include 
#include 
#include 
using namespace std;

const int MAXN = 1005;
vector G[MAXN];
int sg[MAXN], indeg[MAXN];
int n;

int getSG(int u) {
    if (sg[u] != -1) return sg[u];
    bool vis[MAXN] = {false};
    for (int v : G[u]) vis[getSG(v)] = true;
    for (int i = 0; ; i++) if (!vis[i]) return sg[u] = i;
}

int main() {
    while (~scanf("%d", &n)) {
        for (int i = 0; i < n; i++) { G[i].clear(); indeg[i] = 0; }
        for (int i = 0; i < n; i++) {
            int cnt; scanf("%d", &cnt);
            while (cnt--) { int v; scanf("%d", &v); G[i].push_back(v); indeg[v]++; }
        }
        memset(sg, -1, sizeof(sg));
        // 從入度為0的節點開始遞歸計算（或任意節點，備忘錄自動處理依賴）
        for (int i = 0; i < n; i++) if (indeg[i] == 0) getSG(i);

        int m;
        while (scanf("%d", &m) && m) {
            int xorsum = 0;
            while (m--) { int pos; scanf("%d", &pos); xorsum ^= sg[pos]; }
            puts(xorsum ? "WIN" : "LOSE");
        }
    }
    return 0;
}

避坑指南

• 多測試用例初始化： `G`, `sg`, `indeg` 每輪必須清空。
• 圖可能不連通： 需對所有入度為 0 的節點調用 `getSG`，確保覆蓋所有節點。
• 遞歸深度： N ≤ 1000，遞歸棧通常安全；如擔心可改迭代拓撲序 DP。