第一行，三个整数N,M,K，N表示图中节点总数，M表示图中边的条数，K表示棋子的个数。
接下来M行，每行两个整数X,Y表示有一条边从X出发指向Y。
接下来一行，K个空格间隔的整数，表示初始时，棋子所在的节点编号。
若先手胜，输出win，否则输出lose。
6 8 4 2 1 2 4 1 4 1 5 4 5 1 3 3 5 3 6 1 2 4 6
win
对于全部数据，N \leq 2000,M \leq 6000,1 \leq K \leq NN≤2000,M≤6000,1≤K≤N。
// SG函数模板题 #include<bits/stdc++.h> using namespace std; const int MAXM = 1e4 + 7; const int MAXN = 2e3 + 7; int head[MAXM], ver[MAXM], nex[MAXM], vis[MAXM], sg[MAXM], tot; int N, M, K; void add(int x, int y) { ver[++tot] = y; nex[tot] = head[x]; head[x] = tot; } void dfs(int x) { if (vis[x]) return; vis[x] = 1; int up = 0; int mark[MAXN] = {0}; for (int i = head[x]; i; i = nex[i]) { dfs(ver[i]); up = max(up, sg[ver[i]]); mark[sg[ver[i]]] = 1; } for (int i = 0; i <= up + 1; i++) { if (!mark[i]) { sg[x] = i; break; } } } void getSG() { for (int i = 1; i <= N; i++) { if (!vis[i]) dfs(i); } } int main() { int x, y; cin >> N >> M >> K; for (int i = 1; i <= M; i++) { cin >> x >> y; add(x, y); } getSG(); int ans = 0; for (int i = 1; i <= K; i++) { cin >> x; ans ^= sg[x]; } if (ans) cout << "win" << endl; else cout << "lose" << endl; return 0; }
原文：https://www.cnblogs.com/HighLights/p/13363443.html