如何在O(n + m)中的有向图中找到母顶点？

Question

有向图G =(V,E)中的母顶点是顶点v,使得所有其他顶点G可以通过来自v的有向路径到达给出O(n + m)算法以测试图G是否包含母亲顶点.

(c)来自Skiena手册

只找到O(n(n + m))方式

Answer 1

我看到了解决方案。我认为我们不需要找到SCC。只需从随机顶点执行 DFS，然后从上次完成时间的顶点执行 DFS。如果有一个母顶点，那么它一定是这个。