This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub gyouzasushi/library
#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]; } }