Tarjan 复习小结

总算把这几个东西策清楚了。
在\(Tarjan\)算法里面，有两个时间戳非常重要，一个是\(dfn\)，意为深度优先数，即代表访问顺序；一个是\(low\)，意为通过反向边能到达的最小\(dfn\)，也就是最强反祖能力。
注意，强联通分量只存在于有向图中，割点，桥，点双，边双是无向图的概念。

一、割点。

[x] 模板题
割点：一个结点称为割点，当且仅当去掉该节点和其相关的边之后的子图不连通。
针对无向图。
首先我们考虑一个连通图（非连通图可以分别考虑连通块），我们从任意一个起点开始进行深度优先搜索，可以得到一棵树，并且这棵树中所有结点的子树之间不存在边，即没有跨越两棵子树的边
考虑一下，如果存在，那么与深度优先搜索树的定义互相矛盾。
于是有如下定理：

在无向连通图\(G\)中，

1、根结点\(u\)为割顶当且仅当它有两个或者多个子结点；

2、非根结点\(u\)为割顶当且仅当u存在结点v，使得\(v\)与其所有后代都没有反向边可以连回\(u\)的祖先。可以简单写成\(dfn_u\leq low_v\)
贴个代码

void Tarjan(R i,R rt){

	R sum=0;dfn[i]=low[i]=(++cnt);

	for(R k=hd[i];k;k=nt[k]){

		if(!dfn[to[k]]){

			Tarjan(to[k],rt),low[i]=min(low[i],low[to[k]]);

			if(i==rt)sum++;

			else if(low[to[k]]>=dfn[i])ans[i]=1;

		}

		else low[i]=min(low[i],dfn[to[k]]);

	}

	if(i==rt&&sum>1)ans[i]=1;

}

注意 在不联通图中，应当

for(R i=1;i<=n;++i)if(!dfn[i])Tarjan(i,i);

这样才能保证全部求到，注意根节点.

二、桥。

针对无向图。
桥的求法其实也是类似的，它的求法可以看成是割顶的一种特殊情况.
当结点\(u\)的子结点\(v\)的后代通过反向边只能连回\(v\)，那么删除这条边\((u, v)\)就可以使得图\(G\)非连通了。用\(Tarjan\)算法里面的时间戳表示这个条件，就是\(low_v>dfn_u\)。
注意更新\(low\)时是特判不能使用来的反边。
不需要单独考虑根节点的情况。
贴个代码

void Tarjan(R i,R id){

	dfn[i]=low[i]=(++cnt);

	for(R k=hd[i];k;k=nt[k]){

		if(k==(id^1))continue; 无向图中，这样的边是不能被遍历的。

		if(!dfn[to[k]]){

			Tarjan(to[k],k),low[i]=min(low[i],low[to[k]]);

			if(low[to[k]]>dfn[i])G[++tot]=k; k这条边即为桥。

		}

		else low[i]=min(low[i],dfn[to[k]]);

	}

}

三、强联通和双联通一点区别。

链接
所谓双连通与强连通，最大的差别，也是最本质的差别就是后者适用于无向图中，而前者适用于有向图。至于两者的概念是一样的，就是图中有a点、b点，从a点可到达b点，同时从b点可到达a点。

四、强联通分量。

而为了存储整个强联通分量，这里挑选的容器是栈。
每次一个新节点出现，就进，如果这个点有出度就继续往下找。
每次返回上来都看一看子节点与这个节点的\(low\)值，谁小就取谁，保证最小的子树根。
如果找到\(low==dfn\)，说明这个节点是这个分量的根节点。
最后找到分量的节点后，就将这个栈里，它们就组成一个全新的分量。
具体实现的时候，如果这条边是往下的边，就用他的\(low\)去更新现在的\(low\)
否则，如果这条边指向了栈内的点，就用他的\(dfn\)去更新现在的\(low\)
为什么要特别判断是否是栈内的点呢？因为只有栈内的点才可以到达当前点。在有向图中，如果指向的点不在栈内，他也就无法到达当前点，不可能组成强联通。
判断\(low==dfn\)是在\(for\)循环外面进行的。
贴个代码

void Tarjan(R i){

	low[i]=dfn[i]=(++cnt),vis[i]=1,Q[++tp]=i;

	R p=tp;

	for(R k=hd[i];k;k=nt[k]){

		if(!dfn[to[k]])Tarjan(to[k]),low[i]=min(low[i],low[to[k]]);

		else if(vis[to[k]])low[i]=min(low[i],dfn[to[k]]);

	}

	if(dfn[i]==low[i]){

		tot++;

		for(R j=p;j<=top;++j)vis[Q[j]]=0,bel[Q[j]]=tot;

		tp=p-1;

	}

}

五、边双。

其实就是一个求桥的过程。
一个桥把联通块分成了两个部分，这两个部分是独立的两个边双。
贴个代码

void Tarjan(R i,R id){

	dfn[i]=low[i]=(++cnt);

	for(R k=hd[i];k;k=nt[k]){

		if(k==(id^1))continue;

		if(!dfn[to[k]]){

			Tarjan(to[k],k),low[i]=min(low[i],low[to[k]]);

			if(low[to[k]]>dfn[i])vis[k]=vis[k^1]=1; 标记

		}

		else low[i]=min(low[i],dfn[to[k]]);

	}

}

upd on 10.31

另外一种写法：
或者类似于有向图的强联通分量，区别在于：
强制不走回头路。
不需要考虑是否在栈内。

void Tarjan(R i,R op){

	low[i]=dfn[i]=(++cnt),Q[++tp]=i;R p=tp;

	for(R k=hd[i];k;k=nt[k]){

	    if(k==op^1)continue;

		if(!dfn[to[k]])Tarjan(to[k],k),low[i]=min(low[i],low[to[k]]);

		else low[i]=min(low[i],dfn[to[k]]);

	}

	if(dfn[i]==low[i]){

		tot++;

		for(R j=p;j<=top;++j)bel[Q[j]]=tot;

		tp=p-1;

	}

}

六、点双

其实就是一个求割点的过程。
一个割点把联通块分成了两个部分，这两个部分是独立的两个点双。
贴个代码

void Tarjan(R i,R rt){

	R sum=0;dfn[i]=low[i]=(++cnt);

	for(R k=hd[i];k;k=nt[k]){

		if(!dfn[to[k]]){

			Tarjan(to[k],rt),low[i]=min(low[i],low[to[k]]);

			if(i==rt)sum++;

			else if(low[to[k]]>=dfn[i])ans[i]=1;

		}

		else low[i]=min(low[i],dfn[to[k]]);

	}

	if(i==rt&&sum>1)ans[i]=1;

}

和割点的代码是一样的，只是最后\(Dfs\)找到所有点双，注意，一个割点会存在于多个点双内。

七、小清新水题。

[x] 割点模板题
[x] 桥模板题
[x] 有向图强联通分量模板
[x] 无向图边双模板
其他题目在yl题单了。

巴特西

Tarjan 复习小结

一、割点。

二、桥。

三、强联通和双联通一点区别。

四、强联通分量。

五、边双。

upd on 10.31

六、点双

七、小清新水题。

最新文章

热门文章