Question :
Suppose that G is a directed graph. In class we discussed an algorithm that will determine whether a given vertex can reach every other vertex in the graph (this is the 1-to-many reachability problem).
Consider the following similar problem: given graph G, is there any node in G that can reach every other node in G?
Such a node is called a "source node". We want to know whether any node of G is a source node. A trivial algorithm for this is to execute DFS n times, using each node in G as the start node of the DFS. But the total time for this algorithm is O( n* (n+m)).
Describe a linear time algorithm for this "does di-graph G have a source node problem".