tarjan求割点割边的思考

时间:2021-08-17 12:27:11

这个文章的思路是按照这里来的。这里讨论的都是无向图。应该有向图也差不多。

1.如何求割点

首先来看求割点。割点必须满足去掉其以后,图被分割。tarjan算法考虑了两个:

  • 根节点如果有两颗及以上子树,它就是割点。因为它没有父亲了(可怜的点)。

  • 对于有父亲的普通的结点a,如果它递归树的子树中,有任意节点b的low[b]>=dfn[a],那么它就是割点,反之则不是割点。

  如果\(low[b]>=dfn[a]\),a一定是割点。因为\(low[b]>=dfn[a]\)说明有在b这个子树中,里面所有点都互相搞来搞去,但是不能搞到a上面去,所以把a切断以后,这个子树就被隔离了。所以仅仅一个子树就可以让a成为割点。反之如果所有a的孩子b,都满足\(low[b]<low[a]\),那么a就不是割点。

2.如何求桥

桥也必须满足去掉其以后,图被分割。所以对于一条边(a, b),如果\(low[b]>=dfn[a]\),那他就是桥(不证了)。

还有一个low和dfn的问题:在tarjan求割点时,如果v在栈中,必须写成low[u]=min(low[u],dfn[v])。因为u可能被传送到了非树枝边到不了的地方。但是求强连通分量可以这样,因为它是有向图,如果它的祖宗能连到它,他又能连到他的祖宗,那么它的祖宗能连到的地方,他也能连到。同理无向图求割点就不能这样。

tarjan求割点割边的思考

tarjan求割点割边的思考的更多相关文章

  1. 求割点 割边 Tarjan

    附上一般讲得不错的博客 https://blog.csdn.net/lw277232240/article/details/73251092 https://www.cnblogs.com/colle ...

  2. tarjan求割点与割边

    tarjan求割点与割边 洛谷P3388 [模板]割点(割顶) 割点 解题思路: 求割点和割点数量模版,对于(u,v)如果low[v]>=dfn[u]那么u为割点,特判根结点,若根结点子树有超过 ...

  3. poj&lowbar;1144Network&lpar;tarjan求割点&rpar;

    poj_1144Network(tarjan求割点) 标签: tarjan 割点割边模板 题目链接 Network Time Limit: 1000MS Memory Limit: 10000K To ...

  4. Tarjan求割点和桥

    by szTom 前置知识 邻接表存储及遍历图 tarjan求强连通分量 割点 割点的定义 在一个无向图中,如果有一个顶点集合,删除这个顶点集合以及这个集合中所有顶点相关联的边以后,图的连通分量增多, ...

  5. UESTC 900 方老师炸弹 --Tarjan求割点及删点后连通分量数

    Tarjan算法. 1.若u为根,且度大于1,则为割点 2.若u不为根,如果low[v]>=dfn[u],则u为割点(出现重边时可能导致等号,要判重边) 3.若low[v]>dfn[u], ...

  6. POJ 1144 Network(Tarjan求割点)

    Network Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 12707   Accepted: 5835 Descript ...

  7. poj 1523 SPF(tarjan求割点)

    本文出自   http://blog.csdn.net/shuangde800 ------------------------------------------------------------ ...

  8. 洛谷P3388 【模板】割点(割顶)&lpar;tarjan求割点&rpar;

    题目背景 割点 题目描述 给出一个n个点,m条边的无向图,求图的割点. 输入输出格式 输入格式: 第一行输入n,m 下面m行每行输入x,y表示x到y有一条边 输出格式: 第一行输出割点个数 第二行按照 ...

  9. &lbrack;POJ1144&rsqb;&lbrack;BZOJ2730&rsqb;tarjan求割点

    求割点 一种显然的n^2做法: 枚举每个点,去掉该点连出的边,然后判断整个图是否联通 用tarjan求割点: 分情况讨论 如果是root的话,其为割点当且仅当下方有两棵及以上的子树 其他情况 设当前节 ...

随机推荐

  1. 2016年Q2《网络安全创新500强》榜单解读

    近日,美国投资咨询机构Cybersecurity Ventures发布了2016 Q2<网络安全创新500强>企业榜单,新兴安全公司root9B异军突起,国内4家企业上榜. 关于Cyber ...

  2. Servlet与多线程与IO操作

    1.JVM内存模型相关概念 2.Java多线程并发深入理解 3.Servlet.设计模式.SpringMVC深入理解 4.Java基础遗漏点补充 数据库连接池:JDBC connection pool ...

  3. OAF&lowbar;OAF Debug And Log调试和记录工具的详解(案例)

    2014-06-16 Created By BaoXinjian

  4. selenium python (四)键盘事件

    #!/usr/bin/python# -*- coding: utf-8 -*-__author__ = 'zuoanvip' #在实际测试过程中,有时候我们需要使用tab键将焦点转移到下一个需要操作 ...

  5. java实现线性链表结构

    package com.hephec.ds; public class LinkedList<T> { //定义一个内部类节点Node Node实例代表链表的节点 class Node{ ...

  6. hive高级数据类型

    hive的高级数据类型主要包括:数组类型.map类型.结构体类型.集合类型,以下将分别详细介绍. 1)数组类型 array_type:array<data_type> -- 建表语句 cr ...

  7. python字符串之format格式化函数

    学习中~ 觉得应该系统地学习一下python,今天学习了字符串,以下是自己的笔记. 首先说一下format函数,用{}和:代替了%,比如: >>>“{} {} {}”.format( ...

  8. JS代理模式实现图片预加载

    ---恢复内容开始--- 刚刚说了懒加载,现在我们来搞搞预加载吧 预加载的核心: 图片等静态资源在使用前提前请求. 资源后续使用可以直接从缓存中加载,提升用户体验. 几个误区: 预加载不是为了减少页面 ...

  9. &lbrack;noip模拟题&rsqb;排队

    [问题描述] 小sin所在的班有n名同学,正准备排成一列纵队,但他们不想按身高从矮到高排,那样太单调,太没个性.他们希望恰好有k对同学是高的在前,矮的在后,其余都是矮的在前,高的在后.如当n=5,k= ...

  10. 精华阅读第 12 期 &vert; 最新 App Store 审核指南与10大被拒理由?

    很多时候,我们对技术的追求是没有止境的,我们需要不断的学习,进步,再学习,再进步!本文系移动精英开发俱乐部的第12期文章推荐阅读整理,其中涉及到了 Android 数据库框架,架构设计中的循环引用,同 ...