第二题 我是反向建图然后跑拓扑做dp bool ans[maxn]; vector<int> G[maxn]; int du[maxn]; void solve() { int n, m; cin >> n >> m; string s; for(int i = 1; i <= n; ++i) { ans[i] = true; G[i].clear(); du[i] = 0; } for(int i = 0; i < m; ++i) { int u, v; cin >> u >> v; if(u == n) continue; G[v].push_back(u); ++du[u]; } cin >> s; queue<int> que; que.push(n); while(!que.empty()) { int v = que.front(); que.pop(); bool now = !ans[v]; for(int u : G[v]) { ans[u] = min(ans[u], now); --du[u]; if(du[u] == 0) que.push(u); } } if(s == "Alice") { if(ans[1]) cout << "Alice" << endl; else cout << "Bob" << endl; }else { if(!ans[1]) cout << "Alice" << endl; else cout << "Bob" << endl; } }