algorithmtime-complexitygraph-theorydirected-graphedges# Given an directed acyclic graph, create a strategy so that there is a bidirectional path between all possible Vertices

## Given an directed acyclic graph, create a strategy so that there is a bidirectional path between all possible Vertices

You can attain this by adding edges. Propose a strategy for solving this with adding as little edges as possible A Vertice on the input graph can be without edges.

EXAMPLE: To solve this graph the most efficient way, we need to add ONLY 2 edges:

Keep in mind that the algorithm doesn't need to be perfect, also NO NEED to code anything (unless you want to:)).

Solution

Consider a DAG that has m vertices with in-degree 0 and n vertices with out-degree 0:

Obviously, you will need to add m edges incoming to the in-degree 0 vertices, and n edges outgoing from the out-degree 0 vertices, so the best you can hope for is max(m,n) new edges. We can achieve this.

First, if m > n, then connect in-degree 0 vertices until m = n. Otherwise connect out-degree 0 vertices until m = n.

Now we have m=n, which we will maintain:

- Find a vertex with in-degree 0 that
*doesn't*reach all the vertices with out-degree 0. If there isn't one, then connect out-degree 0 vertices arbitrarily to in-degree 0 vertices and you're all done. - Otherwise, connect an out-degree 0 vertex that it
*does*reach to an in-degree 0 vertex that reaches an out-degree 0 vertex that it*doesn't*reach. This reduces m and n by 1. - Repeat until you're done.

- How to generate uniformly distributed subintervals of an interval?
- Generating random number in a non-power-of-2 range from random bits
- Algorithm - Search and Replace a string
- Looking for a branchless algorithm for converting a specific set of 4-bit integers
- Different results for XIRR between Excel and ExcelFinancialFunctions 3.2.0
- Find four,whose sum equals to target
- A* algorithm can't find the goal in Python
- Efficiently getting all divisors of a given number
- Are there any existed API to split IEnumerable<T> to many Vector<T> in CSharp？
- Generating all divisors of a number given its prime factorization
- Efficient way to insert a number into a sorted array of numbers?
- BFS Maximize Minimum Distance from a Monster along a path
- Is there effective algorithm that will return all different combination?
- Big O of algorithm that steps over array recursively
- Modification of Dijkstra's algorithm to make it work with negative weights and its time complexity
- Traversing/Moving over an unfolded cube
- Fibonacci Recursion using Golden Ratio(Golden Number)
- Karatsuba implementation in C
- Why is O(n) better than O( nlog(n) )?
- What is Sliding Window Algorithm? Examples?
- How to write a function to navigate through a non-binary tree?
- Evenly distribute QDate values into certain number of slots
- Find max product using divide and conqure in O(n) time
- Cache-friendly sqare matrix transposition logic issue
- Why doesn't Dijkstra's algorithm work for negative weight edges?
- Fast Convertion From Adjacency List to Edge List
- I convert ASCII words into numbers but am stuck trying to decode them. How to convert 1=a, 2=b, 28=ab etc? (psudeocode okay)
- Reversing the word order in a string in place
- Trying to make a 2x2 rubik's cube solving algorithm , how do i find the solution path (DFS)?
- question about missing element in array