单连通图是一个有向图,从 u 到 v ∀ u,v至多有 1 条路径。
我想到了以下解决方案:
- 从任何顶点运行 DFS。
- 现在再次运行 DFS,但这次从顶点开始,按完成时间递减的顺序。仅对以前的某些 DFS 中未访问的顶点运行此 DFS。如果我们在同一个组件中找到交叉边或前边,则它不是单连接的。
- 如果所有顶点都完成并且没有这样的前边交叉,则单连接。
O(V+E)
这是正确的吗?或者有没有更好的解决方案。
更新:最多 1 个简单路径。
单连通图是一个有向图,从 u 到 v ∀ u,v至多有 1 条路径。
我想到了以下解决方案:
O(V+E)
这是正确的吗?或者有没有更好的解决方案。
更新:最多 1 个简单路径。
如果满足以下两个条件之一,则图不是单连通图:
在同一个组件中,当您执行 DFS 时,您会得到一条从一个顶点到另一个已经完成搜索的顶点的道路(当它被标记为黑色时)
当一个节点从另一个组件指向 >=2 个顶点时,如果 2 个顶点有连接,则它不是单连接的。但这需要你保留一个深度优先的森林。
单连通分量是属于同一实体的任何有向图。它可能不一定是 DAG,可以包含循环的混合。
每个节点至少有一些链接(传入或传出),同一组件中的每个节点至少有一个节点。我们需要做的就是检查同一个组件是否存在这样的链接。
单连通分量可以计算如下:
在所有节点上运行迭代。如果所有节点都有相同的公共领导者,则图的无向版本是单连接的。
否则,它包含由其相应领导者表示的多个单连接子图。