Thank you, Waqar Ahmed (CodenCode). You contributed a lot to the cp community. I will always be grateful to you. I wish you a very good and happy future.

Thank you.

DFS:

First let's forget about the programming thing. Now we are given a graph (some nodes and edges, a connected component)

Now if we just make the graph matrix (adjacency list), and now if we follow the following process:

Suppose we are at some node right now, call it curr.
Now, if curr's currently considered child is already visited (i.e, already in the dfs tree), then just mark them connected in the dfs tree with some lighter color.
Else if curr's currently considered child is non visited yet. Just make it visited and go on it.
Else if all the children have been considered already, and we got no more, then just backtrack to the parent.

if we follow the above steps, then the dfs will definitely be finite (because finite no. of non-visited nodes) and will make all the nodes of the graph visited. why every node will be visited by the end? suppose there's some node x. and consider any path between root and x. R->a1->a2->a3...->x So let us say that kth node of the path is in the dfs tree, then k+1th will be present too. Why? because there is an edge between kth and k+1th node. So by the time kth node would like to call k+1th node, it would already be present in the graph (Just think the graph is prepared till this point only, not entirely) else if it is not visited yet. then kth will call it and it will be visited.

The dfs tree of a graph looks like:

Look in it

And one more observation is : In a dfs tree, a back-edge from some node, is always going to be connected to some of its ancestor only, and same for forward edge (just with its desecendants)

Proof is in the above site itself.

Now we have to convert the above dfs procedure into a program.

So consider this following recursive program developed thru intution:

dfs(curr,isVis,graph){
	isVis[curr]=1;
	cout<<curr<<" ";
	for(auto x:graph[curr]){
		if(!isVis[x]){
			dfs(x,isVis,graph);		
		}
	}
}

Now, let's prove the correctness of the above intuition based program.

In it, suppose if some node is visited, then we are imagining a backedge, with some lighter color. So, suppose till some steps, the program runs fine (i.e, it runs same as the procedure dfs described above the program) So the next will be done fine too. why? Because it just could be one of the following things as the next step : say the next considered node is already visited (then our isVis would be 1 for that). So we are imagining a back-edge being made. say the next considered node is non-visited yet (then we are calling dfs() for that node. hence we are making it visited. (Visualize it as going down) say no node is remaining now, then it will backtrack.

These are the things which we wanted to do at any time, in the procedure of dfs. Hence the program works fine. The program will print the nodes in the order they are getting called or getting visited.

I know I couldn't explain very well. I hope it helps. Thanks.