求割点需要用到tarjan算法,但却与缩点有所不同。

 

缩点,前提是有向图(无向图里到处是环,整张图都是强联通)。

右图中,可以清晰地看到,2,3,4点可以相互到达,故其为整张图的强联通分量。缩点的目的,便是将2.3.4三个可以相互到达的点,缩成一个5号点,该点承载了2.3.4点所有连边、信息(如点权和、最大值)。

缩点完成后,变成下图。

简单求解思想:从任意一点出发进行深搜,能回来的就是环。可是当有如下情况时就有了问题:大环小环套在一起。贪心的想法就会出错。于是我们就要借助Tarjan算法求解。

思想:记录(学名维护)dfn[]、low[]两个数组,并用栈来维护各点的先后顺序。

dfn[]数组记录时间戳,意为记下在深搜过程中,该点(习惯性地,称呼当前点为u,连边另一点为v)u,为第++tim(即为时间戳)个进行搜索的点。如图,dfn[1]=1,dfn[2]=2,dfn[3]=3……

而对于low[]数组就显得有些麻烦,大体是指u点通过返祖边(顾名思义,就是通往已经搜索过的点的一条边,其标志为dfn[v]!=0)能到达的,时间戳最小的点。这里可以思考一下,对于刚才相依为命的两个环,4点通向2点构成了2.3.4的小环,而4点通向1点构成图中的大环。dfn[1]=1>dfn[2]=2;所以low[4]=1。

其次,对于st[]数组,作用是模拟栈。tarjan算法通过深搜实现,故递归结束的条件是没有其他出边,这时程序返回当前u点,并结束对边的遍历。这对环的确定有重要作用。对于一条返祖边(设其连向v点),作用仅限于更新low[u];由于其已有时间戳,不会在深搜下去。当程序回到v点一层时,就可以确定这个环。

详见代码。

void tarjan(int u,int f) {
	dfn[u]=low[u]=++tim;
	st[++top]=u;
	in[u]=true;
	for(int i=head[u]; i; i=e[i].net) {
		if(v==f) continue;
		int v=e[i].to;
		if(!dfn[v]) {
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
		} else if(in[v]) low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==dfn[v]) {
		++col;
		while(st[top]!=u) {
			in[st[top]]=false;
			co[st[top--]=col;
		}
		co[u]==col;
		top--;
	}
}

没什么可以多解释,详见CSDN。有一句经典的话,我一并写出来。孤点也是强联通。判断强联通的标志,是dfn[u]==low[u]。可以看到,low[u]记录着u点通过前向的链能到达的时间戳最小的点。low[u]==dfn[u],意味着u点不能到达更早的点,于是u点以及栈中在u点以上的点都构成了一个环。

0 0 votes
文章评分
订阅这个评论
提醒

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据

0 评论
Inline Feedbacks
View all comments