CODEWITHSUNDEEP
algorithmgraph
Seth Rollins
Seth Rollins

Reputation: 29

Minimum number of edges to create to make directed graph connected from root

What is the minimum number of new edges that need to be built to make all the nodes reachable from the root?

Given directed graph and index of root.

I tried finding all the components (if the graph was undirected), then finding the number of nodes with no parents and I call that number sol. I go through every component and ask for number of orphan nodes. If it has none and it does not contain the root then I add 1 to sol, because I should connect that component to root. This is possible when the component is a cycle. Special case is component that includes root. If it doesn't have a node with 0 parent, then sol stays the same, if it does have any, then sol becomes sol + number_of_those_nodes (if root has a parent) or sol + number_of_those_nodes - 1(otherwise)

Can you help me solve this and create a valid pseudo code.

Upvotes: 2

Views: 2087

Answers (1)

yeputons
yeputons

Reputation: 9238

Idea 1: Find condensation of the graph (graph of strongly connected components). Now the graph is acyclic, but the answer is the same: it doesn't make any sense to add an edge inside strongly connected component and it doesn't matter how exactly are distinct strongly connected components are connected. Our problem is now the same, but on acyclic graph (the root becomes its strongly connected component).

Idea 2: note that for all source vertexes (vertexes with inbound degree of zero) except for the root we should add at least one edge (the inbound one). That gives us a lower bound on the answer.

Idea 3: if that lower bound is zero, that bound can be achieved as the graph is already good.

Proof by contradiction: take a look at arbitrary vertex X unreached from the root. It has at least one inbound edge, otherwise our lower bound would not be zero. Let's say it has an inbound edge from arbitrary vertex Y. If Y is reached, then X would also be reached, so Y is unreached. Repeat the same argument for Y, and now we've got an infinite path of vertexes. But it cannot has the same vertex twice, otherwise there would be a loop in our graph, but it's already condensated. On the other hand, there is finite number of vertexes. Q.E.D.

Idea 4: if that lower bound is greater than zero, we can draw edges from root to each source vertex, lower that lower bound to zero and apply idea 3, thus achieving the exact lower bound.

Upvotes: 2

Related Questions