设计一个时间复杂度为 O(|V | + |E|) 的算法，用于查找有向图的根顶点（或报告 none 存在）
Design a O(|V | + |E|) time algorithm that finds a root vertex (or reports that none exists) of a directed graph
给定一个有向图 G = (V, E)。 G 中的根顶点是这样的顶点 v
G 中的任何其他顶点 u 都可以通过有向路径从 v 到达。如何设计找到根顶点（或报告 none 存在）的 O(|V| + |E|) 时间算法。
这是 O(|V| + |E|) 方法：
- 首先，我们可以将属于相同 SCC（强连通分量）的所有节点连接到超级节点，并在此基础上构建新图，我们称之为 SCC 图（它也被称为凝聚图，可以在 O(|V| + |E|))
中使用 Kosaraju 算法完成
- 因为根据定义 SCC 图不能有环，所以它是 DAG
- 对于 SCC 图中的每个节点，我们可以计算它的入度（指向它的边数）
- 现在如果 SCC 图中有超过 1 个入度为 0 的节点，则没有根
- 如果 SCC 图中只有一个入度为 0 的节点，那么原始图中属于入度为 0 的 SCC 图节点的任何节点都可以是根
给定一个有向图 G = (V, E)。 G 中的根顶点是这样的顶点 v G 中的任何其他顶点 u 都可以通过有向路径从 v 到达。如何设计找到根顶点（或报告 none 存在）的 O(|V| + |E|) 时间算法。
这是 O(|V| + |E|) 方法：
- 首先，我们可以将属于相同 SCC（强连通分量）的所有节点连接到超级节点，并在此基础上构建新图，我们称之为 SCC 图（它也被称为凝聚图，可以在 O(|V| + |E|)) 中使用 Kosaraju 算法完成
- 因为根据定义 SCC 图不能有环，所以它是 DAG
- 对于 SCC 图中的每个节点，我们可以计算它的入度（指向它的边数）
- 现在如果 SCC 图中有超过 1 个入度为 0 的节点，则没有根
- 如果 SCC 图中只有一个入度为 0 的节点，那么原始图中属于入度为 0 的 SCC 图节点的任何节点都可以是根