korasaju算法的粗浅理解

首先证明一些这句话： 逆图中能根据u搜到的点v，说明原图中v可以到达u，而原图中v一定是u树中的结点，也就是说u可到达v,从而一定能形成强连通分支。

• 证明：逆图中能根据u搜到的点v，说明原图中v可以到达u。

  这个很容易证明，因为你在逆图中u能搜到的点v，原图中肯定是v可以到达u。

• 证明：而原图中v一定是u树中的结点，也就是说u可到达v。

  因为是从ｕ开始搜到ｖ，所以ｕ的结束时间比ｖ的大。

  假设原图中ｕ不指向ｖ，又ｖ的结束时间比ｕ小说明先遍历的ｖ后遍历的ｕ，又原图中v可以到达u，故ｖ的结束时间比ｕ的小。则ｕ的结束时间应该比ｖ的小，与已知矛盾，假设不成立。故原图中ｕ能到达ｖ。

综上，也就是说u可到达v,从而形成一个强连通分支。但是能把所有的强连通分支都遍历出来吗？根据强连通性的特点，只要u,v为强连通分量，不管逆图还是原图中u和v都能互相到达。结合上面的证明两个节点的推广一下，就证明了能把包含起始节点u的极大强连通分量给遍历出来。

参考链接：http://www.cnblogs.com/rainydays/archive/2011/05/01/2033941.html

自己的一些总结

根据深搜和回溯来标示节点的开始与结束时间故可以推出以下的性质：

1. 所有比一个结点X的结束时间小的节点都是在原图中节点X能到达的节点

2. 如果逆图中X能到达某一个节点Y,说明原图中节点Y能到达X.

3. 节点X结束时间最大说明：X是一个子树的根，否则X的结束时间不是最大的，其根的时间要比它还大。

4. 其所有子树节点的值处在其开始时间和结束时间之间。

5. 所有比节点X的结束时间大的节点是节点X不能到达的，所以先处理大的结束时间就避免了转置图中所有X能到达的没被访问过的节点在原图中是X能到的。要是X不能到肯定结束时间比X的大已经被处理。