Grundy Number
(math/grundy-number.hpp)

• View this file on GitHub
• Last update: 2021-11-23 10:22:25+09:00
• Include: #include "math/grundy-number.hpp"

Depends on

• グラフテンプレート (graph/graph-template.hpp)
• graph/topological-sort.hpp

Verified with

• verify/verify-yuki/yuki-0103.test.cpp

Code

#pragma once



#include "../graph/topological-sort.hpp"

vector<int> GrundyNumber(vector<vector<int>> &g) {
  vector<int> topo = TopologicalSort(g);
  if ((int)topo.size() == 0) return vector<int>();
  vector<int> grundy(g.size(), 0);
  vector<int> memo(g.size() + 1, 0);
  for (int _ = (int)g.size() - 1; _ >= 0; _--) {
    int i = topo[_];
    if (g[i].size() == 0) continue;
    for (auto &x : g[i]) {
      memo[grundy[x]]++;
    }
    while (memo[grundy[i]] > 0) grundy[i]++;
    for (auto &x : g[i]) {
      memo[grundy[x]]--;
    }
  }
  return grundy;
};

/**
 * @brief Grundy Number
 */

#line 2 "math/grundy-number.hpp"



#line 2 "graph/topological-sort.hpp"

#line 2 "graph/graph-template.hpp"

template <typename T>
struct edge {
  int src, to;
  T cost;

  edge(int _to, T _cost) : src(-1), to(_to), cost(_cost) {}
  edge(int _src, int _to, T _cost) : src(_src), to(_to), cost(_cost) {}

  edge &operator=(const int &x) {
    to = x;
    return *this;
  }

  operator int() const { return to; }
};
template <typename T>
using Edges = vector<edge<T>>;
template <typename T>
using WeightedGraph = vector<Edges<T>>;
using UnweightedGraph = vector<vector<int>>;

// Input of (Unweighted) Graph
UnweightedGraph graph(int N, int M = -1, bool is_directed = false,
                      bool is_1origin = true) {
  UnweightedGraph g(N);
  if (M == -1) M = N - 1;
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    if (is_1origin) x--, y--;
    g[x].push_back(y);
    if (!is_directed) g[y].push_back(x);
  }
  return g;
}

// Input of Weighted Graph
template <typename T>
WeightedGraph<T> wgraph(int N, int M = -1, bool is_directed = false,
                        bool is_1origin = true) {
  WeightedGraph<T> g(N);
  if (M == -1) M = N - 1;
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    T c;
    cin >> c;
    if (is_1origin) x--, y--;
    g[x].emplace_back(x, y, c);
    if (!is_directed) g[y].emplace_back(y, x, c);
  }
  return g;
}

// Input of Edges
template <typename T>
Edges<T> esgraph(int N, int M, int is_weighted = true, bool is_1origin = true) {
  Edges<T> es;
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    T c;
    if (is_weighted)
      cin >> c;
    else
      c = 1;
    if (is_1origin) x--, y--;
    es.emplace_back(x, y, c);
  }
  return es;
}

// Input of Adjacency Matrix
template <typename T>
vector<vector<T>> adjgraph(int N, int M, T INF, int is_weighted = true,
                           bool is_directed = false, bool is_1origin = true) {
  vector<vector<T>> d(N, vector<T>(N, INF));
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    T c;
    if (is_weighted)
      cin >> c;
    else
      c = 1;
    if (is_1origin) x--, y--;
    d[x][y] = c;
    if (!is_directed) d[y][x] = c;
  }
  return d;
}

/**
 * @brief グラフテンプレート
 * @docs docs/graph/graph-template.md
 */
#line 4 "graph/topological-sort.hpp"

// if the graph is not DAG, return empty vector
template <typename T>
vector<int> TopologicalSort(T &g) {
  int N = g.size();
  vector<int> marked(N, 0), temp(N, 0), v;
  auto visit = [&](auto f, int i) -> bool {
    if (temp[i] == 1) return false;
    if (marked[i] == 0) {
      temp[i] = 1;
      for (auto &e : g[i]) {
        if (f(f, e) == false) return false;
      }
      marked[i] = 1;
      v.push_back(i);
      temp[i] = 0;
    }
    return true;
  };

  for (int i = 0; i < N; i++) {
    if (marked[i] == 0) {
      if (visit(visit, i) == false) return vector<int>();
    }
  }
  reverse(v.begin(), v.end());
  return v;
}
#line 6 "math/grundy-number.hpp"

vector<int> GrundyNumber(vector<vector<int>> &g) {
  vector<int> topo = TopologicalSort(g);
  if ((int)topo.size() == 0) return vector<int>();
  vector<int> grundy(g.size(), 0);
  vector<int> memo(g.size() + 1, 0);
  for (int _ = (int)g.size() - 1; _ >= 0; _--) {
    int i = topo[_];
    if (g[i].size() == 0) continue;
    for (auto &x : g[i]) {
      memo[grundy[x]]++;
    }
    while (memo[grundy[i]] > 0) grundy[i]++;
    for (auto &x : g[i]) {
      memo[grundy[x]]--;
    }
  }
  return grundy;
};

/**
 * @brief Grundy Number
 */

Back to top page