如果图有交叉边，不管它是不是单连通的

Question

当我看“算法导论3”时，遇到了下面这个问题。

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

一些人回答说：“从每个顶点运行一次DFS。当且仅当没有正向边和交叉边时，图才是单连通的。”

但我对这种情况表示怀疑。例如，如果图的所有边(A->D，D->E，E->A，B->C，C->A)，DFS从A开始，因此C->A是交叉边，但我认为这个图是单连通的。很抱歉，我无法上传图片，因为堆栈溢出权限。

Answer 1

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