我有以下作业问题:
DAG:设计一个线性时间算法 (O(|E|+|V|)) 来确定 DAG 是否有一个顶点可以从所有其他顶点到达，如果是，找一个。
现在我解决这个问题的方法如下: ->首先找到拓扑排序中最后出现的顶点(称为 V)。
->现在，判断反向图的每个顶点是否都可以从这个顶点V到达。
-> 如果每个顶点都是可达的，则顶点 V 是所需的顶点，否则图中没有任何其他顶点可达的顶点。
这种方法是否正确？
附言。这个问题的解决方案提示说我应该计算每个顶点的出度。但我无法理解计算出度有何帮助。
最佳答案
考虑一个弧 (u, v) ∈ E。由于图是非循环的，u 无法从 v 访问。因此 u 不能解决问题。由此可见，只有出度为零的顶点才是解。
此外，必须恰好有一个出度为零的顶点，否则问题无解。
我将其余部分留给读者作为练习。
关于algorithm - 确定 DAG 是否具有从所有其他顶点可达的顶点的线性时间算法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15716318/