寒假2019培训:双连通分量(点双+边双)

2023-10-19 07:50

本文主要是介绍寒假2019培训:双连通分量(点双+边双),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

定义

若一个无向连通图不存在割点,则称它为“点双连通图”。若一个无向连通图不存在割边,则称它为“边双连通图”。
无向图的极大点双连通子图称为“点双连通分量”,简记为“v-DCC”。无向连通图的极大边双连通子图被称为“边双连通分量”,简记为“e-DCC”。二者统称为“双连通分量”,简记为“DCC”。


边双联通分量

求法:

核心概念: 没有割边
割边只会把图分成两部分,对图中的点没有影响。

在这里插入图片描述

在这里插入图片描述

用红色临摹出来的,便是割边(请看我的另一个博客了解割边)
Tarjan学习+割点+割边+强连通分量

删除他们
在这里插入图片描述
上面就有三个边双了~~

算法:只需求出无向图中所有的割边,把割边都删除后,无向图会分成若干个连通块,每一个连通块就是一个“边双连通分量”。
具体实现:一般先用Tarjan算法求出所有的桥,然后再对整个无向图执行一次dfs遍历(遍历的过程不访问割边),划分出每个连通块即可。

贴上代码~

void dfs(int x){color[x] = tot;for(int i = linkk[x];i;i = e[i].n)if(!color[e[i].y] && !e[i].flag) //e[i].flag表示i为割边dfs(e[i].y);
}
void make_node(){t = 0;memset(linkk,0,sizeof(linkk));for(int i = 1;i <= m;++i){int j = i * 2; int x = e[j].x , y = e[j].y;if(color[x] != color[y]) insert( color[x] , color[y] ) ;}return;
}
// 主程序for(int i = 1;i <= n;++i)if(!color[i]) ++tot , dfs(i);make_node();

上一道模板题吧

bzoj 1718: [Usaco2006 Jan] Redundant Paths 分离的路径

题目描述
In order to get from one of the F (1 <= F <= 5,000) grazing fields (which are numbered 1…F) to another field, Bessie and the rest of the herd are forced to cross near the Tree of Rotten Apples. The cows are now tired of often being forced to take a particular path and want to build some new paths so that they will always have a choice of at least two separate routes between any pair of fields. They currently have at least one route between each pair of fields and want to have at least two. Of course, they can only travel on Official Paths when they move from one field to another. Given a description of the current set of R (F-1 <= R <= 10,000) paths that each connect exactly two different fields, determine the minimum number of new paths (each of which connects exactly two fields) that must be built so that there are at least two separate routes between any pair of fields. Routes are considered separate if they use none of the same paths, even if they visit the same intermediate field along the way. There might already be more than one paths between the same pair of fields, and you may also build a new path that connects the same fields as some other path.

为了从F(1≤F≤5000)个草场中的一个走到另一个,贝茜和她的同伴们有时不得不路过一些她们讨厌的可怕的树.奶牛们已经厌倦了被迫走某一条路,所以她们想建一些新路,使每一对草场之间都会至少有两条相互分离的路径,这样她们就有多一些选择. 每对草场之间已经有至少一条路径.给出所有R(F-1≤R≤10000)条双向路的描述,每条路连接了两个不同的草场,请计算最少的新建道路的数量, 路径由若干道路首尾相连而成.两条路径相互分离,是指两条路径没有一条重合的道路.但是,两条分离的路径上可以有一些相同的草场. 对于同一对草场之间,可能已经有两条不同的道路,你也可以在它们之间再建一条道路,作为另一条不同的道路.

输入格式
Line 1: Two space-separated integers: F and R * Lines 2…R+1: Each line contains two space-separated integers which are the fields at the endpoints of some path.

第1行输入F和R,接下来R行,每行输入两个整数,表示两个草场,它们之间有一条道路.

输出格式
Line 1: A single integer that is the number of new paths that must be built.

最少的需要新建的道路数.

样例数据
input

7 7
1 2
2 3
3 4
2 5
4 5
5 6
5 7
output

2
样例解释:

Building new paths from 1 to 6 and from 4 to 7 satisfies the conditions.
1 2 3
±–±--+
: | |
: | |
6 ±–±--+ 4
/ 5 :
/ :
/ :
7 + - - - -
Check some of the routes:
1 - 2: 1 -> 2 and 1 -> 6 -> 5 -> 2
1 - 4: 1 -> 2 -> 3 -> 4 an

这篇关于寒假2019培训:双连通分量(点双+边双)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/238423

相关文章

