Non-recursive DFS start time and finish time implement

help
, ,
1

Can someone tell me how to write a better version of DFS for calculation of start time and finish time (NON-RECURSIVE DFS using STACK)

In this question: Question, we basically had to calculate start time and finish time for DFS run. I tried implementing, but in the end it became too hacky and I just got it to work after some jugaad.

Here is the solution I submit: submission

The relevant portion of DFS is given below:

// dfs to get intime and outtime
	fill(vis.begin(), vis.end(), 0);
	vector<LL> in_time(n, -1);
	vector<LL> out_time(n);

	stack<LL> st;
	st.push(0);
	LL t = 0;
	vis[0] = 1;

	while (!st.empty()) {
		LL u = st.top();
		if (in_time[u] == -1) {
			in_time[u] = t; t++;
		}

		LL cnt = 0;
		for (auto v : adj[u]) {
			if (!vis[v]) {
				vis[v] = 1;
				st.push(v);
				cnt++;
			}
		}
		if (!cnt) {
			out_time[u] = t; t++;
			st.pop();
		}
	}

I just need to write a better version of this NONRECURSIVE DFS using stack to calculate in, out time

Any advice is well recieved.

2 
int x = 1;
void dfs(int u, int p)
{
    timeIn[u]=x++;
    for(auto v:A[u])
    {
	    if(v==p) continue;
	    dfs(v,u);
    }
    timeOut[u]=x++;

}

I think this is simple! Isn’t it? I’m afraid non recursive one is too much implementation but I’ll check that too.

P.S. I’d recommend recursive DFS and Iterative BFS. They will just save you time and implementation. I just saw the iterative code and it’s a pain in my opinion!

1 Like
3

Both recursive and iterative will take equal time. So the difference is : the recursive one takes the size in the recursive stack , many times when the depth of recursion is very much MLE verdict is seen, but in the problem of trees , if you have to do DFS then recursive solution will never give MLE as the recursion depth size is greater than 2*10^5 , idk exactly how much but still I have never seen a tree problem with 10^6 order size, so using recursion for arr,dep of tree nodes will always work.

1 Like
4

Ok thanks @kkdrummer and @anon71312354