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。我不是很清楚，希望您明白这一点。