Tarjan

这是一篇 Tarjan 求联通分量的笔记

自学的笔记。

了解有关于联通分量的术语

1. 割点 : 如果从图中删去点 x 及与其有关的边后有新的联通块产生，那么这个点就是割点。
2. 割边 : 如果从图中删掉边 x 后有新的联通块产生，那么这条边就是割边。
3. 边双联通分量 : 从该子图中任选一条边删除不会有新联通块产生，即没有割边。
4. 点双联通分量 : 从该子图中任选一个点及与其有关的点删除不会有新联通块产生，即没有割点。
5. 强联通分量 : 在有向图中，从任意一个点出发能到达另一个点的子图叫做强联通分量。

注意 : 3 和 4 一般与无向图有关。

了解有与本篇文章有关的术语

1. 搜索树：我们以某一个节点 x 出发进行深度优先搜索，每一个节点只访问一次，所有被访问过的节点与边构成一棵树，我们可以称之为“搜索树”。

什么是 Tarjan 求联通分量

Tarjan 是一种基于 dfs 的求联通分量的方法，能以线性时间复杂度求出联通分量，割边，割点。

Tarjan 求联通分量的原理

首先定义两个数组 dfn 和 low ，分别存第几个被搜索到，和追溯值。

追溯值的定义为当前节点的搜索树中最小的 low 值。

以后判断一个点或边的的属性只需要看 dfn 和 low 的大小关系就行了。

割边

对于无向图的一条边 (u,v)（假设在 dfs 树中 u 是 v 的父节点），
如果满足：dfn[u]<low[v]那么边 (u,v) 是割边。

本篇文章仅为笔记，可能存在谬误。