algorithm - 确定有向图是否单连通的最有效方法是什么？

Question

我正在做一个作业，其中一个问题要求推导出一种算法来检查有向图 G=(V,E) 是否单连通(对于所有不同的图，从 u 到 v 至多有一条简单路径V 的顶点 u,v。

当然你可以暴力破解，我现在就是这样做的，但我想知道有没有更有效的方法。谁能指出我正确的方向？

Answer 1

这个问题有更好的答案。你可以在 O(|V|^2) 中做到这一点。并且付出更多的努力，您可以在线性时间内完成。

首先你找到 G 的强连通分量。在每个强分量中，你搜索以找到这种情况:1)如果这个分量有前向边，则不是单连通的，2)如果这个组件中有交叉边，则不是单连通的，3) 如果以顶点u为根的树中至少有两条后向边到u的真祖先，则它不是单连通的。

这可以在 O(E) 中完成。 (我认为除了案例 3​​。我无法很好地实现它!!)。

如果以上情况都没有发生，你应该检查G^SCC(图G，强成分被单节点替换)是否有交叉边或前向边，因为我们没有后边，它可以通过在 O(|V|^2) 中对该图的每个顶点重复 dfs 来完成。