设计一个O（| V | + | E |）时间算法，找出有向图的根顶点（或不存在的报告）

Question

给定有向图G =（V，E）。 G中的根顶点是顶点v，使得G中的任何其他顶点u可以通过有向路径从v到达。如何设计一个O（| V | + | E |）时间算法，找到一个根顶点（或报告不存在）。

Answer 1

这里是O（| V | + | E |）方法：

1. 首先，我们可以将属于同一个SCC（强连接组件）的所有节点加入到超级节点并基于此构建新图，我们称之为SCC图（它也称为凝聚图，可以用O中的Kosaraju算法完成） （| V | + | E |））
2. 因为SCC图形根据定义不能有循环，所以它是DAG
3. 对于SCC图中的每个节点，我们可以计算它的度数（指向它的边数）
4. 现在，如果SCC图中有超过1个节点，其中度为0则没有根
5. 如果SCC图中只有一个节点为0度，则原始图中任何节点都是0度的SCC图节点的一部分可以是根节点