BUUCTF靶场[web][极客大挑战 2019]Http、[HCTF 2018]admin

目录   [web][极客大挑战 2019]Http 考点:Referer协议、UA协议、X-Forwarded-For协议 [web][HCTF 2018]admin 考点:弱密码字典爆破 四种方法:   [web][极客大挑战 2019]Http 考点:Referer协议、UA协议、X-Forwarded-For协议 访问环境 老规矩,我们先查看源代码

线性因子模型 - 独立分量分析(ICA)篇

序言 线性因子模型是数据分析与机器学习中的一类重要模型,它们通过引入潜变量( latent variables \text{latent variables} latent variables)来更好地表征数据。其中,独立分量分析( ICA \text{ICA} ICA)作为线性因子模型的一种,以其独特的视角和广泛的应用领域而备受关注。 ICA \text{ICA} ICA旨在将观察到的复杂信号

内卷时代无人机培训机构如何做大做强

在当今社会,随着科技的飞速发展,“内卷”一词频繁被提及,反映了各行业竞争日益激烈的现象。对于无人机培训行业而言,如何在这样的时代背景下脱颖而出,实现做大做强的目标,成为每个培训机构必须深思的问题。以下是从八个关键方面提出的策略,旨在帮助无人机培训机构在内卷时代中稳步前行。 1. 精准定位市场需求 深入研究市场:通过市场调研,了解无人机行业的最新趋势、政策导向及未来发展方向。 明确目标

网络安全运维培训一般多少钱

在当今数字化时代,网络安全已成为企业和个人关注的焦点。而网络安全运维作为保障网络安全的重要环节,其专业人才的需求也日益增长。许多人都对网络安全运维培训感兴趣,那么,网络安全运维培训一般多少钱呢?   一、影响网络安全运维培训价格的因素   1. 培训内容的深度和广度   不同的网络安全运维培训课程涵盖的内容有所不同。一些基础的培训课程可能主要涉及网络安全基础知识、常见安全工具的使用等,价

培训第九周(部署k8s基础环境)

一、前期系统环境准备 1、关闭防火墙与selinux  [root@k8s-master ~]# systemctl stop firewalld[root@k8s-master ~]# systemctl disable firewalldRemoved symlink /etc/systemd/system/multi-user.target.wants/firewalld.servi

超全泛微E10-eBuilder功能培训视频教程(精华)含源码 火!!!

引言  在当今数字化转型的浪潮中,掌握强大而高效的工具将是职业发展的关键。泛微E10的低代码平台e-Builder不仅是一个功能强大的数字化运营管理平台,还为希望在工作中提升效率和技术技能的从业者提供了丰富的学习资源。在这篇文章中,我们将详细介绍泛微E10-eBuilder功能培训视频教程的内容,帮助你了解这款平台如何帮助你在数字化转型和职业提升中领先一步。 一、课程目录介绍 本次培训视频

知名AIGC人工智能专家培训讲师唐兴通谈AI大模型数字化转型数字新媒体营销与数字化销售

在过去的二十年里,中国企业在数字营销领域经历了一场惊心动魄的变革。从最初的懵懂无知到如今的游刃有余,这一路走来,既有模仿学习的艰辛,也有创新突破的喜悦。然而,站在人工智能时代的门槛上,我们不禁要问:下一个十年,中国企业将如何在数字营销的浪潮中乘风破浪? 一、从跟风到精通:中国数字营销的进化史 回顾过去,中国企业在数字营销领域的发展可谓是一部"跟风学习"的编年史。从最初的搜索引擎营销(SEM),

2014年暑假培训 - 数论

A银河上的星星 /**************************************************************     Problem: 1014     User: DoubleQ     Language: C++     Result: Accepted     Time:190 ms     Memor

2014级寒假特训之并查集专题

Problem A: Double和XXZ的生日宴请 Time Limit: 1 Sec   Memory Limit: 128 MB Submit: 9   Solved: 7 [ Submit][ Status][ Web Board] [ Edit] [ TestData] Description Double 和 XXZ同一天生日,他们俩30岁生日那天,当年

2019学习计划

工作三年了,第一年感觉是荒废的,第二年开始学习python,第三年开始自动化 感觉自己会的东西比较少,而且不够深入,流于表面 现制定一下今年大概的学习计划 需持续巩固加强:python、ui自动化、接口自动化、sql等 代码量需提升,敲的不够(重点) 学习: 1.移动端测试,appium等 2.前端知识系统整理学习  3.性能测试 4.docker入门,环境搭建 5.shell