关于tarjan算法求割点
  • 板块学术版
  • 楼主bu_nai_lii
  • 当前回复5
  • 已保存回复5
  • 发布时间2021/11/15 16:57
  • 上次更新2023/11/4 00:29:22
查看原帖
关于tarjan算法求割点
395264
bu_nai_lii楼主2021/11/15 16:57

在dfs时对于边(x,y)有两种情况

1.若x是y的父亲,则low[x]=min( low[x] , low[y]).

2.若x不是y的父亲则low[x]=min(low[x],dfn[y]).

转化到代码上如下:

void tarjan ( int fa , int now ) {
	dfn[now] = low[now] = ++ cnt ;
	int sum = 0 ;
	for ( int i = h[now] ; i ; i = ne[i] ) {
		int j = e[i] ;
		if ( ! dfn[j] ) {
			tarjan ( now , j ) ;
			low[now] = min ( low[now] , low[j] ) ;
			if ( low[j] >= dfn[now] && now != fa ) 
				cut[now] = true ;
			if ( now == fa )
				++ sum ;
		}
		else 
			low[now] = min ( low[now] , dfn[j] ) ;
	}
	if ( sum >= 2 ) 
		cut[now] = true ; 
}

想请问一下为什么在第二种情况下low[x]不能直接等于min(low[x].low[y])呢?

反正low[x]不就表示在不经过x的父节点的情况下能回溯到的最小的dfn值吗?

2021/11/15 16:57
加载中...