algorithm - 连通图与强连接有向图

Closed. This question needs to be more focused. It is not currently accepting answers. Learn more。
想改进这个问题吗？更新问题，使其只关注一个问题editing this post。
给出一个图表：
输入：

0 -> 1
2 -> 1
3 -> 1

代表：

0 -> 1 <- 2
     ^
     |
     3

这个图不是强连接的，因为不是每个顶点都可以到达顶点，反之亦然（路径u到v和v到u）
我目前用于检查有向图是否强连通的算法是从每个顶点O（n3）应用DFS，如果我能从N个顶点中找到N-1个顶点，则有向图是强连通的。
另一种算法是tarjan的算法gm。
但是这个图被认为是连通的吗（不是强连通的）？
如果是的话，有什么好的算法可以应用。
谢谢你

最佳答案

如果你想知道你的有向图是强连通的，有几种算法，在wiki中你可以找到这三种：
Kosaraju's algorithm
Tarjan's algorithm
Path-based strong component algorithm
如果你想检查你的有向图是否只是连通的，你可以简单地假设它是一个图而不是一个有向图，然后用O(|V|+|E|)应用connected component算法如果它只有一个连接的组件，那么你的图是连接的。