数据结构
dfn[i] :编号为i的结点在dfs遍历图的过程中的访问序号（开始时间）
low[i] :从i结点出发dfs过程中i下方的结点能到达的最早的当前搜索路径上的结点的开始时间。（初始时 low[i]=dfn[i] ）
操作
- 遍历结点没被访问过的就开始dfs，碰到哪个结点哪个结点就入栈，栈中结点只有在其所属的强连通分量已经全部求出时才会出栈。
- 连接结点u的当前搜索路径上的v， low[u]=min(low[u],dfn[v]) ，如果low[u]被更新为 dfn[v] 则表明目前u可达的最早结点时v
- 对于u的子结点v，当由它出发的dfs结束回到u时， low[u]=min(low[u],low[v]) 。
- 一个结点完成dfs后， low[u]=dfn[u] 说明u是一个强连通分量在dfs搜索树中的根。
- 将栈中结点一直弹出直到u，弹出的结点时一个强连通分量
1 void Tarjan(u) { 2 dfn[u]=low[u]= ++index //index是开始时间 3 stack.push(u) 4 for each (u, v) in E { // E是边集合 5 if (v is not visited) { 6 tarjan(v) 7 low[u] = min(low[u], low[v]) 8 } 9 else if (v in 当前搜索路径) {//当前搜索路径就是起点(根)到u的路径 10 low[u] = min(low[u], dfn[v]) 11 } 12 } 13 if (dfn[u] == low[u]) { //u是一个强连通分量的根 14 repeat 15 v = stack.pop 16 print v 17 until (u== v) 18 } //退栈，把整个强连通分量都弹出来 19 } //复杂度是O(E+V)的
一些图论定理
有向无环图中，唯一出度为0的点=可以由任何点出发均可达的点
有向无环图中所有入度不为0的点一定可以由某个入度为0的点出发可达。