Tarjan 算法小结

简介

Tarjan (音: 塔扬) 是个神犇,他发明了图论中的著名算法 tarjan 算法

可以轻松方便地解决 \(2\) 种图的连通性问题——割点/边(Cut)与强连通分量(SCC)

割点/边用来解决一些针对性的图的连通问题,强连通分量则广泛运用于化图为 \(DAG\) (缩点) 、\(2-SAT\) 问题。

(注:不严谨地注明一下,割点/边用于无向图,缩点用于有向图(缩点不能求无向图最大团喔))


总思想:

定义

tarjan 算法的精髓在于 \(2\) 个数组:dfnlow

dfn 是该节点的 dfs序 编号 ,俗称时间戳,指它被遍历到的时刻。

low 比较魔性,表示从该节点出发,通过非父子关系的边能回到的最早的节点。

(感谢图论神器)例如下面这张图:

Tarjan 算法小结

(数据不唯一,下面以遍历顺序:\(1,2,4,5,3\) 为例,数组下标由 \(1\) 开始编号):


\[\Large{dfn=\{1,2,5,3,4\}} \]

\[\Large{low=\{1,2,2,2,2\}} \]

(例如 \(4\) 节点可以通过 \(4,5,2\) 回到时间戳为 \(2\) 的 \(2\) 节点,所以low[4]=2

有了这 \(2\) 个数组的定义我们就可以进行奇怪的操作,不过还是先看看它们怎么求。

思路实现

dfn 很容易求,记下遍历时间即可知道。

low 实际上是利用回溯能够快速算出的一个量,主要步骤如下:

  1. low 的初始值为 dfn (指向自己)

  2. 当前节点有一条非通向其父亲的路径指向其某一个祖先,则更新 low 值。

  3. 如果它的儿子能够通向更早的节点,将 low 值更新为它儿子的 low 值。

割点/割边 (Cut)

定义

  • 割点:如果去掉某个点以及与这个点相连的所有边,整个图被分为多个不为空的连通块,则这个点是割点。

  • 割边:如果去掉某条单独的边,整个图被分为多个不为空的连通块,则这条边是割边。

求法

设想一棵 dfs 树,考虑如果某一结点 \(u\) 的儿子能够回到这一结点的祖先节点,说明即使删掉 \(u\) 也不能阻挡 \(u\) 的儿子与它祖先的连通。

那么,如果结点 \(u\) 的儿子不能回到这一节点的祖先,那么很明显,没有 \(u\) 则它的儿子就回不去了 QAQ 。

那么很明显,求取的方法是 ( \(v\) 节点是 \(u\) 节点的儿子 ): IF(low[v]>=dfn[u])u为割点,边 (u,v) 为割边;

同时,根节点需要特判,若它有 \(>1\) 个儿子它才是割点(可能会是删了根节点以后出现 \(1\) 个连通块和 \(1\) 个空的点集)

void tarjan(int u)
{
	q[u].low=q[u].dfn=++dep;for(int i=a.head[u];i;i=a.nxt[i])
	{
		int v=a.des[i];if(!q[v].dfn)
		{
			tarjan(v);q[u].low=min(q[u].low,q[v].low);
			if(q[u].dfn<=q[v].low&&u!=Rt)q[u].isc=1;ch+=(u==Rt);
		}
		q[u].low=min(q[u].low,q[v].dfn);
	}
}
int main(){input();for(int i=1;i<=n;++i){if(!q[i].dfn){dep=0;dfs(i);if(ch>1)q[i].isc=1;}}}

缩点 ——求强连通分量(SCC)

待补充

上一篇:BZOJ2208: [Jsoi2010]连通数(tarjan bitset floyd)


下一篇:信息算法牛杂面