在有向图中如何有效地计算图中彼此顶点的顶点数？
如果图中没有循环，则只能有一个这样的顶点，并且它的度数为零，并且没有其他顶点的度数为零。然后，您必须运行 DFS 以检查是否可以从该 DFS 访问所有其他顶点。所以答案是1或0，取决于DFS的结果。
如果存在循环，则循环中的所有顶点都具有此属性，或者它们都没有此属性。
如果检测到一个周期，请将循环中的所有顶点替换为一个顶点，并为该顶点保留一个标签，以指示它表示的顶点数。使用与上述相同的过程。即，签入度并从新节点运行DFS。答案将是零或标签。
检测周期可以使用 DFS 完成。
图中可能有多个周期。在这种情况下，您必须消除所有这些。您可以在DFS的一次线性传递中消除所有这些，但这很棘手。你也可以使用Tarjan的算法，正如btilly在他的答案中建议的那样。
使用 Tarjan 的强连接组件算法来检测所有循环，然后构建一个图形，将每个强连接组件折叠到单个节点。
现在在这个新图中，寻找没有边缘的顶点就足够了。 如果该顶点连接到其他每个顶点(可通过广度优先线性搜索进行验证(，则它来自的强连接组件中的所有内容都在您的集合中，否则您的集合中没有顶点。