重心 (centroid)
(include/emthrm/graph/tree/centroid.hpp)

• View this file on GitHub
• Last update: 2023-05-12 15:57:02+09:00
• Include: #include "emthrm/graph/tree/centroid.hpp"

根としたときに任意の子の部分木の大きさが木の大きさの半分以下となる頂点である。

任意の木に必ず存在し、高々二つである。二つ存在するとき、木の頂点数は偶数である。

時間計算量

$O(\lvert V \rvert)$

仕様

名前	戻り値
template <typename CostType> std::vector<int> centroid(const std::vector<std::vector<Edge<CostType>>>& graph);	木 $\mathrm{graph}$ の重心

参考文献

• Camille Jordan: Sur les assemblages de lignes, Journal für die reine und angewandte Mathematik, Vol. 70, pp. 185–190 (1869). https://doi.org/10.1515/crll.1869.70.185
• https://qiita.com/drken/items/4b4c3f1824339b090202
• https://lumakernel.github.io/ecasdqina/graph/Centroid
• https://img.atcoder.jp/arc087/editorial.pdf

Submissons

https://atcoder.jp/contests/arc087/submissions/9306188

Depends on

• 辺 (include/emthrm/graph/edge.hpp)

Verified with

• グラフ/木/重心 (test/graph/tree/centroid.test.cpp)

Code

#ifndef EMTHRM_GRAPH_TREE_CENTROID_HPP_
#define EMTHRM_GRAPH_TREE_CENTROID_HPP_

#include <algorithm>
#include <ranges>
#include <vector>

#include "emthrm/graph/edge.hpp"

namespace emthrm {

template <typename CostType>
std::vector<int> centroid(
    const std::vector<std::vector<Edge<CostType>>>& graph) {
  const int n = graph.size();
  std::vector<int> subtree(n, 1), res;
  const auto dfs = [&graph, n, &subtree, &res](
      auto dfs, const int par, const int ver) -> void {
    bool is_centroid = true;
    for (const int e : graph[ver]
                     | std::views::transform(&Edge<CostType>::dst)) {
      if (e != par) {
        dfs(dfs, ver, e);
        subtree[ver] += subtree[e];
        is_centroid &= subtree[e] <= n / 2;
      }
    }
    if (is_centroid && n - subtree[ver] <= n / 2) res.emplace_back(ver);
  };
  dfs(dfs, -1, 0);
  std::sort(res.begin(), res.end());
  return res;
}

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_TREE_CENTROID_HPP_

#line 1 "include/emthrm/graph/tree/centroid.hpp"



#include <algorithm>
#include <ranges>
#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 9 "include/emthrm/graph/tree/centroid.hpp"

namespace emthrm {

template <typename CostType>
std::vector<int> centroid(
    const std::vector<std::vector<Edge<CostType>>>& graph) {
  const int n = graph.size();
  std::vector<int> subtree(n, 1), res;
  const auto dfs = [&graph, n, &subtree, &res](
      auto dfs, const int par, const int ver) -> void {
    bool is_centroid = true;
    for (const int e : graph[ver]
                     | std::views::transform(&Edge<CostType>::dst)) {
      if (e != par) {
        dfs(dfs, ver, e);
        subtree[ver] += subtree[e];
        is_centroid &= subtree[e] <= n / 2;
      }
    }
    if (is_centroid && n - subtree[ver] <= n / 2) res.emplace_back(ver);
  };
  dfs(dfs, -1, 0);
  std::sort(res.begin(), res.end());
  return res;
}

}  // namespace emthrm

Back to top page