Linear time algorithm to determine whether a DAG has a vertex reachable from every other vertex?
algorithm, directed-acyclic-graphs, graph, graph-theory, language-agnostic
Solution
Consider an arc `(u, v) ∈ E`. Since the graph is acyclic, `u` is not reachable from `v`. Thus `u` cannot be the solution to the problem. From this it follows that only a vertex of outdegree zero can be a solution.
Furthermore, there has to be exactly one vertex with outdegree zero, or the problem has no solution.
I leave the rest as an exercise for the reader.
Problem
I have the following homework question: DAG: Design a linear-time algorithm (`O(|E|+|V|)`) to determine whether a DAG has a vertex that is reachable from every other vertex, and if so, find one. Now my approach to solving this question is as follows: ->First find the vertex that comes last in the topological ordering(call it V). ->Now, determine if every vertex of the reverse graph is reachable from this vertex V. -> If every vertex is reachable, then the vertex V is the required vertex, otherwise there is no vertex in the graph that is reachable from every other vertex. Is this approach correct? PS. The hint for this question's solution says that I should compute the outdegree of each vertex. But I cannot understand how computing the outdegree helps.