题目链接：传送门
题目大意：
在一个有N个点的拓扑图上（拓扑图以邻接表的形式输入），放M个棋子（棋子与棋子之间无关，可以重合）。
两人轮流移动棋子，每次只能移动一个棋子经过一条边。
问先手是否必胜。
思路：
因为图是确定的，而且是拓扑图，直接沿着边跑记忆化dfs求每个点的SG值就可以了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <set> using namespace std;
const int MAX_N = ; int N, M;
int Edge[MAX_N][MAX_N];
int SG[MAX_N]; int dfs(int u)
{
if (SG[u] >= )
return SG[u];
bool vis[MAX_N];
memset(vis, false, sizeof vis);
for (int i = ; i <= Edge[u][]; i++) {
int v = Edge[u][i];
int x = dfs(v);
vis[x] = true;
}
int g = ;
while (vis[g])
g++;
return SG[u] = g;
} int main()
{
while (~scanf("%d", &N)) {
for (int i = ; i < N; i++) {
SG[i] = -;
scanf("%d", &Edge[i][]);
for (int j = ; j <= Edge[i][]; j++) {
scanf("%d", &Edge[i][j]);
}
}
for (int i = ; i < N; i++)
dfs(i); while (~scanf("%d", &M)) {
if (M == )
break;
int ans = ;
while (M--) {
int cur;
scanf("%d", &cur);
ans ^= SG[cur];
}
if (ans)
puts("WIN");
else
puts("LOSE");
}
}
return ;
}