Hi all,

May I know if anyone knows an efficient way to write iterative dfs? I am asking this because I am writing a program that has to deal with extremely large rooted trees. Even if I increase the stack limit, I think recursive dfs will be much slower than iterative dfs in this case due to the numerous function calls. Therefore, I implemented an iterative dfs as follows.

Note: the tree is rooted tree (edges point from parent to child), so I do not check if vertices have been visited.

```
vector <int> graph[MAXN];
stack <pair<int,int> > S;
S.push(pair<int,int>(TREE_ROOT,-1));
while(!S.empty()) {
pair<int,int> cur = S.top();
S.pop();
cur.second++;
// do stuff
if (cur.second < graph[cur.first].size()) {
S.push(cur);
S.push(pair<int,int>(graph[cur.first][cur.second],-1));
}
else {
//do more stuff
}
}
```

I am not sure if this is the best way to implement what I have. In practice my performance is not that good. Does anyone have a better implementation? My main concern is with speed.

Thank you!

Why you didn't check that a node is already in the stack or not before push it to stack ?

It is a rooted tree. I editted the post to make it clearer.

OK, right.

Optimize it more by change the stack type become stack of current node only. If you pop the current stack top element must be parent

I'm no user of C++, nor am I sure of the correctness of the following code (or even if it's efficient), but I think this is pretty much equivalent to your code and it should also cover an additional common case (just after we've processed a child). This code could be plain shit, but at least it's different. =D