# Strongly-Connected Components's Graph by running DFS

I got this question, and I'd be happy for help.

G=(V,E). $G_S$ is a Strongly-Connected Components's Graph.

I need to prove, that if there is only one Component ($C_0$) which is not with incoming edge, that there is a DFS running in G that ruturn one tree, and only him.

I thought to start from the vertex with the lattest finish time in $C_0$. It works on my examples, but I dont know how to prove it, and if it is correct.

Thank you for your help.

-
Think of that Component as being the source of your graph. Also, think of each CC (Connected Component) as being it's own vertex in a graph. – Nicolas Villanueva May 3 '11 at 10:16
@Nicolas Villanueva: Thank u, but I didn't understand What do you mean about thinking of each CC (Connected Component) as being it's own vertex in a graph? CC is composed from many vertex of the graph G. Do you talk about $G$ or G_s$? – Amir May 3 '11 at 11:48 @Amir Yes each individual CC is a set of vertices, but you can combine the vertices into 1 vertex. For example, look at Figure 2 of cs.berkeley.edu/~vazirani/s99cs170/notes/lec12.pdf on page 2. – Nicolas Villanueva May 3 '11 at 11:58 @Nicolas Villanueva: sorry, but I still don't understand how it helps me. The Graph$G_s\$ is given, and I need to prove that there is DFS running on G. Now, How it helps me to combine all the vertex to CC in G? I need to prove for each CC that there is only one tree from DFS's scanning? – Amir May 3 '11 at 12:20
@Amir Yes. If you contract all CC's so they are represented by a single vertex, then only one of those contracted vertices will not have an in-deg = 0, this will be your source/starting vertex for DFS. I have finals in about an hour, but that should hopefully get you started in the correct direction – Nicolas Villanueva May 3 '11 at 15:18