在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值吗?