C++ Library for Competitive Programming
View the Project on GitHub emthrm/cp-library
/* * @title グラフ/木/重心分解 * * verification-helper: IGNORE * verification-helper: PROBLEM https://atcoder.jp/contests/abc291/tasks/abc291_h */ #include <iostream> #include <vector> #include "emthrm/graph/edge.hpp" #include "emthrm/graph/tree/centroid_decomposition.hpp" int main() { int n; std::cin >> n; std::vector<std::vector<emthrm::Edge<bool>>> graph(n); for (int i = 0; i < n - 1; ++i) { int a, b; std::cin >> a >> b; --a; --b; graph[a].emplace_back(a, b); graph[b].emplace_back(b, a); } const std::vector<int> p = emthrm::CentroidDecomposition(graph).parent; for (int i = 0; i < n; ++i) { std::cout << (p[i] == -1 ? -1 : p[i] + 1) << " \n"[i + 1 == n]; } return 0; }
#line 1 "test/graph/tree/centroid_decomposition.test.cpp" /* * @title グラフ/木/重心分解 * * verification-helper: IGNORE * verification-helper: PROBLEM https://atcoder.jp/contests/abc291/tasks/abc291_h */ #include <iostream> #include <vector> #line 1 "include/emthrm/graph/edge.hpp" /** * @title 辺 */ #ifndef EMTHRM_GRAPH_EDGE_HPP_ #define EMTHRM_GRAPH_EDGE_HPP_ #include <compare> namespace emthrm { template <typename CostType> struct Edge { CostType cost; int src, dst; explicit Edge(const int src, const int dst, const CostType cost = 0) : cost(cost), src(src), dst(dst) {} auto operator<=>(const Edge& x) const = default; }; } // namespace emthrm #endif // EMTHRM_GRAPH_EDGE_HPP_ #line 1 "include/emthrm/graph/tree/centroid_decomposition.hpp" #include <ranges> #line 6 "include/emthrm/graph/tree/centroid_decomposition.hpp" #line 1 "include/emthrm/graph/edge.hpp" /** * @title 辺 */ #ifndef EMTHRM_GRAPH_EDGE_HPP_ #define EMTHRM_GRAPH_EDGE_HPP_ #include <compare> namespace emthrm { template <typename CostType> struct Edge { CostType cost; int src, dst; explicit Edge(const int src, const int dst, const CostType cost = 0) : cost(cost), src(src), dst(dst) {} auto operator<=>(const Edge& x) const = default; }; } // namespace emthrm #endif // EMTHRM_GRAPH_EDGE_HPP_ #line 8 "include/emthrm/graph/tree/centroid_decomposition.hpp" namespace emthrm { template <typename CostType> struct CentroidDecomposition { int root; std::vector<int> parent; std::vector<std::vector<int>> g; explicit CentroidDecomposition( const std::vector<std::vector<Edge<CostType>>>& graph) : graph(graph) { const int n = graph.size(); parent.assign(n, -1); g.resize(n); is_alive.assign(n, true); subtree.resize(n); root = build(0); } private: std::vector<bool> is_alive; std::vector<int> subtree; const std::vector<std::vector<Edge<CostType>>> graph; int build(const int s) { const int centroid = search_centroid(-1, s, calc_subtree(-1, s) / 2); is_alive[centroid] = false; for (const int e : graph[centroid] | std::views::transform(&Edge<CostType>::dst)) { if (is_alive[e]) { const int child = build(e); g[centroid].emplace_back(child); parent[child] = centroid; } } is_alive[centroid] = true; return centroid; } int calc_subtree(const int par, const int ver) { subtree[ver] = 1; for (const int e : graph[ver] | std::views::transform(&Edge<CostType>::dst)) { if (e != par && is_alive[e]) { subtree[ver] += calc_subtree(ver, e); } } return subtree[ver]; } int search_centroid(const int par, const int ver, const int half) const { for (const int e : graph[ver] | std::views::transform(&Edge<CostType>::dst)) { if (e != par && is_alive[e] && subtree[e] > half) { return search_centroid(ver, e, half); } } return ver; } }; } // namespace emthrm #line 13 "test/graph/tree/centroid_decomposition.test.cpp" int main() { int n; std::cin >> n; std::vector<std::vector<emthrm::Edge<bool>>> graph(n); for (int i = 0; i < n - 1; ++i) { int a, b; std::cin >> a >> b; --a; --b; graph[a].emplace_back(a, b); graph[b].emplace_back(b, a); } const std::vector<int> p = emthrm::CentroidDecomposition(graph).parent; for (int i = 0; i < n; ++i) { std::cout << (p[i] == -1 ? -1 : p[i] + 1) << " \n"[i + 1 == n]; } return 0; }