Tarjan算法之点强连通分量

定义

若一个无向连通图不存在割点,则称它为“点双连通图”。无向连通图的极大点双连通子图被称为“点双连通分量”,简记为“v-DCC”。

类型

  1. 单独的孤立点是一个点双连通分量。
  2. “杠铃”(两点一边,也可有重边)是一个点双连通分量。
  3. 图中任何两点都至少包含在一个简单环中(即没有割点)

求法

去掉所有割点剩下的就是v-DCC
以上为误解。应当在tarjan判断割点的条件(不管是不是根)dfn[x] <= low[y]达成后,把y及以上节点弹出,并把x也算入y所在的v-DCC中。所以一个割点可能属于多个v-DCC。
也常与缩点搭配:把每个割点与v-DCC当做一个

待更.....

原文地址:https://www.cnblogs.com/Thomastine/p/11792215.html