graph/CentroidDecomposition.h

• View this file on GitHub
• Last update: 2025-12-09 07:33:19+07:00

Code

void dfs_sz(int u, int p) {
    sub_sz[u] = 1;
    for (int v : adj[u]) {
        if (v != p && !removed[v]) {
            dfs_sz(v, u);
            sub_sz[u] += sub_sz[v];
        }
    }
}
 
int find_centroid(int u, int p, int total) {
    for (int v : adj[u]) {
        if (v != p && !removed[v] && sub_sz[v] > total / 2) {
            return find_centroid(v, u, total);
        }
    }
    return u;
}
 
void decompose(int u, int p) {
    dfs_sz(u, -1);
    int centroid = find_centroid(u, -1, sub_sz[u]);
    
    par_centroid[centroid] = p;
    removed[centroid] = true;
    
    for (int v : adj[centroid]) {
        if (!removed[v]) {
            decompose(v, centroid);
        }
    }
}

#line 1 "graph/CentroidDecomposition.h"
void dfs_sz(int u, int p) {
    sub_sz[u] = 1;
    for (int v : adj[u]) {
        if (v != p && !removed[v]) {
            dfs_sz(v, u);
            sub_sz[u] += sub_sz[v];
        }
    }
}
 
int find_centroid(int u, int p, int total) {
    for (int v : adj[u]) {
        if (v != p && !removed[v] && sub_sz[v] > total / 2) {
            return find_centroid(v, u, total);
        }
    }
    return u;
}
 
void decompose(int u, int p) {
    dfs_sz(u, -1);
    int centroid = find_centroid(u, -1, sub_sz[u]);
    
    par_centroid[centroid] = p;
    removed[centroid] = true;
    
    for (int v : adj[centroid]) {
        if (!removed[v]) {
            decompose(v, centroid);
        }
    }
}

Back to top page