重心分解
(graph/tree/centroid-decomposition.hpp)

• View this file on GitHub
• Last update: 2023-11-04 18:06:00+09:00
• Include: #include "graph/tree/centroid-decomposition.hpp"

Depends on

• グラフ構造体 (graph/graph_template.hpp)

Code

#pragma once

#include "../graph_template.hpp"

// TODO: 良いインターフェイスを模索する
struct CentroidDecomposition {
    const Graph<int>& G;
    std::vector<int> subtree_size, parent;
    std::vector<bool> removed;

    explicit CentroidDecomposition(const Graph<int>& g): G(g), subtree_size(g.size(), 0), parent(g.size(), -1), removed(g.size(), false) {}

    void get_subtree_size(int u, int p) {
        subtree_size[u] = 1;
        for(int v : G[u]) {
            if(v == p or removed[v]) continue;
            get_subtree_size(v, u);
            subtree_size[u] += subtree_size[v];
        }
    }

    void decomp(int u, int p) {
        get_subtree_size(u, -1);
        int sz = subtree_size[u];
        int pre = -1;
        while(1) {
            int mx = -1, mx_v = -1;
            for(int v : G[u]) {
                if(v == pre or removed[v]) continue;
                if(mx < subtree_size[v]) {
                    mx = subtree_size[v];
                    mx_v = v;
                }
            }
            if(mx * 2 <= sz) break;
            pre = u;
            u = mx_v;
        }
        removed[u] = true;
        parent[u] = p;
        for(int v : G[u]) {
            if(removed[v]) continue;
            decomp(v, u);
        }
    }
};

#line 2 "graph/tree/centroid-decomposition.hpp"

#line 2 "graph/graph_template.hpp"

#include <cassert>
#include <vector>

template <typename Cost = int> struct Edge {
    int from, to;
    Cost cost;
    int id;
    Edge() = default;
    explicit Edge(int from, int to, Cost cost = 1, int id = -1)
        : from(from), to(to), cost(cost), id(id) {}
    operator int() const { return to; }
};

template <typename Cost = int> class Graph {
  public:
    Graph() = default;
    explicit Graph(int N) : N(N), M(0), G(N) {}

    inline void add_directed_edge(int from, int to, Cost cost = 1) {
        assert(0 <= from && from < N);
        assert(0 <= to && to < N);
        G[from].emplace_back(from, to, cost, M++);
    }

    inline void add_undirected_edge(int from, int to, Cost cost = 1) {
        assert(0 <= from && from < N);
        assert(0 <= to && to < N);
        G[from].emplace_back(from, to, cost, M);
        G[to].emplace_back(to, from, cost, M++);
    }

    inline size_t size() const { return G.size(); }
    inline std::vector<Edge<Cost>> &operator[](const int &i) { return G[i]; }
    inline const std::vector<Edge<Cost>> &operator[](const int &i) const {
        return G[i];
    }

  protected:
    int N, M;
    std::vector<std::vector<Edge<Cost>>> G;
};

template <class Cost = int> using Edges = std::vector<Edge<Cost>>;
#line 4 "graph/tree/centroid-decomposition.hpp"

// TODO: 良いインターフェイスを模索する
struct CentroidDecomposition {
    const Graph<int>& G;
    std::vector<int> subtree_size, parent;
    std::vector<bool> removed;

    explicit CentroidDecomposition(const Graph<int>& g): G(g), subtree_size(g.size(), 0), parent(g.size(), -1), removed(g.size(), false) {}

    void get_subtree_size(int u, int p) {
        subtree_size[u] = 1;
        for(int v : G[u]) {
            if(v == p or removed[v]) continue;
            get_subtree_size(v, u);
            subtree_size[u] += subtree_size[v];
        }
    }

    void decomp(int u, int p) {
        get_subtree_size(u, -1);
        int sz = subtree_size[u];
        int pre = -1;
        while(1) {
            int mx = -1, mx_v = -1;
            for(int v : G[u]) {
                if(v == pre or removed[v]) continue;
                if(mx < subtree_size[v]) {
                    mx = subtree_size[v];
                    mx_v = v;
                }
            }
            if(mx * 2 <= sz) break;
            pre = u;
            u = mx_v;
        }
        removed[u] = true;
        parent[u] = p;
        for(int v : G[u]) {
            if(removed[v]) continue;
            decomp(v, u);
        }
    }
};

Back to top page