[acwing] 909. Chess game

Title address ：

https://www.acwing.com/problem/content/911/

Given a directed acyclic graph as a chessboard , There are... On the chessboard $M$ A chess piece , Multiple pieces can be placed on the same point in the chessboard . Two players play games on the chessboard , Each player needs to move any piece along a directed edge to any point adjacent to it every round . When it's a player's turn , If the player cannot move any pieces , It is regarded as a game failure . Will you be the first to win .

Input format ：
The first line contains integers $N$, There are... In the diagram $N$ A little bit .
Next $N$ That's ok , Each line contains several integers , The first integer $X_i$ Indicates from number $i$ The number of directed edges starting from the point of , Next $X_i$ A number represents the end of each directed edge .
The number of the point is $0$ To $N-1$, Above $N$ Row data is introduced in sequence by $0\sim N-1$ The number of directed edges starting from point No. and the end point of each edge .
The next few lines are asking , Each line first contains an integer $M$, Indicates the number of pieces in a group of queries , Next it contains $M$ It's an integer , Express $M$ The number of the initial point where the pieces are located .
The last line is an integer $0$, End of input .

Output format ：
Each group of inquiry outputs a result , Each result takes up one line , If you win first, you will output WIN, Otherwise output LOSE.

Data range ：
$1\le N\le 10000$
$1\le M\le 10$
The data guarantees that the number of edges in the graph will not exceed $10^5$ strip .
The number of inquiries will not exceed $10000$ Time .

It can be used SG Functions do . Reference resources https://blog.csdn.net/qq_46105170/article/details/114006814. For the digraph of this problem , You can find out the of each point first SG Function value , Because the pieces are independent of each other , It can be seen as $M$ Two independent games are playing at the same time , So by the SG Theorem , Just put the initial position of all the pieces SG Function to do XOR , If it's not zero , First hand wins , Otherwise, we will lose first . The code is as follows ：

#include <iostream>
#include <cstring>
#include <unordered_set>
using namespace std;

const int N = 10010, M = N * 10;
int n, m;
int h[N], e[M], ne[M], idx;
int f[N];

void add(int a, int b) {
    
  e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int sg(int x) {
    
  if (~f[x]) return f[x];
  unordered_set<int> st;
  for (int i = h[x]; ~i; i = ne[i])
    st.insert(sg(e[i]));
  
  for (int i = 0;; i++)
    if (!st.count(i)) 
      return f[x] = i; 
}

int main() {
    
  memset(h, -1, sizeof h);
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    
    scanf("%d", &m);
    while (m--) {
    
      int x;
      scanf("%d", &x);
      add(i, x);
    }
  }

  memset(f, -1, sizeof f);
  while (cin >> m, m) {
    
    int res = 0;
    while (m--) {
    
      int x;
      scanf("%d", &x);
      res ^= sg(x);
    }

    res ? puts("WIN") : puts("LOSE");
  }
}

Preprocessing time complexity $O(NM)$（ Can calculate SG The time of the function is counted as preprocessing ）, The time complexity of each inquiry $O(M)$, Space $O(NM)$.