Sprague-Grundy Theorem

1. Find a topological order of the DAG.
2. Process vertices in reverse topological order:
   1. Mark the Grundy values of all outgoing neighbors.
   2. Set sg[v] to the smallest unmarked non-negative integer.
3. Set xor_sum = 0.
4. For every starting token at v, xor sg[v] into xor_sum.
5. The first player wins exactly when xor_sum is nonzero.

#include <bits/stdc++.h>

#define fi first
#define se second

using namespace std;

const int N = 200200;

int n, m;
int indeg[N], sg[N];
vector<int> g[N];

void solve() {
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int v, u;
        cin >> v >> u;
        g[v].push_back(u);
        indeg[u]++;
    }

    queue<int> q;
    for (int v = 1; v <= n; v++) {
        if (indeg[v] == 0) {
            q.push(v);
        }
    }

    vector<int> order;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        order.push_back(v);

        for (int u : g[v]) {
            indeg[u]--;
            if (indeg[u] == 0) {
                q.push(u);
            }
        }
    }

    for (int at = n - 1; at >= 0; at--) {
        int v = order[at];
        vector<bool> seen(g[v].size() + 1);
        for (int u : g[v]) {
            if (sg[u] < (int)seen.size()) {
                seen[sg[u]] = true;
            }
        }
        while (sg[v] < (int)seen.size() && seen[sg[v]]) {
            sg[v]++;
        }
    }

    int k;
    cin >> k;

    int xr = 0;
    while (k--) {
        int v;
        cin >> v;
        xr ^= sg[v];
    }

    cout << (xr != 0 ? "FIRST\n" : "SECOND\n");
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    solve();

    return 0;
}

Introduction

Problem or motivation

Core concept

Hall's Theorem

Main algorithm

Mental model and detailed walkthrough

Implementation

Common mistakes

Complexity