algorithm - 查找强连接组件之间的弧

Question

有了图及其所有强连通分量，我想知道找到连接两个 SCC 的弧的最有效方法是什么。我找到的所有解决方案都涉及运行所有节点，我想知道是否有一种方法可以在不这样做的情况下执行此操作，特别是在我用来在图中找到 SCC 的 Tarjan 算法期间。无论如何以线性方式进行？

非常感谢!

Answer 1

只需将不同顶点之间的连接设为一个指针，并将给定 SCC 的每个顶点的值更改为相同的值即可。

这样你就不必“搜索”任何东西。

Ex: 1->2->3->4->1

这样你就可以得到一个包含 1234 的 SCC

then 4->5
and 5->6->7->5

如果您将连接存储为指针，您只需将顶点 5 中的值 5 更改为 6，然后转到从 4 到 5 的指针，您将获得 6。我不是很清楚希望你明白这个想法。