边双联通分量与割边

前言

在图论中,除了在有向图中的强连通分量,在无向图中还有一类双联通分量

双联通分量一般是指点双连通分量

当然,还有一种叫做边双连通分量

边双联通分量

对于一个连通图,如果任意两点至少存在两条“边不重复”的路径,则说图是点双连通的,边双连通的极大子图称为边双连通分量。

边双联通分量的计算方法比较简单

类比tarjan求强联通分量的算法,唯一的区别在于不能沿着dfs过来的那条边走回去。

也就是说在tarjan的时候我们需要记录一下父亲节点

其余的就和普通的tarjan一样啦

例题

割边(桥)

割边:对于无向图中的边i,若去掉i,无向图的联通快个数会增加,则称点i为割边(桥)

计算方法

不难发现一条边是割边当且仅当他不在任何一个边双里。

也就是说当low[v]>dfn[u](u,v)就是一条割边。

例题

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

HDU 1874 畅通工程续【Floyd算法实现】

畅通工程续 Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Jav...

294100
来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之变态跳台阶(九度OJ1389)

题目描述: 一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 输入: 输入可能包含多个测试样例,对...

19980
来自专栏Deep learning进阶路

caffe随记(五)---/build/tools/caffe.bin工具简析

1、怎么用这个命令 在caffe根目录下输入如下命令:  ./build/tools/caffe.bin, 得到如下显示 ? usage:caffe<comm...

64200
来自专栏尾尾部落

[剑指offer] 变态跳台阶

一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

12520
来自专栏数据结构与算法

点双连通分量与割点

前言 在图论中,除了在有向图中的强连通分量,在无向图中还有一类双连通分量 双连通分量一般是指点双连通分量 当然,还有一种叫做边双连通分量 点双连通分量 对于一个...

38280
来自专栏开发与安全

算法:最短路径之弗洛伊德(Floyd)算法

为了能讲明白弗洛伊德(Floyd)算法的主要思想,我们先来看最简单的案例。图7-7-12的左图是一个简单的3个顶点的连通网图。 ? 我们先定义两个二维数组D[3...

97270
来自专栏空间大数据可视化

GIS基础算法之Kruskal算法(2015.10.15)

13350
来自专栏一棹烟波

OpenGL进行简单的通用计算实例

博主作为OpenGL新手,最近要用OpenGL进行并行的数据计算,突然发现这样的资料还是很少的,大部分资料和参考书都是讲用OpenGL进行渲染的。好不容易找到一...

30970
来自专栏用户2442861的专栏

Python-OpenCV 处理图像(二):滤镜和图像运算

喜欢自拍的人肯定都知道滤镜了,下面代码尝试使用一些简单的滤镜,包括图片的平滑处理、灰度化、二值化等:

25910
来自专栏开发与安全

数据结构:图的存储结构之邻接矩阵

图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图。一个一维的数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息...

71680

扫码关注云+社区

领取腾讯云代金券