单连通图？

Question

单连通图是一个有向图，它最多有1条路从u到v∀u，v。

我想出了以下解决办法：

1. 从任何顶点运行DFS。
2. 现在再次运行DFS，但这次从顶点开始，以减少完成时间。只对某些以前的DFS中未访问的顶点运行此DFS。如果我们在同一分量中找到一个交叉边或一个前向边，那么它就不是单连通的。
3. 如果所有顶点都已完成，且没有这样的前向边交叉，则单连通。

O(V+E)

是这样的吗？或者有没有更好的解决方案。

更新:最简单的1条路径。

Answer 1

如果下列两个条件之一满足下列条件之一，则图不是单连通的：

1. 在同一个组件中，当您执行DFS时，您会得到从一个顶点到另一个已经完成搜索的顶点的路径(当它被标记为黑色时)。
2. 当一个节点指向来自另一个组件的>=2顶点时，如果两个顶点有一个连接，那么它就不是单连通的。但这需要你保持一片深度第一的森林。

Answer 2

单连通分量是属于同一实体的任意有向图。它可能不一定是一个DAG，可以包含一个混合循环。

每个节点至少有一些链接(进来或输出)，每个节点在同一组件中至少有一个节点。我们所需要做的就是检查同一组件是否存在这样的链接。

单连通分量可计算如下：

• 将图转换为它的无向等价
• 运行DFS并设置每个节点的公共领导。

在所有节点上运行一个迭代。如果所有节点具有相同的公共领导，则图的无向版本是单连通的。

否则，它包含多个单连通子图，由其相应的领导者表示。

Answer 3

是这样的吗？

不，这不对。考虑以下图，它不是单连通的。第一个组件来自以顶点b开头的dfs，第二个组件来自以顶点a开头的dfs。

​

​

正确的一个：

如果DFS满足以下三个条件，则图是单连通的：

1. 无翼边
2. 在同一组件中没有交叉边
3. 任何两个组件之间的交叉边不超过一个。