Centroid Find Algorithm
コードについての説明
木の重心を求めるアルゴリズム.
頂点 $u$ が木の重心であるとは $u$ を根と見たときに $u$ の子を根とするすべての部分木のサイズが $n / 2$ 以下(木の頂点数を $n$ とする)であることをいう.
また重心は $1$ つの木に対して $1$ 個または $2$ 個存在する.
ある頂点を根としてそのときの各頂点を根とする部分木のサイズを dfs で求めておけば簡単に求まる.
時間計算量: $\O (n)$
コード
class centroid {
private:
int V;
vector<vector<int> > G;
vector<int> sz;
void dfs(int u,int p, vector<int>& ct){
bool ok = true;
sz[u] = 1;
for(int v : G[u]){
if(v != p){
dfs(v, u, ct);
sz[u] += sz[v];
if(2*sz[v] > V) ok = false;
}
}
if(ok && V <= 2*sz[u]) ct.push_back(u);
}
public:
centroid(int node_size) : V(node_size), G(V), sz(V, 0){}
void add_edge(int u,int v){
G[u].push_back(v), G[v].push_back(u);
}
vector<int> solve(){
vector<int> ct;
dfs(0, -1, ct);
return ct;
}
};
verify 用の問題
Atcoder : Squirrel Migration 提出コード