2、 很多有关有向图的算法都从分解步骤开始，这种分解可把原始的问题分成数个子问题，其中每个子子问题对应 一个强连通分支。构造强连通分支之间的联系也就把子问题的解决方法联系在一起，我们可以用一种称之为分支图的图来表示这 种构造。

3、 寻找图G=(V,E)的强连通分支的算法中使用了G 的转置，即E‘由G中的边改变方向后组成。若已知图G的邻接表，则建立GT所需时间为O(V+E)。G和G’有着完全相同的强连通支， 即在G中u和v互为可达当且仅当在GT中它们互为可达。

4、 下列运行时间为Θ(V+E)的算法可得出有向图G=(V,E)的强连通分支，该算法使用了两次深度优先搜索，一次在 图G上进行，另一次在图G‘上进行：

Strongly_Connected_Components(G)

a、 调用DFS(G)以计算出每个结点u的完成时刻f[u];

b、 计算出G’；

c、 调用DFS(GT)，但在DFS的主循环里按f[u]递减的顺序考虑各结点(和第一行中一样计算);

d、 输出第3步中产生的深度优先森林中每棵树的顶点， 作为各自独立的强连通分支。

Strongly_Connected_Component算法的思想来自于分支图GSCC = (VSCC, ESCC)的一个重要性质：

假设G的强连通分支为C1 , C2 ,..., Ck。顶点集Vscc 为{v1 , v2 ,..., vk }, 对于G的每一个强连通分支Ci ，都包含一个顶点vi。如果对于某个x ∈Ci 以及某个y ∈Cj，G中包含了一条有向边(x, y) 的话，则就有一条边(vi , vj ) ∈Escc；从另一方面看，收缩那些其关联顶点都处于G的同一强连通分支内的边，即可得到图Gscc。

5、 引理：设C和C′是有向图G = (V, E)中的两个不同的强连通分支，设u, v ∈C, u′, v′∈C′, 并假设G中存在着一条通路u→u′，那么G中就不可能同时存在通路v′→ v。

6、 引理： 设C和C’为有向图G=(V,E)中的两个不同的强连通分支。假设一条边(u,v) ∈E,其中u ∈C，v ∈C’，则f(C)>f(C’)。

推论：设C和C’为有向图G=(V,E)中两个不同强连通分支，假设存在着一条边(u, v) ∈ET, u ∈C且v ∈ C′. 那么f(C) < f(C′)。

7、 Strongly_Connected_Components(G)能正常工作的原因：

a、 第二次在GT 上执行深度优先搜索：从强连通分支C开始，f(C)是最大的，搜索从C的某个顶点x开始，访问C 所有顶点。

b、 根据推论，GT没有从C到其他连通分支的边。根为x的树仅包含C中的顶点。

c、 接下来访问C’，f(C’)是f(C)外最大的，与访问C过程类似当算法第3行对GT 进行深度优先搜索时，该分支出来的任何边都指向已被访问过的分支。

因此，每颗深度优先树都是一个强连通分支。