在有向图中查找所有根

Question

我需要找到一种算法,用于在有向图中找到所有根,在O(n + m)中.

我有一个查找单个根的算法:

1. 在V中的某些v上运行DFS(v).如果结果是单个生成树,则v是根.否则,结果就是一片树林.然后:
2. 在最后一棵树的根目录上运行DFS(u).如果结果是单个生成树,则u是根.否则,图中没有根.

现在,如果我想找到所有的根,那么每次在最后一棵树的不同顶点上运行上述算法O(n)次的最佳方法是什么？假设我找到了一个根,如果存在另一个根,那么它必须在最后一棵树上,那么如果我继续运行上述算法直到收到"没有根存在"或者直到遍历所有顶点,那么它是O(n + m)吗？

提前致谢 !

Answer 1

两种做法：

1. 反转图形并计算 DFS-loop() 并注意没有出边的顶点（如 Abhishek 所说）。

2. 更高效 - 在图上运行 DFS-loop() 并使用真假表跟踪没有传入边的顶点。

在最坏的情况下，方法 1 需要两倍的时间。