假设我们在有向图上运行 sharir kosaraju 算法。我们在这个图上有一个弧线（u，v）。在此算法中，我们有两个 DFS 传递。现在假设我们将顶点 u 插入到第一个深度树 T 中。v可以出现在哪里？它是在更早创建的另一棵树中还是在较晚创建的另一棵树中？提前感谢！
我正在学习考试...所以我想这是一种家庭作业，但我真的不知道！
Kosaraju 的算法基于这样一个事实，即图的转置具有与原始图相同数量的强连接组件 （SCC）。
1） 你有一个图 G 和一个空的堆栈 S。
2）虽然S不包含G中的所有节点，但选择一个随机顶点U并在u上执行DFS。在此 DFS 期间浏览完节点 v 后，在 S 中推送节点 v。
回到你的问题，如果有一个有向边（u，v），v肯定会在u之前插入堆栈S中。但是，在插入 v 和插入 u 之间可以有更多的节点。
3）你通过从堆栈S弹出顶点来执行G的转置的DFS，直到S为空。这将在图 G 中获得所有 SCC。
维基：http://en.wikipedia.org/wiki/Kosaraju%27s_algorithm 很有启发性。我已经实现了该算法，可在此处获得。
http://khanna111.com/wordPressBlog/2012/04/11/strongly-connected-components-of-a-graph/
要了解的主要事情是，在传递后的第一步中，堆栈中的顶级元素将是父元素，在第二步中，它们将更早地弹出并在转置上运行，其中在原始图形中强连接的节点将在转置中保持强连接。
第一次通过的全部原因是让父母到达堆栈的顶部。