グラフ/木/重心分解
(test/graph/tree/centroid_decomposition.test.cpp)

• View this file on GitHub
• Last update: 2023-02-27 17:26:42+09:00
• Problem: https://atcoder.jp/contests/abc291/tasks/abc291_h

Depends on

• 辺 (include/emthrm/graph/edge.hpp)
• 重心分解 (centroid decompositon) (include/emthrm/graph/tree/centroid_decomposition.hpp)

Code

/*
 * @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;
}

Back to top page