首页 > 其他分享 >无向图tarjan

无向图tarjan

时间:2023-11-29 21:46:02浏览次数:51  
标签:tarjan int 无向 ins dfn low cnt

· 区别于有向图(他的儿子是可能等于他的爸爸的)所以需要这么打

tarjan(1,0);
void tarjan(int x,int fa)
{
    dfn[x]=low[x]=++tot;
    q.push(x),ins[x]=1;
    for(int y:e[x])
        if(y==fa) continue;//他的儿子是可能等于他的爸爸的
        else if(!dfn[y])
            tarjan(y,x),low[x]=min(low[x],low[y]);
        else if(ins[y])
            low[x]=min(low[x],dfn[y]);
    if(dfn[x]==low[x])
    {
        int y;++cnt;
        while(y!=x)
            y=q.top(),
            q.pop(),
            ins[y]=0,
            color[y]=cnt;
    }
}

标签:tarjan,int,无向,ins,dfn,low,cnt
From: https://www.cnblogs.com/Charlieljk/p/17865959.html

相关文章

  • hszxoj ATM [tarjan]
    hszxojATM题目描述:$Siruseri$城中的道路都是单向的。不同的道路由路口连接。按照法律的规定,在每个路口都设立了一个$Siruseri$银行的$ATM$取款机。令人奇怪的是,$Siruseri$的酒吧也都设在路口,虽然并不是每个路口都设有酒吧。$Banditji$计划实施$Siruseri$有史以来最......
  • 【图论】无向图数圈圈
    本篇主要讨论圈数较小(\(k\leq5\))的时候无向图上数圈的方法。1.k\(\leq\)4这部分可以做到\(n,m\leq10^5\)(点数和边数)。\(k=2\):???不用说。\(k=3\):我们考虑有方向性的数环避免重复,给每个点定义其属性为\((deg_i,i)\),\(deg\)即无向图度数,比较属性时首先比较第一项......
  • Tarjan 学习笔记
    萌新刚学Tarjan,啥也不会,肯定一堆错,请大佬指正谢谢前置强连通强连通:在不是强连通图的有向图\(G\)内,其顶点\(u\),\(v\)两个方向上都存在有向路径,则\(u\)和\(v\)强连通强连通图:对于有向图\(G\),若\(G\)中任意两个结点连通,则称有向图\(G\)强连通。强连通分量:有向图的极......
  • B3610 [图论与代数结构 801] 无向图的块 题解
    题目传送门前言本题解内容均摘自我的Tarjan学习笔记。解法Tarjan与无向图无向图与割点(割顶)在一个无向图中,不存在横叉边(因为边是双向的)。一个无向图中,可能不止存在一个割点。割点(割顶):在一个无向图中,若删除节点\(x\)以及所有与\(x\)相关联的边之后,图将会被分......
  • 离线快速LCA(最近公共祖先) Tarjan算法
    离线快速LCA(最近公共祖先)Tarjan算法前言对于OIer来说,LCA一直是处理树上问题的好帮手,无论是倍增还是树剖都有着优秀的\(\logn\)的复杂度。不过由于我们(数据规模)的上进,需要更快速求LCA,于是就有了……反正之前打死我都不相信这玩意能离线,还能O(1)算法思路首先来一棵树:......
  • 【算法题】统计无向图中无法互相到达点对数
    题目:给你一个整数n,表示一张无向图中有n个节点,编号为0到n-1。同时给你一个二维整数数组edges,其中edges[i]=[ai,bi]表示节点ai和bi之间有一条无向边。请你返回无法互相到达的不同点对数目。示例1:输入:n=3,edges=[[0,1],[0,2],[1,2]]输出:0解释:所......
  • tarjan、缩点、删点、删边
    D.CyclicOperations好久没有用tarjan了,今天做一道题,顺便复习一下tarjan是用来求连通性的算法,时间复杂度O(n)。网上关于tarjan的博文很多,我这里就不写了,只是复习一下。这道题很容易想到建边i-a[i]:对于长度是k的环,很显然可以满足;对于长度不是k的环,无论如何都不能......
  • 2023-10-04:用go语言,现有一棵无向、无根的树,树中有 n 个节点,按从 0 到 n - 1 编号 给你
    2023-10-04:用go语言,现有一棵无向、无根的树,树中有n个节点,按从0到n-1编号给你一个整数n和一个长度为n-1的二维整数数组edges,其中edges[i]=[ai,bi]表示树中节点ai和bi之间存在一条边。每个节点都关联一个价格。给你一个整数数组price,其中price[i]是第i......
  • TARJAN复习 求强连通分量、割点、桥
    TARJAN复习求强连通分量、割点、桥目录TARJAN复习求强连通分量、割点、桥强连通分量缩点桥割点感觉之前写的不好,再水一篇博客强连通分量“有向图强连通分量:在有向图G中,如果两个顶点vi,vj间(vi>vj)有一条从vi到vj的有向路径,同时还有一条从vj到vi的有向路径,则称两个顶点强连通(......
  • 连通性与 Tarjan
    强连通分量和Tarjan强连通分量(StronglyConnectedComponents,SCC),指的是极大的连通子图。tarjan算法,用于求图的强连通分量。dfs生成树有向图的dfs生成树大致分为四种边:树边(treeedge):示意图中以黑色边表示,每次搜索找到一个还没有访问过的结点的时候就形成了一条树边......