tarjan学习笔记

在 Tarjan 算法中为每个结点u维护了以下几个变量：
dfn[u]:深度优先搜索遍历时结点u被搜索的次序。
low[u]:设以u为根的子树为Subtree(u)。 low[u]定义为以下结点的dfn的最小值： 
Subtree(u)中的结点；
从Subtree(u)通过一条不在搜索树上的边能到达的结点。

如何计算low？
首先让low[x]=dfn[x]（根据定义，最大也不过是dfn[x]）
若在搜索树上x是y的父节点，则low[x]=min(low[x],low[y]) 递归求解
若无向边(x,y)不是搜索树上的边，则low[x]=min(low[x],dfn[y])

性质：
一个结点的子树内结点的 dfn 都大于该结点的 dfn。
从根开始的一条路径上的 dfn 严格递增，low 严格非降。

感性理解:low[x]就是从以x为根的搜索树子树内能到达的最小dfn