Tarjan总结

懒惰的大鸽子$HellPix$来更博了。

$tarjan$三种运用:

  • 有向图的强连通分量:$dfn[x]=low[x]$,把栈中元素弹出,直到弹出$x$。缩点双成为一个$DAG$,应用:缩点$dp$
  • 无向图的点双联通分量:$low[v]>=dfn[u]$,把栈中元素弹出,直到弹出$v$(此时,$u$也属于这个点双,但是因为$u$也有可能属于别的点双,所以要把$u$保留在栈中)
  • 无向图的边双联通分量:$low[v]>dfn[u]$,则$(u,v)$为割边,$dfn[x]=low[x]$时弹出(私以为,无向图边双就是相当于有向图的强分),缩边双成为一棵树。
上一篇:Tarjan-割点


下一篇:Blockade(tarjan求割点...)-poi2008