Centroid Enumerate
(graph/tree/CentroidEnumerate.hpp)

• View this file on GitHub
• Last update: 2025-05-03 16:51:51+09:00
• Include: #include "graph/tree/CentroidEnumerate.hpp"

概要

todo

計算量

todo

Code

vector<int> Centroid(const vector<vector<int>> &g) {
    int n = int(g.size());

    vector<int> centroids;
    vector<int> subtree_size(n, 1);
    auto dfs = [&](int u, int prev) {
        bool is_centroid = true;

        for (auto v : g[u]) {
            if (v != prev) {
                dfs(v, u);
                subtree_size[u] += subtree_size[v];
                if (subtree_size[v] > n / 2) is_centroid = false;
            }
        }
        if (n - subtree_size[u] > n / 2) is_centroid = false;
        if (is_centroid) centroids.emplace_back(u);
    };

    dfs(0, -1);
    return centroids;
}

#line 1 "graph/tree/CentroidEnumerate.hpp"
vector<int> Centroid(const vector<vector<int>> &g) {
    int n = int(g.size());

    vector<int> centroids;
    vector<int> subtree_size(n, 1);
    auto dfs = [&](int u, int prev) {
        bool is_centroid = true;

        for (auto v : g[u]) {
            if (v != prev) {
                dfs(v, u);
                subtree_size[u] += subtree_size[v];
                if (subtree_size[v] > n / 2) is_centroid = false;
            }
        }
        if (n - subtree_size[u] > n / 2) is_centroid = false;
        if (is_centroid) centroids.emplace_back(u);
    };

    dfs(0, -1);
    return centroids;
}

Back to top page