Lib/オイラーツアー
☆再帰を使わないオイラーツアーの実装☆
code:cpp
vector<ll> index(n,-1);
vector<ll> rev_index(n,-1);
vector<ll> d(n,-1);
stack<pair<ll,bool>> stk;
stk.push({0,true});
ll pt = 0;
ll depth = 0;
while(!stk.empty()){
auto p,type = stk.top();
stk.pop();
if(type){
depth++;
indexp = pt;
dp = depth;
pt++;
stk.push({p,false});
for(auto next : gp){
if(indexnext == -1) stk.push({next,true});
}
}else{
depth--;
rev_indexp = pt;
pt++;
}
}
0→任意の頂点へのパスクエリ、部分木に対するクエリ、最小共通祖先(LCA)の取得などができる
パスクエリ+LCAで任意の2頂点間の距離が取れる
#Lib