【競技プログラミング】重心分解を25行で書く方法
はじめに
重心分解は 25 行程度でかけます
(わかりやすい様にコメント付加してたら 30 行程度になってしまいました)
ポイントは重心分解によって出来る木を BFS でなく DFS で潜ることです！！！
Centroid_Decomposition.cpp
vector<vector<int>>g;//元の木の隣接リスト
vector<int>used;//重心が確定したか
vector<int>v;//重心分解後の木のDFS順の列
vector<vector<int>>ch;//重心分解後の木の親子関係
int s;//重心分解後の木の根
int dfs(int n,int p,int sz,int root){
constexpr int inf=g.size()*2;
if(used[n])return 0;
bool b=1;
int res=1;
for(auto e:g[n]){
if(p==e)continue;
auto t=dfs(e,n,sz,root);
res+=t;
if(t>sz/2)b=0;
}
if(!b||sz-res>sz/2)return res;//重心で無いなら部分木のサイズを返す
//重心を登録
if(root!=-1)ch[root].push_back(n);
else s=n;
v.push_back(n);
used[n]=1;
//重心分解後の木で自身の子となる重心を探す
//dfs(e,n,inf,n)では部分木のサイズを求めてる
//(szをinfにすると当然重心が見つからないため部分木のサイズが返る)
for(auto e:g[n])dfs(e,n,dfs(e,n,inf,n),n);
//重心はすでに見つかったためinf=g.size()*2を返す
return inf;
}
v には重心分解後の木を dfs した結果が入ります(なくてもいいかも)
ch には、重心分解後の木における子供が入ります
s は重心分解後の木の根が入ります
dfs の挙動は見たままです。は?(質問がある方はtwitterまで)