有了图及其所有强连通分量，我想知道找到连接两个 SCC 的弧的最有效方法是什么。我找到的所有解决方案都涉及运行所有节点，我想知道是否有一种方法可以在不这样做的情况下执行此操作，特别是在我用来在图中找到 SCC 的 Tarjan 算法期间。无论如何以线性方式进行？
非常感谢!
最佳答案
只需将不同顶点之间的连接设为一个指针，并将给定 SCC 的每个顶点的值更改为相同的值即可。
这样你就不必“搜索”任何东西。
Ex: 1->2->3->4->1
这样你就可以得到一个包含 1234 的 SCC
then 4->5
and 5->6->7->5
如果您将连接存储为指针，您只需将顶点 5 中的值 5 更改为 6，然后转到从 4 到 5 的指针，您将获得 6。 我不是很清楚希望你明白这个想法。
关于algorithm - 查找强连接组件之间的弧，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/49352911/