題目連結: https://tioj.ck.tp.edu.tw/problems/1085
# 內容
Mimi, Moumou 兩人是青梅竹馬，從小就玩在一起（雖然他們現在也才小學三年級而已）。愛玩的兩人，平常的遊戲玩久了之後就覺得無聊沒勁，常常湊在一起發明新的遊戲。
這天他們又開始在設計新遊戲了，遊戲的規則如下：
先在地上畫 N 個圓圈，編號 1 到 N，並規定 1 號圓圈是起點、N 號是終點
在這 N 個圓圈之間任意互相畫” 單向” 箭頭，箭頭起點和終點各有一圓圈且兩圓圈不為同一圓，假設有一箭頭從圓 a 連到圓 b，則遊戲中可以從 a 跳到 b。
檢查 1, 2 步驟所畫出的圖，確保任何編號 1 ~ N-1 的圓都有路徑可以走到終點，同時圖中也不可以有迴圈產生（也就是對於任何一個圓，絕對不會有路徑可以從自己走到自己），對任兩圓 a, b 最多只有一個箭頭從 a 指向 b。
兩個人進行遊戲，開始時先由一人站在起點（1 號圓），另一個人站在圖外。
遊戲中假設甲站在一個圓 C 中而乙在圖外，則乙要從 C 所指出去的箭頭中選一個箭頭，站到這個箭頭所指的圓上，然後甲則離開 C 走到圖外。
兩人重複步驟 5 的動作，直到其中一人到達終點，到達終點的人為贏家。
# 解題思路
只需要管該點是先手贏或後手贏，那顯然最後一點是先手贏，而連到最後一點的都輸，所以可以導出該點一定跟他下一點相反，而如果前面的點有必勝的點，那對方也一定走過去，所以只要看他連到的點有沒有必勝的，若有自己就必輸，若無則自己必贏，所以 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(){ | |
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]; | |
} | |
int main(){ | |
cin>>n>>e; | |
while(n+e!=0){ | |
init(); | |
while(e--){ | |
int a,b; | |
cin>>a>>b; | |
graph[a].push_back(b); | |
} | |
isset[n]=1; | |
val[n]=1; | |
dfs(1); | |
string name; | |
cin>>name; | |
if((!val[1] && name[1]=='i') || (val[1] && name[1]=='o')) | |
puts("Moumou"); | |
else | |
puts("Mimi"); | |
cin>>n>>e; | |
} | |
return 0; | |
} |
