Euler Tour Algorithm
コードについての説明
木の頂点を dfs でたどっていきながら途中で通った頂点を順番に配列に格納するアルゴリズム.
構築した配列を Segment Tree などと組み合わせて LCA を求めたり, 部分木の頂点集合に加算を行ったりなどいろいろなことができる.
以下には "行きがけ、通りがけ、帰りがけ順で通った頂点を記録",
"行きがけ、帰りがけ順で通った頂点を記録", "行きがけ順で通った頂点を記録" の $3$ 種類の実装を置いている. 実装自体はただ DFS をしているだけなので難しくはない. 用途に応じて使い分ける.
時間計算量: $\O (n+m)$
コード
const int MAX_N = 100005;
//uを根とする部分木は[lb[u],rb[u])で表せる
//行きがけ、通りがけ、帰りがけのすべてを記録
vector<int> G[MAX_N];
vector<int> ord;
int lb[MAX_N],rb[MAX_N],id[MAX_N];
void dfs(int u,int p)
{
id[u] = ord.size();
lb[u] = (int)ord.size();
ord.push_back(u);
for(int v : G[u]){
if(v != p){
dfs(v,u);
ord.push_back(u);
}
}
rb[u] = (int)ord.size() - 1;
}
//行きがけ、帰りがけのみを記録
vector<int> G[MAX_N];
vector<int> ord;
int lb[MAX_N],rb[MAX_N],id[MAX_N];
void dfs(int u,int p)
{
id[u] = ord.size();
lb[u] = (int)ord.size();
ord.push_back(u);
for(int v : G[u]){
if(v != p){
dfs(v,u);
}
}
ord.push_back(u);
rb[u] = (int)ord.size() - 1;
}
//行きがけのみを記録
vector<int> G[MAX_N];
vector<int> ord;
int lb[MAX_N],rb[MAX_N],id[MAX_N];
void dfs(int u,int p)
{
id[u] = ord.size();
lb[u] = (int)ord.size();
ord.push_back(u);
for(int v : G[u]){
if(v != p){
dfs(v,u);
}
}
rb[u] = (int)ord.size();
}
verify 用の問題
省略