I need help to prove a classical graph problem about strongly connected components.
Difference between en2 and en3, changed 110 character(s)
I have come to read [this](https://stackoverflow.com/questions/14305236/minimal-addition-to-strongly-connected-graph) stackoverflow post. It basically asks this-`I have a set of nodes and set of directed edges between them. The edges have no weight. How can I found minimal number of edges which has to be added to make the graph strongly connected?`↵

[This](https://stackoverflow.com/a/14318315) answer gives a solution to this problem↵

It's a really classical graph problem.↵

    1. Run algorithm like Tarjan-SCC algorithm to find all SCCs. Consider each SCC as a new vertice, link a edge between these new vertices according to the origin graph, we can get a new graph. Obviously, the new graph is a Directed Acyclic Graph(DAG).↵
    2. In the DAG, find all vertices whose in-degree is 0, we define them {X}; find all vertices whose out-degree is 0, we define them {Y}.↵
    3. If DAG has only one vertice, the answer is 0; otherwise, the answer is max(|X|, |Y|).↵

I am not been able to prove the third point. How is the answer "max(|X|, |Y|)"?  Can anyone help me?


Edit: I need this to solve this lightoj [problem](http://lightoj.com/volume_showproblem.php?problem=1210).

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English prince_of_crows 2018-06-13 04:53:08 110
en2 English prince_of_crows 2018-06-13 04:48:12 0 (published)
en1 English prince_of_crows 2018-06-13 04:47:15 1159 Initial revision (saved to drafts)