graph-algorithm - 单连通图？

Question

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

我想到了以下解决方案：

1. 从任何顶点运行 DFS。
2. 现在再次运行 DFS，但这次从顶点开始，按完成时间递减的顺序。仅对以前的某些 DFS 中未访问的顶点运行此 DFS。如果我们在同一个组件中找到交叉边或前边，则它不是单连接的。
3. 如果所有顶点都完成并且没有这样的前边交叉，则单连接。

O(V+E)

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

更新：最多 1 个简单路径。

Answer 1

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

1. 在同一个组件中，当您执行 DFS 时，您会得到一条从一个顶点到另一个已经完成搜索的顶点的道路（当它被标记为黑色时）

2. 当一个节点从另一个组件指向 >=2 个顶点时，如果 2 个顶点有连接，则它不是单连接的。但这需要你保留一个深度优先的森林。

Answer 2

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

每个节点至少有一些链接（传入或传出），同一组件中的每个节点至少有一个节点。我们需要做的就是检查同一个组件是否存在这样的链接。

单连通分量可以计算如下：

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

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

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

Answer 3

这是正确的吗？

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

---

正确的那一个：

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

1. 没有前缘
2. 同一组件中没有交叉边
3. 任意两个组件之间的交叉边不超过 1 个