[TIOJ] 1092. A.跳格子遊戲

題目連結:http://tioj.infor.org/problems/1092

---

本題是個對稱遊戲，所以應該只需要管該點是先手贏或後手贏，那顯然最後一點是先手贏，而連到最後一點的都輸，所以可以導出該點一定跟他下一點相反，而如果前面的點有必勝的點，那對方也一定走過去，所以只要看他連到的點有沒有必勝的，若有自己就必輸，若無則自己必贏，所以DFS一遍就可以解決了XD

#include <bits/stdc++.h>
using namespace std;
#define N 10000

vector<int> graph[N+10];
int n,e;
bitset<N+10> isset;
bitset<N+10> val;

inline void init();
bool dfs(int);

int main(){
	scanf("%d%d",&n,&e);
	while(n+e!=0){
		init();
		while(e--){
			int a,b;
			scanf("%d%d",&a,&b);
			graph[a].push_back(b);
		}
		isset[n]=1;
		val[n]=1;
		dfs(1);
		char name[7];
		scanf("%s",name);
		if((!val[1] && name[1]=='i') || (val[1] && name[1]=='o'))
			puts("Moumou");
		else
			puts("Mimi");
		scanf("%d%d",&n,&e);
	}
	return 0;
}

inline void init(){
	for(int i=0;i<n;i++)graph[i+1].clear();
	isset.reset();
	val.reset();
}

bool dfs(int w){
	if(!isset[w]){
		bool ans=1;
		for(auto i : graph[w]){
			ans&=dfs(i);
		}
		val[w]=ans;
		isset[w]=1;
	}
	return !val[w];
}