木の重心
(atcoder/centroid.hpp)

• View this file on GitHub
• Last update: 2021-10-25 13:43:12+09:00
• Include: #include "atcoder/centroid.hpp"

概要

無向木の重心を求める.

木のハッシュの計算や, 木上の分割統治(重心分解)に応用できる.

• centroid(g) : 無向木 $g$ の重心を全て(1個 or 2個)返す.

計算量

• $O(

  V

  )$

Required by

• atcoder/treehash.hpp

Verified with

• test/treehash.test.cpp

Code

#ifndef ATCODER_CENTROID_HPP
#define ATCODER_CENTROID_HPP 1

#include <vector>

namespace atcoder {

std::vector<int> centroid(const std::vector<std::vector<int>>& g) {
    const int n = int(g.size());
    std::vector<int> sz(n,1), ret;
    auto dfs = [&](auto dfs, int u, int p) -> int {
        bool isCent = true;
        for (int v : g[u]) {
            if (v == p) continue;
            sz[u] += dfs(dfs, v, u);
            if (sz[v] > n / 2) isCent = false;
        }
        if (n - sz[u] > n / 2) isCent = false;
        if (isCent) ret.emplace_back(u);
        return sz[u];
    };
    dfs(dfs, 0, -1);
    return ret;
}

}  // namespace atcoder

#endif  // ATCODER_CENTROID_HPP

#line 1 "atcoder/centroid.hpp"



#include <vector>

namespace atcoder {

std::vector<int> centroid(const std::vector<std::vector<int>>& g) {
    const int n = int(g.size());
    std::vector<int> sz(n,1), ret;
    auto dfs = [&](auto dfs, int u, int p) -> int {
        bool isCent = true;
        for (int v : g[u]) {
            if (v == p) continue;
            sz[u] += dfs(dfs, v, u);
            if (sz[v] > n / 2) isCent = false;
        }
        if (n - sz[u] > n / 2) isCent = false;
        if (isCent) ret.emplace_back(u);
        return sz[u];
    };
    dfs(dfs, 0, -1);
    return ret;
}

}  // namespace atcoder

Back to top page