24 lines
608 B
C++
24 lines
608 B
C++
namespace centroid {
|
|
int sz[MX], cpar[MX];
|
|
bitset<MX> vis;
|
|
void dfs(vector<int> * G, int u, int p = 0) {
|
|
sz[u] = 1;
|
|
for (int v : G[u]) if (v != p && !vis[v]) dfs(G, v, u), sz[u] += sz[v];
|
|
}
|
|
int centroid(vector<int> * G, int u) {
|
|
dfs(G, u);
|
|
int num = sz[u], p = 0;
|
|
do {
|
|
int nxt = 0;
|
|
for (int v : G[u]) if (v != p && !vis[v] && 2*sz[v] > num) nxt = v;
|
|
p = u, u = nxt;
|
|
} while (u);
|
|
return p;
|
|
}
|
|
void centroid_decomp(vector<int> * G, int u = 1, int p = 0) {
|
|
int c = centroid(G, u);
|
|
vis[c] = 1, cpar[c] = p;
|
|
for (int v : G[c]) if (!vis[v]) centroid_decomp(G, v, c);
|
|
}
|
|
}
|