algorithm - 如果图有交叉边，是否是单连通的

Question

当我看“算法介绍3”时，在下面遇到这个问题。

22.3-13 * 如果 u -> v 意味着 G 对于所有顶点 V 至多包含一条从 u 到 v 的简单路径，则有向图 G 是单连通的。给出一个有效的算法来确定一个有向图是否是单连通的。

一些答案，例如“从每个顶点运行一次 DFS。当且仅当没有前向边且没有交叉边时，该图是单连接的”

但我怀疑这种情况。例如，如果图的所有边（A->D，D->E，E->A，B->C，C->A），DFS从A开始，因此C->A是交叉边，但I认为这个图是单连通的。抱歉，由于stackoverflow的许可，我无法上传图片。

Answer 1

图中可能存在交叉边，也可能存在循环，并且图将是单连通的（SC）。如果我们有前向边，很明显我们有 2 条到目的地 V 的路径。但是在这种情况下，如果我们有交叉边图不是 SC:: 假设 ab 或 zb 是图中的交叉边，如果有路径a和z之间的图不是SC，如果我们没有相同的路径它绝对是SC。如果 ab(或 zb) 是我们的交叉边缘，则 a 和 z 之间不应该有路径。