Tarjan
前置知识
搜索树 & 搜索森林
\(在一张连通图中,所有的节点以及发生递归的边共同构成一棵搜索树。如果这张图不连通,则构成搜索森林。\)
\(\color{green}树边:\) \(dfs经过的边,dfs搜索树の边\)
\(\color{yellow}返祖边:\) \(可以理解为返回去の边\)
\(\color{red}横叉边:\) \(dfs中指到已被动过的边,但是这个节点并不是当前节点的祖先时形成的\)
\(\color{blue}前向边:\) \(指向子树中节点的边,父节点指向子孙节点(but...没啥用)\)
low && dfn
\(dfn(时间戳(in))\) : \(在搜索树中被访问の顺序(dfs序in序)\)
\(low(回溯值)\) : \(返回到の祖宗(从当前节点作为搜索树的根节点出发,能够访问到的所有节点中,时间戳最小的值)\)
对 low && dfn の 修改
\(tot记录进入\)
$初始:low_x = dfn_x = tot $
\(继续dfs后计算low_x:\)
{
if( x -> y 是树 可以理解为返回去の边边(have not be changed ) )
low[ x ] = min( low[ x ] , dfn[ y ] ) ;
else if( x -> y 是返祖边 )(访问过&&在栈中)
low[ x ] = min( low[ x ] , dfn[ y ] ) ;
else ( x -> y 是横叉边 )(不在栈中了)
do nothing
}
code
int tot , dfn[ N ] , low[ N ] ;
stack < int > s ;
bool ins[ N ] ;
int ans , id[ N ] ;
void Tarjan( int x ) // T 大写 据sb.所说不写会CE
{
tot ++ ;
s.push( x ) ;
int k = -114514 ;
low[ x ] = dfn[ x ] = tot ;
ins[ x ] = true ;
for ( int i = head[ x ] ; i ; i = e[ i ].next )
{
int y = e[ i ].to ;
if ( !dfn[ y ] )
{
Tarjan( y ) ;
low[ x ] = min( low[ x ] , low[ y ] ) ;
}
else if ( ins[ y ] == true )
{
low[ x ] = min( low[ x ] , dfn[ y ] ) ;
}
}
if ( low[ x ] == dfn[ x ] )
{
ans ++ ;
while ( k != x )
{
k = s.top( ) ;
s.pop( ) ;
id[ k ] = ans ;
}
}
}
标签:Tarjan,dfs,int,tot,dfn,low,节点
From: https://www.cnblogs.com/hangry/p/17990532