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