1
$\begingroup$

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.

  • 0
    @Nicolas Villanueva: Can u give a clue how I prove that if I have a tree in a contracted graph then I have a tree in the graph. I tried everything: induction, contradiction..2011-05-04

0 Answers 0