Artifact 4b76a9848cd0e992e6f251efe8a09bbb01321c02
//-------------------------------------------------------------
// Tree DFS numbering
// O(N)
//
// G : adjacent list of a graph (forming a tree)
// Labels each node v as dfs[v].
// Inclusive [dfs[v], dfs_end[v]] denotes the descendant range.
//
// Verified by
// - Codeforces 200 Div1 D
//-------------------------------------------------------------
void dfs_numbering(
int root,
const vector<vector<int>>& G, vector<int>& dfs, vector<int>& dfs_end,
vector<int>& parent_of)
{
int dfs_number = root;
dfs[root] = dfs_number++;
parent_of[root] = -1;
stack<tuple<int,int,int>> stk;
stk.push(make_tuple(-1, root, 0));
while(!stk.empty()) {
int grandparent = get<0>(stk.top());
int parent = get<1>(stk.top());
int child_id = get<2>(stk.top());
stk.pop();
if(G[parent].size() <= child_id) {
dfs_end[parent] = dfs_number - 1;
continue;
}
stk.push(make_tuple(grandparent, parent, child_id+1));
int me = G[parent][child_id];
if(me != grandparent) {
dfs[me] = dfs_number++;
parent_of[me] = parent;
stk.push(make_tuple(parent, me, 0));
}
}
}