TIOJ 1092 跳格子遊戲 ( DP + Game theory )

1092 - A.跳格子遊戲 | TIOJ INFOR Online Judge
看網上大家都是寫拓撲排序逆著遞推，我覺得沒必要。另外我換了一下題意，因為事實上第一個動作的是初期的後手，所以我調換一下，這樣比較容易思考。邊界是當目前這個節點沒有可移動的，就代表前一個人已經勝利，那麼現在動手的人就是敗者。如此一來就能利用經典理論當作遞推的依據：
• 若且唯若存在至少一個後繼，是先手必敗，那麼當前的狀態一定是先手必勝
• 若不存在任何後繼，或者所有後繼都是先手必勝，那麼當前的狀態一定是先手必敗

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 4;
const int MAXE = 10 * MAXN;
const int NPWIN = 1;

int n, e;
vector<int> G[ MAXN ];
string player[ 2 ] = { "Mimi", "Moumou" };
string fplayer;

int dp[ MAXN ];

int dfs(int u){
    if( dp[ u ] >= 0 ) return dp[ u ];
    if( G[ u ].empty() ) return dp[ u ] = !NPWIN;
    int has_son_nplose = 0;
    for(int v: G[ u ])
        has_son_nplose |= !dfs( v );
    return dp[ u ] = has_son_nplose; // has_son_nplose -> npwin
}

void solve(){
    memset( dp, -1, sizeof(dp) );
    int ans = dfs( 1 );
    if( ans == NPWIN ) cout << fplayer << endl;
    else if( fplayer != player[ 0 ] )
        cout << player[ 0 ] << endl;
    else
        cout << player[ 1 ] << endl;
}

int main(){
    while( cin >> n >> e && n + e ){
        for(int i = 1; i <= n; ++i)
            G[ i ].clear();
        for(int i = 0; i < e; ++i){
            int a, b; cin >> a >> b;
            G[ a ].push_back( b );
        }
        cin >> fplayer;
        if( fplayer != player[ 0 ] )
            fplayer = player[ 0 ];
        else
            fplayer = player[ 1 ];
        solve();
    }
    return 0;
}