根付き木の各部分木をハッシュ値に変換した列
(Src/Graph/Tree/SubtreesHash.hpp)

• View this file on GitHub
• Last update: 2025-04-09 18:50:51+09:00
• Include: #include "Src/Graph/Tree/SubtreesHash.hpp"

概要

Rooted Tree Isomorphism Classification をします。$O(N\log N)$でやる代わりに、ハッシュ値が衝突することはありません。

ライブラリの使い方

SubtreesHasher()

ハッシュ列を返す関数オブジェクト

複数の木に対して同型判定をしたい場合は単一の関数オブジェクトを利用すること

template <class G>
std::vector<usize> SubtreesHasher::operator()(const G& g, usize r = 0u)

gをrを根とした木の隣接リストと捉え、各頂点 $v$ の部分木のハッシュ値を返す。

operator()を二回以上呼ぶとき、返り値の $\max + 1$ が種類数と限らないことに注意

• LCのテストでは一回しか呼ばないため、 $\max + 1$ が種類数と一致している

Depends on

• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Verified with

• Test/AtCoder/arc194_d.test.cpp
• Test/LC/rooted_tree_isomorphism_classification.test.cpp

Code

#pragma once

#include "../../Template/TypeAlias.hpp"

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

namespace zawa {

class SubtreesHasher {
public:

    SubtreesHasher() = default;

    template <class G>
    std::vector<usize> operator()(const G& g, usize r = 0u) {
        std::vector<usize> res(g.size());
        auto dfs = [&](auto dfs, usize v, usize p) -> usize {
            std::vector<usize> ch;
            ch.reserve(g[v].size());
            for (usize x : g[v]) if (x != p) {
                ch.push_back(dfs(dfs, x, v));
            }
            std::sort(ch.begin(), ch.end());
            return res[v] = mapping(std::move(ch));
        };
        dfs(dfs, r, std::numeric_limits<u32>::max());
        return res;
    }

private:

    std::map<std::vector<usize>, usize> map;

    usize mapping(std::vector<usize>&& A) {
        usize cur = map.size();
        return map.try_emplace(std::move(A), cur).first->second;
    }
};

} // namespace zawa

#line 2 "Src/Graph/Tree/SubtreesHash.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Graph/Tree/SubtreesHash.hpp"

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

namespace zawa {

class SubtreesHasher {
public:

    SubtreesHasher() = default;

    template <class G>
    std::vector<usize> operator()(const G& g, usize r = 0u) {
        std::vector<usize> res(g.size());
        auto dfs = [&](auto dfs, usize v, usize p) -> usize {
            std::vector<usize> ch;
            ch.reserve(g[v].size());
            for (usize x : g[v]) if (x != p) {
                ch.push_back(dfs(dfs, x, v));
            }
            std::sort(ch.begin(), ch.end());
            return res[v] = mapping(std::move(ch));
        };
        dfs(dfs, r, std::numeric_limits<u32>::max());
        return res;
    }

private:

    std::map<std::vector<usize>, usize> map;

    usize mapping(std::vector<usize>&& A) {
        usize cur = map.size();
        return map.try_emplace(std::move(A), cur).first->second;
    }
};

} // namespace zawa

Back to top page