algorithm - 使用强连通分量算法作为循环检测

Question

我知道，如果一组顶点是强连接组件的一部分，那么组件内的所有这些顶点都可以相互连接；一个循环。

现在，我想利用这个事实并声称如果图 G = (V,E) 有一个循环，那么该循环必须在 scc 内。

换句话说，所有周期都必须是 scc 的一部分（我的主张）。

我想不出任何反例来反驳我的主张，所以我想知道图中是否有任何不属于 scc 的循环。
或者我的主张是正确的吗？

Answer 1

这是正确的。如果一组顶点在一个循环中，那么它们都是可以相互访问的（通过绕过循环），因此根据定义它们是一个 SCC。

话虽如此，这不完全是编程问题:)

Answer 2

让 e = (u, v) 成为有问题的边。我们注意到这是 G 中包含 e 的环当且仅当 u 连接到 G{e} 中的 v。我们的算法只是在 G{e} 上从 u 运行 DFS，如果 v 可以从 u 到达，则输出 yes，否则输出 no。该算法在线性时间中运行，因为 DFS 在线性时间中运行（我们只运行 DFS 算法的一部分来查找包含 u 的组件）。这个算法显然是正确的。如果 u 通过某个路径 p 连接到 G{e} 中的 v，我们可以将边 e 添加到 p 以形成一个循环。否则，从 G 中删除 e 会断开 u 和 v。