algorithm to test whether G contains an arborescence
graph
Solution
What you are exactly looking for is the so called Edmond's algorithm. The minimum spanning tree algorithms are not going to work on directed graphs but that is the idea. The MST problem became arborescence problem when the graph is directed and arborescence is what you have described above.
The naive complexity is O(EV) just like the Prim's algorithm for undirected MST problem but I am sure there are faster implementations of it.
For more information you can check the wiki page:
Edmonds Algorithm
Problem
An arborescence of a directed graph G is a rooted tree such that there is a directed path from the root to every other vertex in the graph. Give an efficient and correct algorithm to test whether G contains an arborescence, and its time complexity. I could only think of running DFS/BFS from every node till in one of the DFS all the nodes are covered. I thought of using min spanning tree algorithm, but that is also only for un-directed graphs is there any other efficient algorithm for this ? I found a follow up question which state there is a O(n+m) algorithm for the same, can anybody help what could be the solution ?