平凡的O(V^3)解决办法是使用弗洛伊德warshal所有到所有的最短路径，但是这是一个矫枉过正（以时间复杂度）。

可以在中完成O(V+E)。

要求：

DAG按拓扑结构半连接，每个i都有一个边缘(vi,vi+1)

证明：

给定具有拓扑排序的DAG v1,v2,...,vn：

如果(vi,vi+1)某边没有边i，则也就没有路径(vi+1,vi)（因为它是DAG的一种拓扑结构），并且该图不是半连接的。

如果每个i都有一条边(vi,vi+1)，则每个i,j（i
<j）都有一条路径vi->vi+1->...->vj-1->vj，并且该图是半连接的。

由此我们可以得到算法：

1. 在图中找到最大SCC
2. 建立SCC图G’=（U，E’），使之U成为一组SCC。E'= {(V1,V2) | there is v1 in V1 and v2 in V2 such that (v1,v2) is in E)
3. 对G’进行拓扑排序
4. 检查每个i是否有边Vi，Vi + 1。

正确性证明：

如果该图是半连接的，那么对于一对(v1,v2)，则存在一条路径v1->...->v2-假设V1，V2为它们的SCC。由于V1和V2中的所有节点均已牢固连接，因此存在从V1到V2的路径，因此也有从v1到v2的路径。

如果算法得出的结果为true，则对于任何两个给定的节点v1，v2-我们知道它们在SCC
V1和V2中。从V1到V2有一条路径（不失一般性），因此也有从v1到v2的路径。

---

附带说明一下，每个半连接图也有一个根（r通向所有顶点的顶点）：

证明：
假设没有根。定义#(v) = |{u | there is a path from v to u}|（具有v到它们的路径的节点数）。
选择a这样#(a) = max{#(v) | for all v}。
a不是根，因此有些节点u没有a到它的路径。由于图形是半连接的，因此意味着存在一条路径u->...->a。但这意味着#(u) >= #(a) + 1（所有节点均可从a和访问u）。
与的最大值矛盾#(a)，因此有一个根。