test/library-checker/rooted_tree_isomorphism_classification.test.cpp

• View this file on GitHub
• Last update: 2023-01-11 14:05:50+09:00
• Problem: https://judge.yosupo.jp/problem/rooted_tree_isomorphism_classification

Depends on

• 根付き木の同型性による部分木の分類 (graph/subtree_classify.hpp)

Code

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

#include <iostream>

#include "graph/subtree_classify.hpp"
int main() {
    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);
    }

    std::vector<int> a = subtree_classify(g);
    int k = *std::max_element(a.begin(), a.end()) + 1;
    std::cout << k << '\n';
    for (int i = 0; i < n; i++) {
        std::cout << a[i] << " \n"[i == n - 1];
    }
}

#line 1 "test/library-checker/rooted_tree_isomorphism_classification.test.cpp"
#define PROBLEM \
    "https://judge.yosupo.jp/problem/rooted_tree_isomorphism_classification"

#include <iostream>

#line 2 "graph/subtree_classify.hpp"

#include <algorithm>
#include <map>
#include <vector>
std::vector<int> subtree_classify(std::vector<std::vector<int>> g,
                                  int root = 0) {
    std::vector<int> ret(g.size());
    std::map<std::vector<int>, int> cache;
    auto dfs = [&](auto dfs, int u) -> int {
        std::vector<int> hash;
        hash.push_back(-1);
        for (int v : g[u]) hash.push_back(dfs(dfs, v));
        std::sort(hash.begin(), hash.end());
        hash.push_back(-1);
        if (!cache.count(hash)) cache[hash] = int(cache.size());
        return ret[u] = cache[hash];
    };
    dfs(dfs, root);
    return ret;
}
#line 7 "test/library-checker/rooted_tree_isomorphism_classification.test.cpp"
int main() {
    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);
    }

    std::vector<int> a = subtree_classify(g);
    int k = *std::max_element(a.begin(), a.end()) + 1;
    std::cout << k << '\n';
    for (int i = 0; i < n; i++) {
        std::cout << a[i] << " \n"[i == n - 1];
    }
}

Back to top page