我要求设计一个算法来确定在有向图中是否存在任何不可到达的顶点对。算法必须在o（v+e）时间内运行
意思是：顶点i不能到达顶点j，顶点j不能到达顶点i。
我已经读过寻找强连接组件的方法，我想知道我是否可以从那里开始设计一个在当前情况下可用的算法？
最佳答案
如果你能在要求的线性o（v+e）时间内找到所有强连接的组件，那么你就完成了。这看起来有点过头了，但它解决了问题。要查找所有强连接的组件，假设图被表示为邻接列表，最简单的O（V+E）线性时间算法可能是Kosaraju的，请参见http://en.wikipedia.org/wiki/Kosaraju%27s_algorithm
找到所有强连接组件后，测试是否有一对未通过任何路径连接的强连接组件是相当简单的通过考虑节点是强连通分量的凝聚图，并且如果在从两个连通分量中选择的任意两个节点之间存在边缘，则存在边缘。
关于algorithm - 在有向图中互不可达的一对顶点，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/27494929/