Graph Algorithm Problem:

Let's say that a graph is "accessible'' if it contains a vertex v that can reach all the other vertices. In this case, we call v an "access point'' of the graph.

Suppose that we want to design an algorithm that, for a given directed acyclic graph, returns a "certificate'' that makes it easy to check whether the graph is accessible or not. If the graph is accessible, the algorithm should output, as the certificate, a vertex v that can reach all the others. (Note that, given v, verifying that the graph is accessible can be done with a reachability computation from v.) If the graph is not accessible, what simple structure can we use as a certificate of this fact? In other words, what information of a non-accessible graph guarantees that it is not accessible, and is easy to verify (in constant time)? Describe a linear-time algorithm for finding this structure in a directed acyclic graph that is not accessible.