Cheap and Secure Web Hosting Provider : See Now

What edge-set is required to make a non-cyclic directed disconnected graph initial?

, , No Comments
Problem Detail: 

Is there an algorithm to find the minimum set of edges required from a new node in order to make a disconnected directed graph initial?

Example -

input:

a -> b; b -> c; b -> d; e -> f; f -> g; 

input

output:

n -> a; n -> e; 

output

Result:

result

Thanks!

Asked By : Lyndon Maydwell

Answered By : Yuval Filmus

Assuming that "initial" means connected and having a single source, you can do no better than adding an edge to each source.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/53581

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback