# 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;
}
```