首页 > 其他分享 >Tarjan

Tarjan

时间:2024-01-26 19:22:36浏览次数:29  
标签:Tarjan dfs int tot dfn low 节点

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

相关文章

  • Tarjan 算法(超详细!!)
    Tarjan算法前言说来惭愧,这个模板仅是绿的算法至今我才学会。我还记得去年CSP2023坐大巴路上拿着书背Tarjan的模板。虽然那年没有考连通分量类似的题目。现在做题遇到了Tarjan,那么,重学,开写!另,要想学好此算法的第一件事——膜拜Tarjan爷爷。Tarjan算法到底是什么其......
  • Tarjan的学习笔记
    \(Tarjan\)的学习笔记一,\(tarjan\)概述:(1)定义:$~~~~~~~~$$tarjan$是基于深度优先搜索的一种算法,求解图的连通性等问题,巧妙地利用了对图进行深搜时产生的搜索树上的边。(2)\(tarjan\)中的几种边:\(~~~~~~~~\)树边:父亲与孩子的边。\(~~~~~~~~\)前向边:祖先到孩子的边(树边属于特......
  • hszxoj 矿场搭建 [tarjan]
    hszxoj矿场搭建题目描述原题来自:HNOI2012煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见,希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口,使得无论哪一个挖煤点坍塌之后,其他挖煤点的工人都有一条道......
  • tarjan无向图割点板子
    //无向图割点模板#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'#defineN20001usingnamespacestd;template<typenameTp>inlinevoidread(Tp&x){x=0;registerboolf=1;registercharc=getchar();for(;c&......
  • 【POJ 1144】Network 题解(Tarjan算法求无向图的割点)
    一家电话线公司(TLC)正在建立一个新的电话电缆网络。它们连接由1到N的整数编号的几个位置。没有两个地方的数字相同。这些线路是双向的,总是连接在两个地方,在每一个地方,线路都以电话交换机结束。每个地方都有一个电话交换机。从每个地方可以通过其他地方的线路到达,但不需要直接连接,可......
  • 无向图tarjan
    ·区别于有向图(他的儿子是可能等于他的爸爸的)所以需要这么打tarjan(1,0);voidtarjan(intx,intfa){dfn[x]=low[x]=++tot;q.push(x),ins[x]=1;for(inty:e[x])if(y==fa)continue;//他的儿子是可能等于他的爸爸的elseif(!dfn[y])......
  • hszxoj ATM [tarjan]
    hszxojATM题目描述:$Siruseri$城中的道路都是单向的。不同的道路由路口连接。按照法律的规定,在每个路口都设立了一个$Siruseri$银行的$ATM$取款机。令人奇怪的是,$Siruseri$的酒吧也都设在路口,虽然并不是每个路口都设有酒吧。$Banditji$计划实施$Siruseri$有史以来最......
  • Tarjan 学习笔记
    萌新刚学Tarjan,啥也不会,肯定一堆错,请大佬指正谢谢前置强连通强连通:在不是强连通图的有向图\(G\)内,其顶点\(u\),\(v\)两个方向上都存在有向路径,则\(u\)和\(v\)强连通强连通图:对于有向图\(G\),若\(G\)中任意两个结点连通,则称有向图\(G\)强连通。强连通分量:有向图的极......
  • 离线快速LCA(最近公共祖先) Tarjan算法
    离线快速LCA(最近公共祖先)Tarjan算法前言对于OIer来说,LCA一直是处理树上问题的好帮手,无论是倍增还是树剖都有着优秀的\(\logn\)的复杂度。不过由于我们(数据规模)的上进,需要更快速求LCA,于是就有了……反正之前打死我都不相信这玩意能离线,还能O(1)算法思路首先来一棵树:......
  • tarjan、缩点、删点、删边
    D.CyclicOperations好久没有用tarjan了,今天做一道题,顺便复习一下tarjan是用来求连通性的算法,时间复杂度O(n)。网上关于tarjan的博文很多,我这里就不写了,只是复习一下。这道题很容易想到建边i-a[i]:对于长度是k的环,很显然可以满足;对于长度不是k的环,无论如何都不能......