Tarjan学习笔记

Tarjan算法是基于dfs，可以对图进行缩点，使得一个强联通分量的点缩成一个点

---

概述

$Tarjan$算法是基于$dfs$ ，可以对图进行缩点，使得一个强联通分量的点缩成一个点

$dfn[]: dfs$时每个节点访问的时间戳

$low[ ]$ : 定义$low[u]=min(low[u],low[v])$
( $v$ 为 $u$ 可到达的所有点，初始$low[u]=dfn[u]$ )

结论：若$low[u]==dfn[u]$，则节点 $u$ 为一个强联通分量的首领

如何知道每个点所属的强联通分量？

$belong[]:$ 每个点所属的强联通分量，即所在强联通的首领，假设缩点都共有$scc$个点，那么$1≤belong[]≤scc$

具体实现

$dfs$ 时将每个点压入 栈 $(stack)$ 中，每次遇到一个强联通分量的首领就将栈中元素弹出，直至栈顶元素为当前强联通分量的首领，则弹出的这些点即为当前强联通分量的首领所在的强联通

模板

// u[],v[] 有向边集合
// tms: dfs时间戳
// scc:缩点后点的数量
// belong数组的值是1~scc
// dfn[]: 每个点访问的时间戳
// low[]: 确定强联通的祖先
// vector<int>dag[]: 缩点后的新图