问如果我们反转一个图(使用Kosaraju的算法)，SCC模式会改变吗？

EN

不，即使当图被反转时，图的SCC也将保持不变，这是kosaraju关于SCC的算法中非常重要的一点，只有SCC之间的链接才是反向的。Kosaraju的算法利用这一事实在反向图上评估DFS，该图为SCC提供了更高的完成时间值，后者更接近接收器SCC。由于Sink SCC没有向另一个SCC发出的边缘，因此对其进行DFS计算，将SCC作为整体连通分量，并允许将图分解成一个具有相似性质的子图，我们再次应用DFS来得到另一个SCC。

如果您查看algorithm，您将看到：

“转置图(每个边的方向相反的相同图)与原图完全相同的强连通分量。”

(强连接组件是一个可以从组件中的每个顶点到每个其他顶点的组件，如果您反转所有链接，这仍然有效)。当然，连接不同组件的链接将被反转，所以我希望您能够得到不同顺序的组件。