algorithm - 如何查找从一个 SCC 到另一个 SCC 的路径是否存在？

Question

对于一个图，在找到强连通分量之后，如何找到彼此有路径的 SCC 的数量？我想查找是否有从 SCC1 到 SCC2 的路径。

Answer 1

你问了两件事：

如何找到彼此有路径的 SCC 的数量？

您可以从每个 SCC 运行 dfs 并保存您可以访问的 SCC。

例如：你从 SCC A 运行 dfs 可以到达 SCC B 和 C。（只需检查你正在访问的节点的 SCC 是什么）然后你从另一个 SCC D 运行 dfs 并到达 SCC A。此时你可以停止你的dfs，因为你已经计算出了其他的。

所以时间复杂度是O(n+m)

Answer 2

假设您只需要知道一个 SCC 是否可以从另一个 SCC 访问（真/假），您可以在发现一个 SCC 时为每个 SCC 分配一个身份，并为其所属的 SCC_ID 的每个节点创建一个映射。然后再次遍历原始图。如果存在一条边(u,v)，SCC_ID(u) != SCC_ID(v)则 SCC 可以从另一个边到达。

类似的问题：Kosaraju's Algorithm for find SCCs but keep track of edge between SCCs?

Answer 3

在使用 Kosaraju 查找 SCC 时（因为它很容易实现）为每个 SCC 发现者（也称为代表）分配一个唯一的 id，并且对于每个 SCC，将其 id 分配给它的所有成员。这将有助于记住哪个成员属于哪个 SCC。现在这个信息可以帮助我们把这个图压缩成一个图，每个节点都是SCC（representative ID）。在构建此压缩图时，您将知道哪个 SCC 连接到哪个 SCC。
您可以参考此链接以获取更多详细信息以及实现：https ://cp-algorithms.com/graph/strongly-connected-components.html 。