tree/centroid_decomposition.cpp

• View this file on GitHub
• Last update: 2020-11-25 11:16:51+09:00

Verified with

• test/aoj0452.test.cpp

Code

class CentroidDecomposition {
    int dfs(int x, int par){
        sz[x] = 1;
        for (auto &&i : G[x]) {
            if(i == par || v[i]) continue;
            sz[x] += dfs(i, x);
        }
        return sz[x];
    }

    int search_centroid(int x, int p, const int mid){
        for (auto &&i : G[x]) {
            if(i == p || v[i]) continue;
            if(sz[i] > mid) return search_centroid(i, x, mid);
        }
        return x;
    }
public:
    int n;
    vector<vector<int>> G, out;
    vector<int> sz, v;
    CentroidDecomposition(int n) : n(n), G(n), out(n), sz(n), v(n) {}
    void add_edge(int l, int r){
        G[l].emplace_back(r);
        G[r].emplace_back(l);
    }
    int get(int x){
        int centroid = search_centroid(x, -1, dfs(x, -1)/2);
        v[centroid] = true;
        for (auto &&i : G[centroid]) {
            if(!v[i]) out[centroid].emplace_back(get(i));
        }
        v[centroid] = false;
        return centroid;
    }
};

#line 1 "tree/centroid_decomposition.cpp"
class CentroidDecomposition {
    int dfs(int x, int par){
        sz[x] = 1;
        for (auto &&i : G[x]) {
            if(i == par || v[i]) continue;
            sz[x] += dfs(i, x);
        }
        return sz[x];
    }

    int search_centroid(int x, int p, const int mid){
        for (auto &&i : G[x]) {
            if(i == p || v[i]) continue;
            if(sz[i] > mid) return search_centroid(i, x, mid);
        }
        return x;
    }
public:
    int n;
    vector<vector<int>> G, out;
    vector<int> sz, v;
    CentroidDecomposition(int n) : n(n), G(n), out(n), sz(n), v(n) {}
    void add_edge(int l, int r){
        G[l].emplace_back(r);
        G[r].emplace_back(l);
    }
    int get(int x){
        int centroid = search_centroid(x, -1, dfs(x, -1)/2);
        v[centroid] = true;
        for (auto &&i : G[centroid]) {
            if(!v[i]) out[centroid].emplace_back(get(i));
        }
        v[centroid] = false;
        return centroid;
    }
};

Back to top page