### chaotic_iak's blog

By chaotic_iak, 10 years ago,

I was working on an interesting problem. (Tip: Homework of algorithm courses can be fun!)

Find the minimum number of (directed) edges to introduce into a directed graph to make it strongly connected (from any vertex you can go to any other vertex). Also, find one configuration of edges to add that satisfies the property and reaches the minimum.

I wonder if this problem is a well-known problem, and if any, what name it is known with? I saw this Stack Overflow question which asks about the minimum number of edges only, not finding one such configuration, and it's said to be "a really classical problem".

I also wonder if there is a more efficient algorithm. My algorithm works in O(V3), which involves several steps to reduce the graph in question into a directed acyclic graph, a weakly connected directed acyclic graph, a connected bipartite graph, and finally giving the answer. A friend says that there is a literature on the internet giving algorithm, but I haven't managed to find it. Or is there an even better algorithm?

• +18

| Write comment?
 » 10 years ago, # | ← Rev. 2 →   +13 There was a similar post in Russian half a year ago. You can find paper in English in the comments and my comment in Russian which briefly describes solution (not sure if it's same as in paper).
•  » » 9 years ago, # ^ |   0 Hi. Will the answer remain same if the graph if initially disconnected?
•  » » » 9 years ago, # ^ |   0 I think so.
 » 10 years ago, # |   +10 Divide graph into strongly connected components and you will get a DAG. Number of edges you need to add is a maximum of numbers of vertices with 0 indegree and 0 outdegree (vertices = SCCs). That is a trivial lower bound, but to show that it is sufficient it is significantly harder :P.
•  » » 10 years ago, # ^ |   0 For searching the number, it has been given in the Stack Overflow thread above. Proving it's sufficient is simple; just give any algorithm that works and prove its correctness. Optimizing the algorithm is the hard part.
•  » » » 10 years ago, # ^ |   0 For the algorithm I described in my comment providing the algorithm was the hard part, optimization from O(N3) to O(N) took only one very simple observation.
•  » » » » 6 years ago, # ^ |   0 Could you show me that observation?
•  » » » » » 6 years ago, # ^ |   0 Sure. The cubic solution I've mentioned was about finding the maximal matching between sources and sinks, and then adding some edges.The observation is that we don't really need "maximal" matching, we only need a "blocking" matching (like in Dinic's algorithm), i.e. one which cannot be extended by adding another disjoint path from a source to a sink. And finding "blocking" matching is significantly easier: you just run DFS while you can.
•  » » 6 years ago, # ^ |   +5 For that trivial lower bound solution, should we add vertices with 0 degree to both numbers of vertices with 0 indegree and 0 outdegree ?
•  » » » 6 years ago, # ^ |   0 Well think about it. Would the graph be strongly connected if you only added in-edges to those vertices? Why? What might be the intuition for adding these edges anyway?
 » 5 years ago, # |   -22 There is a question which exactly asks this. https://codeforces.com/contest/22/problem/E
•  » » 4 years ago, # ^ | ← Rev. 2 →   -9 Thank you. It's exactly same concept.
 » 20 months ago, # |   0 Problem https://codeforces.com/gym/103960/problem/H asks exactly that.
 » 14 months ago, # |   0 I know this is an old post, but I had this question too and it took me some time to find out the answer.This post is still one of the top google searches for "how to add edges to make a strongly connected graph", so I'm linking to this Stack Overflow article which describes the algorithm for creating the configuration: https://stackoverflow.com/questions/12681785/creating-strongly-connected-components-from-a-dag
 » 10 months ago, # |   -8 I have coded it
•  » » 5 months ago, # ^ |   +9 Thank you !Unfortunately the link you provided is now broken, but it can be easily found at the moved repository, i've also added it to my lib, and there is a CSES exercise which asks exactly for it : https://cses.fi/problemset/task/1685
•  » » » 5 months ago, # ^ |   0 Unrelated but I support how codeforces has the downvote. I hope they never remove it