tarjan备忘录

有向图

1. SCC 强连通分量
   • 记录方式：用栈记录
   • 处理位置：dfs 尾部
   • 处理条件：low[u]==dfn[u] 这是一个 SCC。
   • 处理方式：把栈到 $u$ 的部分全部取出来变成一个 SCC。
   • 多次贡献：否
   • 处理逻辑：$u$ 这个点及其 dfs 子树节点若都不能去到更早的地方，那么这个子树最多连通到 $u$，子树内这且不属于是其他 SCC 的点成为 $u$ 这个 SCC，那么用栈记录剩下的点。并且栈中点一定能构成 SCC 若不行则会在其他点统计到。

无向图

1. VDCC 点双连通分量

   • 记录方式：用栈记录
   • 处理位置：遍历出边的时候
   • 处理条件：low[v]>=dfn[u] 这是一个 VDCC。若 $u$ 不是无向图根节点，那么出现一次 low[v]>=dfn[u] $u$ 就是一个割点；否则要出现两次 $u$ 才能是一个割点。
   • 处理方式：把栈到 $v$ 的部分全部取出来加上 $u$ 变成一个 SCC。
   • 多次贡献：是
   • 处理逻辑：若这个 $v$ 点最多返回到 $u$，那么去掉 $u$ 这一坨就会散开，变得不连通，并且一定会散开，因为不散开肯定其他地方有链接，但是无向图 dfs 不允许这样的事情发生，除非这个时候是 dfs 树根节点，因为去掉根节点下面不会不连通，只有有两次时才会散开。

2. EDCC 边双连通分量

   • 记录方式：标记割边
   • 处理位置：遍历出边的时候
   • 处理条件：low[v]>dfn[u] 这是一个 EDCC。
   • 处理方式：tarjan 结束后 dfs 遍历图，每次遍历不经过标记的割边，每次遍历到的点形成一个 EDCC。
   • 多次贡献：否
   • 处理逻辑：若这个 $v$ 点返回不到 $u$，那么去掉 $u\rightarrow v$ 这条边，$v$ 这一坨与 $u$ 就不连通了。