prince_of_crows's blog

By prince_of_crows, history, 6 years ago, In English

I have come to read this 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 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.

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by prince_of_crows (previous revision, new revision, compare).

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I looked up this question previously and found this post. http://codeforces.com/blog/entry/15102

I believe the paper mentioned in the first comment gives a proof for your 3rd point.