Grundy Numbers
(game/grundy.hpp)

• View this file on GitHub
• Last update: 2026-08-24 02:00:33+09:00
• Include: #include "game/grundy.hpp"

Overview

Computes the Sprague-Grundy number of every state in a finite directed acyclic impartial game. An edge v -> u means that a player may move from state v to state u. Terminal states receive Grundy number zero, and every other state receives the minimum excluded Grundy number of its successors.

The xor of the Grundy numbers of independent components is nonzero exactly when their disjoint sum is winning under normal play.

Functions

All functions are in namespace m1une::game.

Function signature	Description	Complexity
template<class Graph> std::vector<int> grundy_numbers(const Graph& graph)	Returns one Grundy number per state. graph[v] lists states reachable from v.	O(V + E) time, O(V) extra space

States and edges are zero-based. Every endpoint must be in [0, V), and the graph must be acyclic; both conditions are asserted in debug builds. Parallel edges are allowed and do not affect the result.

Example

#include "game/grundy.hpp"
#include <iostream>
#include <vector>

int main() {
    std::vector<std::vector<int>> moves(4);
    moves[0] = {1, 2};
    moves[1] = {3};
    moves[2] = {3};

    auto grundy = m1une::game::grundy_numbers(moves);
    std::cout << grundy[0] << '\n';  // 0
}

Required by

• Game Library (game/all.hpp)

Verified with

• verify/game/game_algorithms.test.cpp

Code

#ifndef M1UNE_GAME_GRUNDY_HPP
#define M1UNE_GAME_GRUNDY_HPP 1

#include <cassert>
#include <queue>
#include <vector>

namespace m1une {
namespace game {

// graph[v] contains the states reachable from v in one move.
// The graph must be a DAG.
template <typename Graph>
std::vector<int> grundy_numbers(const Graph& graph) {
    const int size = int(graph.size());
    std::vector<int> indegree(size);
    for (int vertex = 0; vertex < size; ++vertex) {
        for (int next : graph[vertex]) {
            assert(0 <= next && next < size);
            indegree[next]++;
        }
    }

    std::queue<int> queue;
    for (int vertex = 0; vertex < size; ++vertex) {
        if (indegree[vertex] == 0) queue.push(vertex);
    }
    std::vector<int> order;
    order.reserve(size);
    while (!queue.empty()) {
        const int vertex = queue.front();
        queue.pop();
        order.push_back(vertex);
        for (int next : graph[vertex]) {
            if (--indegree[next] == 0) queue.push(next);
        }
    }
    assert(int(order.size()) == size);

    std::vector<int> grundy(size);
    std::vector<int> seen(size + 1, -1);
    for (int position = size - 1; position >= 0; --position) {
        const int vertex = order[position];
        for (int next : graph[vertex]) {
            const int value = grundy[next];
            if (value <= size) seen[value] = vertex;
        }
        while (grundy[vertex] <= size && seen[grundy[vertex]] == vertex) {
            grundy[vertex]++;
        }
    }
    return grundy;
}

}  // namespace game
}  // namespace m1une

#endif  // M1UNE_GAME_GRUNDY_HPP

#line 1 "game/grundy.hpp"



#include <cassert>
#include <queue>
#include <vector>

namespace m1une {
namespace game {

// graph[v] contains the states reachable from v in one move.
// The graph must be a DAG.
template <typename Graph>
std::vector<int> grundy_numbers(const Graph& graph) {
    const int size = int(graph.size());
    std::vector<int> indegree(size);
    for (int vertex = 0; vertex < size; ++vertex) {
        for (int next : graph[vertex]) {
            assert(0 <= next && next < size);
            indegree[next]++;
        }
    }

    std::queue<int> queue;
    for (int vertex = 0; vertex < size; ++vertex) {
        if (indegree[vertex] == 0) queue.push(vertex);
    }
    std::vector<int> order;
    order.reserve(size);
    while (!queue.empty()) {
        const int vertex = queue.front();
        queue.pop();
        order.push_back(vertex);
        for (int next : graph[vertex]) {
            if (--indegree[next] == 0) queue.push(next);
        }
    }
    assert(int(order.size()) == size);

    std::vector<int> grundy(size);
    std::vector<int> seen(size + 1, -1);
    for (int position = size - 1; position >= 0; --position) {
        const int vertex = order[position];
        for (int next : graph[vertex]) {
            const int value = grundy[next];
            if (value <= size) seen[value] = vertex;
        }
        while (grundy[vertex] <= size && seen[grundy[vertex]] == vertex) {
            grundy[vertex]++;
        }
    }
    return grundy;
}

}  // namespace game
}  // namespace m1une

Back to top page