Artifact Content
Not logged in

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));
		}
	}
}