Test/LC/rooted_tree_isomorphism_classification.test.cpp

View this file on GitHub
Last update: 2025-04-09 18:54:17+09:00
Problem: https://judge.yosupo.jp/problem/rooted_tree_isomorphism_classification

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/rooted_tree_isomorphism_classification"

#include "../../Src/Graph/Tree/SubtreesHash.hpp"

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

using namespace zawa;

int main() {
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int N;
    std::cin >> N;
    std::vector<std::vector<int>> g(N);
    for (int i = 1 ; i < N ; i++) {
        int p;
        std::cin >> p;
        g[p].push_back(i);
    }
    auto ans = SubtreesHasher{}(g);
    auto K = *std::max_element(ans.begin(), ans.end()) + 1;
    std::cout << K << '\n';
    for (int i = 0 ; i < N ; i++) std::cout << ans[i] << (i + 1 == N ? '\n' : ' ');
}

#line 1 "Test/LC/rooted_tree_isomorphism_classification.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/rooted_tree_isomorphism_classification"

#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
#line 4 "Test/LC/rooted_tree_isomorphism_classification.test.cpp"

#line 6 "Test/LC/rooted_tree_isomorphism_classification.test.cpp"
#include <iostream>
#line 8 "Test/LC/rooted_tree_isomorphism_classification.test.cpp"

using namespace zawa;

int main() {
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int N;
    std::cin >> N;
    std::vector<std::vector<int>> g(N);
    for (int i = 1 ; i < N ; i++) {
        int p;
        std::cin >> p;
        g[p].push_back(i);
    }
    auto ans = SubtreesHasher{}(g);
    auto K = *std::max_element(ans.begin(), ans.end()) + 1;
    std::cout << K << '\n';
    for (int i = 0 ; i < N ; i++) std::cout << ans[i] << (i + 1 == N ? '\n' : ' ');
}