rooted_tree_isomorphism.hpp¶

SECTIONGraph INCLUDEnoya/rooted_tree_isomorphism.hpp

给有根树分配同构类型编号；用于判断多棵根树是否只差孩子排列，或压缩相同子树结构。

Complexity: Time: O(n log n) from sorting child labels. Space: O(n).

AC 记录：rooted_tree_isomorphism_classification。

Implementation¶

ReferenceSourceExpanded

当前头文件，省略 include guard；依赖见 #include。

/// @complexity Time: O(n log n) from sorting child labels.
/// Space: O(n).

#include <algorithm>
#include <map>
#include <vector>

namespace noya {

/// @brief Assign canonical hash labels to rooted subtrees for isomorphism testing.
struct tree_isomorphism {
  std::map<std::vector<int>, int> mp;
  int cnt = 0;

  /// @brief Compute canonical labels for all nodes of a rooted tree.
  /// @return Vector mapping each node to its canonical subtree label.
  std::vector<int> solve(const std::vector<std::vector<int>> &g,
                         const int rt = 0) {
    int N = int(g.size());
    std::vector<int> ans(N);
    auto dfs = [&](auto &self, int u, int fa) -> int {
      std::vector<int> ch;
      for (int v : g[u]) {
        if (v != fa) {
          ch.push_back(self(self, v, u));
        }
      }
      std::sort(ch.begin(), ch.end());
      if (!mp.count(ch))
        mp[ch] = cnt++;
      return ans[u] = mp[ch];
    };
    dfs(dfs, rt, -1);
    return ans;
  }
};

} // namespace noya

#ifndef NOYA_ROOTED_TREE_ISOMORPHISM_HPP
#define NOYA_ROOTED_TREE_ISOMORPHISM_HPP 1

/// @complexity Time: O(n log n) from sorting child labels.
/// Space: O(n).

#include <algorithm>
#include <map>
#include <vector>

namespace noya {

/// @brief Assign canonical hash labels to rooted subtrees for isomorphism testing.
struct tree_isomorphism {
  std::map<std::vector<int>, int> mp;
  int cnt = 0;

  /// @brief Compute canonical labels for all nodes of a rooted tree.
  /// @return Vector mapping each node to its canonical subtree label.
  std::vector<int> solve(const std::vector<std::vector<int>> &g,
                         const int rt = 0) {
    int N = int(g.size());
    std::vector<int> ans(N);
    auto dfs = [&](auto &self, int u, int fa) -> int {
      std::vector<int> ch;
      for (int v : g[u]) {
        if (v != fa) {
          ch.push_back(self(self, v, u));
        }
      }
      std::sort(ch.begin(), ch.end());
      if (!mp.count(ch))
        mp[ch] = cnt++;
      return ans[u] = mp[ch];
    };
    dfs(dfs, rt, -1);
    return ans;
  }
};

} // namespace noya

#endif // NOYA_ROOTED_TREE_ISOMORPHISM_HPP

#include <algorithm>
#include <map>
#include <vector>

/// @complexity Time: O(n log n) from sorting child labels.
/// Space: O(n).

namespace noya {

/// @brief Assign canonical hash labels to rooted subtrees for isomorphism testing.
struct tree_isomorphism {
  std::map<std::vector<int>, int> mp;
  int cnt = 0;

  /// @brief Compute canonical labels for all nodes of a rooted tree.
  /// @return Vector mapping each node to its canonical subtree label.
  std::vector<int> solve(const std::vector<std::vector<int>> &g,
                         const int rt = 0) {
    int N = int(g.size());
    std::vector<int> ans(N);
    auto dfs = [&](auto &self, int u, int fa) -> int {
      std::vector<int> ch;
      for (int v : g[u]) {
        if (v != fa) {
          ch.push_back(self(self, v, u));
        }
      }
      std::sort(ch.begin(), ch.end());
      if (!mp.count(ch))
        mp[ch] = cnt++;
      return ans[u] = mp[ch];
    };
    dfs(dfs, rt, -1);
    return ans;
  }
};

} // namespace noya