other/todd_coxeter.hpp

• View this file on GitHub
• Last update: 2026-10-24 10:36:44+09:00
• Include: #include "other/todd_coxeter.hpp"
• Link: https://github.com/maspypy/library/blob/main/other/todd_coxeter.hpp

Depends on

• ds/unionfind/unionfind.hpp

Code

// Source: https://github.com/maspypy/library/blob/main/other/todd_coxeter.hpp
#include "ds/unionfind/unionfind.hpp"

// 有限モノイドであることを前提として，遷移表を返す
template <int K>
vc<array<int, K>> todd_coxeter(const vc<pair<vc<int>, vc<int>>> &R) {
  int N = 0;

  vector<array<int, K>> T;
  UnionFind uf;
  vc<bool> done;

  auto add_vertex = [&]() -> int {
    int v = N++;
    T.emplace_back().fill(-1);
    uf.add_vertex();
    done.eb(false);
    return v;
  };

  auto step = [&](int v, int x) -> int {
    v = uf[v];
    if (T[v][x] == -1) return T[v][x] = add_vertex();
    return uf[T[v][x]];
  };

  auto walk = [&](int v, const vc<int> &s) -> int {
    for (int x : s) v = step(v, x);
    return v;
  };

  auto merge = [&](int p, int q) -> void {
    vc<pair<int, int>> que;
    que.eb(p, q);
    while (len(que)) {
      auto [p, q] = POP(que);
      p = uf[p], q = uf[q];
      if (p == q) continue;
      uf.merge(p, q);
      int r = uf[p];
      done[r] = done[p] | done[q];
      FOR(x, K) {
        int a = T[p][x], b = T[q][x];
        T[r][x] = max(a, b);
        if (a != -1 && b != -1) que.eb(a, b);
      }
    }
  };

  add_vertex();
  for (int p = 0; p < len(T); ++p) {
    for (auto &[u, v] : R) merge(walk(p, u), walk(p, v));
    FOR(x, K) step(p, x);
    done[uf[p]] = true;
  }

  // 代表元だけを残してインデックスをつけなおし，遷移表を返す
  vc<int> root;
  FOR(v, N) if (uf[v] == v) root.emplace_back(v);
  int n = len(root);
  vc<int> new_idx(N);
  FOR(i, n) new_idx[root[i]] = i;
  for (int v : root) {
    FOR(x, K) T[v][x] = new_idx[uf[T[v][x]]];
  }
  FOR(i, n) T[i] = T[root[i]];
  T.resize(n);
  return T;
}

#line 1 "other/todd_coxeter.hpp"
// Source: https://github.com/maspypy/library/blob/main/other/todd_coxeter.hpp
#line 1 "ds/unionfind/unionfind.hpp"
// Source: https://github.com/maspypy/library/blob/main/ds/unionfind/unionfind.hpp

struct UnionFind {
  int n, n_comp;
  vc<int> dat;  // par or (-size)
  UnionFind(int n = 0) { build(n); }

  void build(int m) {
    n = m, n_comp = m;
    dat.assign(n, -1);
  }

  void reset() { build(n); }

  int add_vertex() {
    ++n_comp, dat.eb(-1);
    return n++;
  }

  int operator[](int x) {
    while (dat[x] >= 0) {
      int pp = dat[dat[x]];
      if (pp < 0) {
        return dat[x];
      }
      x = dat[x] = pp;
    }
    return x;
  }

  ll size(int x) {
    x = (*this)[x];
    return -dat[x];
  }

  bool merge(int x, int y) {
    x = (*this)[x], y = (*this)[y];
    if (x == y) return false;
    if (-dat[x] < -dat[y]) swap(x, y);
    dat[x] += dat[y], dat[y] = x, n_comp--;
    return true;
  }

  vc<int> get_all() {
    vc<int> A(n);
    FOR(i, n) A[i] = (*this)[i];
    return A;
  }
};
#line 3 "other/todd_coxeter.hpp"

// 有限モノイドであることを前提として，遷移表を返す
template <int K>
vc<array<int, K>> todd_coxeter(const vc<pair<vc<int>, vc<int>>> &R) {
  int N = 0;

  vector<array<int, K>> T;
  UnionFind uf;
  vc<bool> done;

  auto add_vertex = [&]() -> int {
    int v = N++;
    T.emplace_back().fill(-1);
    uf.add_vertex();
    done.eb(false);
    return v;
  };

  auto step = [&](int v, int x) -> int {
    v = uf[v];
    if (T[v][x] == -1) return T[v][x] = add_vertex();
    return uf[T[v][x]];
  };

  auto walk = [&](int v, const vc<int> &s) -> int {
    for (int x : s) v = step(v, x);
    return v;
  };

  auto merge = [&](int p, int q) -> void {
    vc<pair<int, int>> que;
    que.eb(p, q);
    while (len(que)) {
      auto [p, q] = POP(que);
      p = uf[p], q = uf[q];
      if (p == q) continue;
      uf.merge(p, q);
      int r = uf[p];
      done[r] = done[p] | done[q];
      FOR(x, K) {
        int a = T[p][x], b = T[q][x];
        T[r][x] = max(a, b);
        if (a != -1 && b != -1) que.eb(a, b);
      }
    }
  };

  add_vertex();
  for (int p = 0; p < len(T); ++p) {
    for (auto &[u, v] : R) merge(walk(p, u), walk(p, v));
    FOR(x, K) step(p, x);
    done[uf[p]] = true;
  }

  // 代表元だけを残してインデックスをつけなおし，遷移表を返す
  vc<int> root;
  FOR(v, N) if (uf[v] == v) root.emplace_back(v);
  int n = len(root);
  vc<int> new_idx(N);
  FOR(i, n) new_idx[root[i]] = i;
  for (int v : root) {
    FOR(x, K) T[v][x] = new_idx[uf[T[v][x]]];
  }
  FOR(i, n) T[i] = T[root[i]];
  T.resize(n);
  return T;
}

Back to top page