以下先证明Tarjan 算法的某些特性。
引理1：对于有向图G，Tarjan 算法的DFS过程中不含有横向边和前向边，v和v的子结点x，如果有low[x]<dfn[v]，则以x为根结点的子树必定有一条后向边指向v的祖先结点。
证明：由于DFS过程仅存在后向边，运用反证法，假设以x为根结点的子树不存在这样的后向边，根据Tarjan算法过程有low[x]=dfn[x]，而low[x]<dfn[v]<dfn[x]，矛盾，故必定存在这样的后向边。
引理2：图G的DFS树中不含有前向边或横向边，u是v的祖先结点，则从u到v的任何路径均会经过u到v的DFS树上的所有点
这个引理相当直观，可以对DFS树上u到v的树边数目用数学归纳法严格证明
引理3：图G的DFS树中不含有前向边或横向边，如果点u到v有两条完全不同的简单路径(路径上的点各不相同)，则v必定为u的祖先结点
证明：DFS图中只有树边和后向边，抓住这个重点。u和v只有三种关系
(1) u是v的祖先结点
(2) v是u的祖先结点
(3) u、v没有祖先、子孙关系
只要证明(1)、(3)这两种情况均会出现矛盾即可。
情况(1)：根据引理2，u到v的任何路径都要经过DFS树中u到v的所有点，不可能有两条完全不同的路径，矛盾。
情况(3): 假设u、v的LCA为x，由于没有横向边和前向边，则从u到v的任何路径都必须经过x，不可能有两条完全不同的路径，矛盾。
引理4：图G中，从u到v有两条路径，则一定存在两点x，y，从x到y有两条完全不同的路径，即这两个路径上除了起点x、终点y之外，完全不相同
这个引理看起来也是很显然的，这里使用构造证明法，假设u到v的一条路径为P1：u, t1, ..., tn=v，另一条路径为P2：u,s1,...,sm=v，从t1到tn这n个点中找一个点ti，使ti属于路径P2，而且i最小，这个ti点肯定存在，因为点tn就属于P2，只需要找i最小的点
(1) 如果i=n则表示这两条路径完全不同
(2) 如果i>1，则u到ti有两条完全不同的路径
(3) 如果i=1且t1!=s1，则u到t1有两条完全不同的路径
(4) 如果i=1，且t1=s1，则令u=t1继续迭代这个过程，由于图G的有限性这个过程一定会终止，又由于这是两条不同的路径，故一定会出现(1) (2) (3)的情况。
定理：图G是强连通图且DFS不含有前向边或横向边，G不是单连通图当且仅当DFS树满足以下任意一个条件：
(1) 存在点v至少有两条后向边
(2) 存在点v只有一条后向边，且v的某个子结点x，low[x] <dfn[v]
(3) 存在点v，v至少有两个子结点x,y，low[x]<dfn[v]，low[y]<dfn[v]
证明：充分性很显然，如果满足任意一个条件，根据引理1，则v到p(v)至少有两条路径，则知G不是单连通图。
必要性比较复杂，假设G不是单连通图，则存在点u、v，从u到v至少有两条路径，又根据引理4，可假设这两条路径完全不相同。又根据引理3则知v必定为u的祖先结点，又DFS只有树边和后向边，则以u为根结点的子树必定有后向边到达u的祖先结点，否则从u无法到达v；因为有两条路径，则也必须有两条这样的后向边。
这两条后向边详细划分就分三种情况，
(1) u有两条后向边
(2) u只有一条后向边，另一条后向边在从u为根结点的子树中，且指向u的祖先结点；
(3) u没有后向边，从u为根结点的子树中，有两条后向边指向u的祖先结点
此定理可以扩展到含有多个强连通分支的有向图，根据此定理，只要DFS过程不出现任意一个条件，则确保任意一个强连通分支内部是单连通图，然后再考察其分支图即可。
单连通图O(V*V)算法步骤
(1) 从任意结点开始进行一次DFS，检查单个强连通分支是否为单连通图。即DFS树没有前向边、DFS树内横向边，而且不存在定理3种条件的任意一种。如此确保任意一个强连通分支为单连通图，O(V+E)
(2) 获取分支图GSCC，如果某两个点之间有多条边，则不是单连通图，O(V+E)
(3) 在分支图GSCC基础上，对每一个点进行DFS，由于GSCC基为有向无环图，故其边数必定小于V，则复杂度为O(V*V)
总体复杂度为O(V*V).