我知道如果一组顶点是强连通组件的一部分,那么组件中的所有顶点都可以相互到达; 一个循环.
现在,我想使用这个事实,并声称如果图G =(V,E)有一个周期,那么该周期必须在scc内.
换句话说,所有周期都必须是scc的一部分(我的主张).
我想不出我的主张的任何反例,所以我想知道图中是否有任何不属于scc的周期.
或者是我的主张,对吗？
令 e = (u, v) 为所讨论的边。我们注意到，当且仅当 u 连接到 G{e} 中的 v 时，这是 G 中包含 e 的循环。我们的算法仅在 G{e} 上从 u 运行 DFS，如果从 u 可以到达 v，则输出 yes，否则输出 no。该算法以线性时间运行，就像 DFS 以线性时间运行一样（我们只运行部分 DFS 算法来查找包含 u 的分量）。这个算法显然是正确的。如果u通过某个路径p连接到G{e}中的v，我们可以将边e添加到p以形成环。否则，从 G 中删除 e 会断开 u 和 v 的连接。