前置知识
啊嘿嘿，第三次学习 tarjan 终于是给我学明白了。
先来看一下 dfs 树上的三种边：
- 树边：从父亲连向儿子的边
- 返祖边：从儿子连向祖先的边
- 横叉边：除了前两种边之外的边
tarjan 算法中常用的两个数组：
- \(dfn_i\)：表示 \(i\) 的时间戳，即第几个被遍历到
- \(low_i\)：表示 \(i\) 只经过最多一条返祖边到达的最小时间戳
下面正片开始！
有向图的 tarjan 算法
求强连通分量
这个好像是 tarjan 算法在有向图中的唯一常见应用吧~
强连通定义
对于有向图中的一个联通子图 \(G(V,E)\)，若子图中的任意两点之间都是可以到达的，则称 \(G(V,E)\) 是一个强连通分量
实现
对着代码理解吧~
初始化：dfn[u] = low[u] = ++tim 显然一个点不经过任何边可以到达的最小时间戳是他自己
if(!dfn[v]){ tarjan(v);low[u] = min(low[u], low[v]);
}
else if(in[v]) low[u] = min(low[u], dfn[v]);
如果当前点的时间戳没有被算过就说明是树边，否则就是非树边。
对于一条非树边只能用 \(v\) 的 \(dfn\) 去更新当前的 $low#，否则可以用 \(low\) 来更新当前点的 \(low#\)。
注意，有向图中的 dfs 树可能会出现横叉边的情况，而横叉边是不可以用来更新 \(low\) 的，所以要特判（用是否在栈内，即是否属于当前子树来判断）。