根付き木の同型性判定をするコード

isomorphic.cpp

#include <algorithm>
#include <iostream>
#include <sstream>
#include <vector>

using Tree = std::vector<std::vector<int>>;
struct RootedTree {
  const Tree& tree;
  const int root;
  RootedTree(const Tree& tree, int root) : tree(tree), root(root) {}
  std::string to_s() const { return to_s(root); }
  std::string to_s(int v, int parent = -1) const {
    std::ostringstream oss;
    oss << '(';
    std::vector<std::string> children;
    children.reserve(tree[v].size());
    for (int u : tree[v]) {
      if (u == parent) continue;
      children.emplace_back(to_s(u, v));
    }
    std::stable_sort(children.begin(), children.end());
    for (const auto& child : children) {
      oss << child;
    }
    oss << ')';
    return oss.str();
  }
  bool operator==(const RootedTree& rhs) const { return to_s() == rhs.to_s(); }
};