遍历整个图的最小节点数
minimum number of nodes that traverse entire graph
注意：问题完全改变了。
在下图中，如果我们 select 节点 0 和 2，我们可以遍历整个图。我正在寻找一种 returns 这两个节点的有效算法。请注意，这既不是顶点覆盖问题也不是支配集问题，因为我们不需要 select 节点 3。我们说，如果我们 select 节点 0，我们可以从在那里，如果我们 select 节点 2，我们可以转到节点 3，然后从那里转到节点 4。
如果我运行一个SCC算法，它发现所有顶点都是不同的SCC，我不能从那里去任何地方：
C:\>project2 ../../input.txt o.txt
Following are strongly connected components in given graph (Each line is a different SCC)
2
4
3
0
1
如果图中没有环，即图是有向无环图（DAG），那么我们只需要计算每个节点的入度即可。入度为0的节点集合是需要的集合。
如果你对入度不熟悉，如果有一条边a->b那么b的入度增加1 .
这是有效的，因为如果有一条边 a->b 即 b 有一个入度，这意味着有一个节点 a 可以到达 b。因此，将节点 a 包含到集合中总是比 b 更好。入度为 0 的节点没有其他方法可以访问，除非我们从节点本身开始。所以它会被包含在集合中。
如果图中有环，我们搜索强连通分量（SCC）。然后我们构建了一个将 SCC 视为一个节点的新图，并从连接两个不同 SCC 的初始图中添加边。新图将是 DAG。然后我们可以应用上面的过程来找到所需的节点集。
注意：问题完全改变了。
在下图中，如果我们 select 节点 0 和 2，我们可以遍历整个图。我正在寻找一种 returns 这两个节点的有效算法。请注意，这既不是顶点覆盖问题也不是支配集问题，因为我们不需要 select 节点 3。我们说，如果我们 select 节点 0，我们可以从在那里，如果我们 select 节点 2，我们可以转到节点 3，然后从那里转到节点 4。
如果我运行一个SCC算法，它发现所有顶点都是不同的SCC，我不能从那里去任何地方：
C:\>project2 ../../input.txt o.txt
Following are strongly connected components in given graph (Each line is a different SCC)
2
4
3
0
1
如果图中没有环，即图是有向无环图（DAG），那么我们只需要计算每个节点的入度即可。入度为0的节点集合是需要的集合。
如果你对入度不熟悉，如果有一条边a->b那么b的入度增加1 .
这是有效的，因为如果有一条边 a->b 即 b 有一个入度，这意味着有一个节点 a 可以到达 b。因此，将节点 a 包含到集合中总是比 b 更好。入度为 0 的节点没有其他方法可以访问，除非我们从节点本身开始。所以它会被包含在集合中。
如果图中有环，我们搜索强连通分量（SCC）。然后我们构建了一个将 SCC 视为一个节点的新图，并从连接两个不同 SCC 的初始图中添加边。新图将是 DAG。然后我们可以应用上面的过程来找到所需的节点集。