I need to build the following proof:
Let $G = (V, E)$ be a graph, and consider the forest $F$ obtained after executing $DFS(G)$. The components of $F$ are precisely the connected components of $G$.
But I have no idea on how to begin this. Could someone please give me an advice or a text book which I can find such proof or some help?
Edit
I think that this is essentially the question 22.3-12 from Cormen, Introduction to Algorithms
Show that we can use a depth-first search of an undirected graph G to identify the connected components of G, and that the depth-first forest contains as many trees as G has connected components. More precisely, show how to modify depth-first search so that it assigns to each vertex vv an integer label v.cc between 1 and k, where k is the number of connected components of G, such that u.cc = v.cc if and only if u and v are in the same connected component.
Could someone please verify that?
Let $V_1, . . . , V_n$ be the vertices in the various trees of the forest $F$.
Clearly $G[V_i]$ is connected since they are connected in the forest.
We want to show that there is no edge of the form $(u, v)$ with $u \in V_i$ and $v \in V_j$ . Suppose there is, and without loss of generality assume $fst[u] < fst[v]$. By the edge property, we have $fst[u] < fst[v] < lst[v] < lst[u]$. But this means $v$ is a descendant of $u \in F$ contradicting the fact they exist in different connected components of $F$. $\blacksquare$