strongly connected component(SCC): 里面的任一对顶点都是互相可达的。

一个有向图，将每个SCC缩成一个点，那么这个图就变成了DAG（有向无环图）。

原图进行DFS之后，使post (u)最大的u点必然在source中.

如果C和C'是两个不同的SCC，一条边从C到C'，那么C中post值最大的值一定比C'中最大的要大。

寻找SCC的算法：

1 call DFS (G) to compute finishing times post[u] for each vertex u

2 compute GT // GT 即对G中的边取反后得到的图。取反后，SCC内部仍然是通的，但SCC之间就不再是连通的了。
3 call DFS (GT), but in the main loop of DFS, consider the vertices in order of decreasing post[u]

4 output the vertices of each tree in the depth-first forest formed in step 3 as a SCC

计算GT的时间：O(V+E)
两次DFS的时间：O(V+E)
总时间： O(V+E)

算法实现：

最新文章

  1. java.net.SocketException: Connection reset
  2. 开启gpu加速的高性能移动端相框组件！
  3. php截取字符串函数
  4. loj 1377 (bfs)
  5. SQL语言和DML相关操作以及相应的运算符
  6. 代码静态分析工具--PMD,Findbugs,CheckStyle
  7. 【转】Android中JNI的使用方法
  8. BZOJ 2820 YY的GCD（莫比乌斯函数）
  9. Using Apache Maven
  10. Application使用示例
  11. 使用 IDEA 创建 Maven Web 项目 （一）- 使用IEAD创建Maven项目
  12. unity3d 学习过程记录
  13. java利用poi生成/读取excel表格
  14. PL/SQL 记录 Record 简介
  15. Python集合set
  16. how2heap学习笔记
  17. css实现div内一段文本的两端对齐
  18. 编程实现类似Linux系统的cp功能
  19. 12.8 Daily Scrum
  20. hdu5443 ST表裸题：求区间最大

热门文章

  1. OAuthLogin2.0
  2. Spark Mllib里的向量标签概念、构成（图文详解）
  3. MySQL 实现字符串换行
  4. ASPECTJ 注解。。。
  5. Redhat/CentOS 软件安装
  6. 在2017年，如何将你的小米4刷上Windows 10 mobile？（后附大量图赏）
  7. 重温Javascript（一）-基本概念
  8. Android（java）学习笔记118：BroadcastReceiver之 外拨电话的广播接收者
  9. Java压缩字符串工具类
  10. Understanding NFS Caching