tree/tree_hash.cpp

View this file on GitHub
Last update: 2026-02-02 02:08:49+08:00

Verified with

test/rooted_tree_isomorphism_classification.test.cpp

Code

template<bool ordered = false>
auto tree_hash(vvi &g, int root = 0) {
  int nxt = 0;
  static map<vi, int> seq_to_id;
  vi subtree_id(size(g));
  auto dfs = [&](int v, int p, auto self) -> int {
    vi seq;
    seq.reserve(ssize(g[v]));
    for(int x : g[v]) if (x != p)
      seq.emplace_back(self(x, v, self));
    if constexpr (!ordered)
      ranges::sort(seq);
    auto [ite, insert] = seq_to_id.emplace(seq, nxt);
    if (insert) nxt++;
    return subtree_id[v] = ite -> second;
  };

  dfs(root, -1, dfs);

  return pair(nxt, subtree_id);
}

#line 1 "tree/tree_hash.cpp"
template<bool ordered = false>
auto tree_hash(vvi &g, int root = 0) {
  int nxt = 0;
  static map<vi, int> seq_to_id;
  vi subtree_id(size(g));
  auto dfs = [&](int v, int p, auto self) -> int {
    vi seq;
    seq.reserve(ssize(g[v]));
    for(int x : g[v]) if (x != p)
      seq.emplace_back(self(x, v, self));
    if constexpr (!ordered)
      ranges::sort(seq);
    auto [ite, insert] = seq_to_id.emplace(seq, nxt);
    if (insert) nxt++;
    return subtree_id[v] = ite -> second;
  };

  dfs(root, -1, dfs);

  return pair(nxt, subtree_id);
}