我正在做一项作业，其中一个问题要求导出一种算法来检查有向图 G=(V,E) 是否是单连通的（对于所有不同的顶点 u 至多有一条从 u 到 v 的简单路径， v 的 v。
当然你可以暴力检查它，这就是我现在正在做的，但我想知道是否有更有效的方法。有人能指出我正确的方向吗？
对于这个问题有一个更好的答案。你可以在 O(|V|^2) 内做到这一点。只要付出更多努力，您就可以在线性时间内完成。
首先你找到G的强连通分量。在每个强分量中，你搜索找到这种情况：
1) 如果该组件中存在前向边缘，则它不是单连接的，
2）如果该组件中有交叉边，则它不是单连接的，
3) 如果树中至少有两个以顶点 u 为根的后边到 u 的真祖先，则它不是单连接的。
这可以在 O(E) 内完成。 （我认为除了情况3。我无法很好地实现它！！）。
如果上述情况都没有发生，你应该检查G^SCC上是否有交叉边或前向边（图G，用单个节点替换强组件），因为我们没有后边，可以通过以下方式完成在 O(|V|^2) 内对该图的每个顶点重复 dfs。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
