I am trying to create an algorithm in linear time where if given a directed acyclic graph I can add edges to make it strongly connected components.I believe I have an algorithm to identify sources and sinks in the input list of edges in form1 22 53 1 etcAnd I know that the minimum number of edges to be added in order to create connected components is equal to MAX(sources,sinks).My question is, is there a way to come up with where I should add edges so that I can have the minimum number and still be linear complexity?Here is an example of what I'm after.Given this input edges:1 31 42 32 45 75 86 86 9Output these edges to be added:3 14 57 68 19 2
If I have sources and sinks of a DAG can I find the minimum number of edges to be added to make it Strongly Connected?
algorithms;graph theory;graphs