Sentroid dekompozitsiyasi

Sentroid dekompozitsiyasi - Course 5

int subtree_size[maxn];

int get_subtree_size(int node, int parent = -1) {
    int &res = subtree_size[node];
    res = 1;
    for (int x : adj[node]) {
        if (x == parent) continue;
        res += get_subtree_size(x, node);
    }
    return res;
}

int get_centroid(int node, int tree_size, int parent = -1) {
    for (int x : adj[node]) {
        if (x == parent) continue;

        if (subtree_size[x] * 2 > tree_size) {
            return get_centroid(x, tree_size, node);
        }
    }
    return node;
}

int get_centroid(int node, int tree_size, int parent = -1) {
    for (int child : adj[node]) {
        if (child == parent || is_removed[child]) continue;
        if (subtree_size[child] * 2 > tree_size) {
            return get_centroid(child, tree_size, node);
        }
    }
    return node;
}

void build_centroid_decomp(int node = 0) {
    int centroid = get_centroid(node, get_subtree_size(node));

    // use centroid to do some magic!

    is_removed[centroid] = true;

    for (int child : adj[centroid]) {
        if (is_removed[child]) continue;
        build_centroid_decomp(child);
    }
}

Sentroid dekompozitsiyasi

Sentroid dekompozitsiyasiga kirish

Sentroid ta’rifi

Dekompozitsiya jarayoni

Sentroidni topish

Implementatsiya

Dekompozitsiya algoritmi

Algoritm qadamlari

Vizualizatsiya

Implementatsiya