library/tree/RootedTreeIsomorphism.hpp

View this file on GitHub
Last update: 2025-11-24 18:49:07+09:00
Include: #include "library/tree/RootedTreeIsomorphism.hpp"

Depends on

build/pch/stdc++.hpp

Verified with

test/library-checker/Tree/RootedTreeIsomorphismClassification.test.cpp

Code

template <typename TREE>
std::pair<int, std::vector<int>> rooted_tree_isomorphism(TREE &t) {
    assert(~t.root);
    std::vector<int> res(t.n);
    std::map<std::vector<int>, int> mp;
    for (const int v : t.DFS) {
        std::vector<int> h;
        for (int to : t.son(v))
            h.push_back(res[to]);
        std::ranges::sort(h);
        if (!mp.count(h))
            mp[h] = mp.size();
        res[v] = mp[h];
    }
    return {mp.size(), res};
}

#line 1 "library/tree/RootedTreeIsomorphism.hpp"
template <typename TREE>
std::pair<int, std::vector<int>> rooted_tree_isomorphism(TREE &t) {
    assert(~t.root);
    std::vector<int> res(t.n);
    std::map<std::vector<int>, int> mp;
    for (const int v : t.DFS) {
        std::vector<int> h;
        for (int to : t.son(v))
            h.push_back(res[to]);
        std::ranges::sort(h);
        if (!mp.count(h))
            mp[h] = mp.size();
        res[v] = mp[h];
    }
    return {mp.size(), res};
}