【題目敘述】https://tioj.ck.tp.edu.tw/problems/1092
【解題想法】反向(?)拓撲排序 (Topological sorting)
- 舉例如下圖，9個圓圈，編號1到9，並規定1號圓圈是起點、9號是終點。走到9號圓圈者為贏家。
- 有箭頭從 a 指向 b時，表示b的上一層有a，pre[b] = a。
- a的「出邊」要多加一條，out[a]++。
- 下圖8號圓圈的「出邊」只有一條，因此可以決定走到8號圓圈者為輸家。
- 由此類推，走到6號圓圈和7號圓圈者為贏家。
- 繼續類推到1號圓圈，可以知道先開始的人贏或輸。
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int maxn = 1e4;
int n, e, out[maxn], winner[maxn], now, a, b;
vector <int> pre[maxn];
string player1;
int main() {
while (cin >> n >> e){
if (n == 0 && e == 0) break;
memset(out, 0, sizeof(out));
memset(winner, 0, sizeof(winner));
for (int i = 0; i < n; i++){
pre[i].clear();
}
for (int i = 0; i < e; i++){
cin >> a >> b;
pre[b-1].push_back(a-1);
out[a-1]++;
}
queue <int> q;
q.push(n-1);
winner[n-1] = 0;
while (!q.empty()){
now = q.front();
q.pop();
for (int i:pre[now]){
out[i]--;
if (winner[now] == 0) winner[i] = 1;
if (out[i] == 0) q.push(i);
}
}
cin >> player1;
if (player1 == "Mimi") winner[0] ^= 1;
if (winner[0]) cout << "Mimi\n";
else cout << "Moumou\n";
}
return 0;
}