Luogu P6066 [USACO05JAN] Watchcow S 题解 欧拉回路
题目链接:Luogu P6066 [USACO05JAN] Watchcow S 欧拉回路
题目描述:
给定一张无向图,输出任意一条从一号结点出发的欧拉回路(欧拉回路指每条无向边来回经过且只经过一次),给定的图保证这样的欧拉回路存在。
题解:
只需要从一号结点开始使用
Hierholzer算法进行遍历即可。对于一个存在欧拉回路或者欧拉通路的图Hierholzer算法的思想是一直在图中找环,每找到一个环就将这个环从图中删除。具体地:
- 遍历到某个结点时,找到一个以当前结点为起点的环,如果不存在这样的环,则退出;
- 从图中删除当前找到的环经过的边,然后依次从当前的环上的每个点遍历,即回到1。
- 将遍历的当前结点加入到栈中。
上述的过程保存的结点依次从栈中弹出,则是一条以传入结点开始的欧拉回路或者欧拉通路。
在实际实现中我们知道DFS算法可以找环,所谓的删除边的操作,我们则可以每遍历一条边即将边给删除,这样只需要一次遍历即可找到欧拉回路或者欧拉通路(因此时间复杂度为O(n+m)),对于边的删除操作,如果使用邻接矩阵存边,我们没访问一次便执行connect[u][v]--操作,对于邻接表我们可以通过给每一条边增加一个deleted的标志,遍历之后将deleted置为true或者使用一个cnt数组,cnt[u]表示u结点应该从第几条边开始遍历,每遍历一条边便使cnt[u]++即可达到删除边的操作,使用链式前向星也可以通过增加deleted标志来实现删除边的效果。具体可以参见代码实现。
特别地,对于需要按照字典序进行遍历的情况而言,我们需要使用邻接表存边,这样才能够进行排序。除此之外,对于有些题目会要求无向边只经过一次,我们在删除边的时候需要将其反向边也给删除掉,而如果使用邻接表进行存边的话,我们需要保存反向边的编号,同时对于自环需要额外注意反向边的编号差异,而如果使用链式前向星则可以通过i^1的方式很容易的获取到反向边,因此对于这种题目推荐使用邻接表保存排序后(如果需要的话),对邻接表进行遍历再通过链式前向星保存图(由于链式前向星后加入的边会先遍历,因此排序时往往需要逆序)。
代码:LuoguP6066
相关文章:
Luogu P6066 [USACO05JAN] Watchcow S 题解 欧拉回路
题目链接:Luogu P6066 [USACO05JAN] Watchcow S 欧拉回路 题目描述: 给定一张无向图,输出任意一条从一号结点出发的欧拉回路(欧拉回路指每条无向边来回经过且只经过一次),给定的图保证这样的欧拉回路存在。…...
计算机网络_1.6.3 计算机网络体系结构分层思想举例
1.6.3 计算机网络体系结构分层思想举例 1、实例引入(用户在主机中使用浏览器访问web服务器)2、从五层原理体系结构的角度研究该实例3、练习题 笔记来源: B站 《深入浅出计算机网络》课程 本节通过一个常见的网络应用实例,来介绍计…...
图论练习1
内容:,拆点,分层,传递,带限制的最小生成树 [HNOI2015]菜肴制作 题目链接 题目大意 有个限制,号菜肴在号前完成在满足限制的条件下,按照出菜( 是为了满足的限制 ) 解题思路 由限制…...
canvas设置图形各种混合模式,类似photoshop效果
查看专栏目录 canvas实例应用100专栏,提供canvas的基础知识,高级动画,相关应用扩展等信息。canvas作为html的一部分,是图像图标地图可视化的一个重要的基础,学好了canvas,在其他的一些应用上将会起到非常重…...
谷粒商城-P19
项目结构创建&提交到码云 数据库初始化 保持docker数据库一直打开 docker update redis --restartalways 连不上了,发现配置文件错了 换了一个配置文件。 快速开发 使用开源的脚手架 人人开源 (gitee.com) 使用renren-fast作为后台开发,使用…...
Vue3入门到实战笔记02
9. watch 作用:监视数据的变化(和Vue2中的watch作用一致)特点:Vue3中的watch只能监视以下四种数据: ref定义的数据。reactive定义的数据。函数返回一个值(getter函数)。一个包含上述内容的数组…...
CDN高防IP:技术解析与相关问题解答
在使用CDN高防IP技术的过程中,可能会遇到一些问题。下面是一些常见问题和相应的解答,希望能帮助读者更好地了解和使用CDN高防IP技术。 问题一:什么是CDN高防IP技术? 解答:CDN高防IP技术是一种通过将网站流量分散到多…...
【React】react组件传参
【React】react组件传参 一、props:父组件向子组件传参1、将普通的参数作为props传递2、将jsx作为props传递(组件插槽)(1)基础功能示例(2)进阶示例 二、自定义事件:子父组件向父组件…...
Vue/html中点击复制到剪贴板
1.使用JQ实现复制功能 html <div class"tran_one tran_yi"><div class"form-group"><textarea>文本</textarea></div><div class"form-group tran_group"><div class"tran_flex tran_left tran_co…...
MtfLive直播导航PHP源码,附带系统搭建教程
将自动采集斗鱼、虎牙、触手、YY、章鱼、电视直播按分类/关键词聚合,用户选择分类,可以观看到全网该关键词下正在直播的内容。 特点 PC站和H5移动站自适应 自动缓存,避免频繁抓取数据 自定义抓取采集规则,同时支持HTML和JSON …...
day19 初始HTML
什么是HTML HTML(Hyper Text Markup Language)超文本标记语言 超文本包括:文字、图片、音频、视频、动画等 HTML5,提供了一些新的元素和一些有趣的新特性,同时也建立了一些新的规则。这些元素、特性和规则的建立&…...
从编程中理解:退一步海阔天空
编程中,“退一步海阔天空”的理念指的是在面对问题时,有时过于纠结于细节或局部优化,反而会陷入困境。这时,如果能暂时放下手中的具体工作,从更高的层面或者换个角度来审视整个系统的设计和架构,可能会发现…...
【前沿技术杂谈:开源软件】引领技术创新与商业模式的革命
【前沿技术杂谈:开源软件】引领技术创新与商业模式的革命 开源软件如何推动技术创新开源软件的开放性和协作精神促进知识共享和技术迭代推动关键技术的发展开源软件与新技术的融合 开源软件的商业模式开源软件的商业模式将开源软件与商业软件相结合 开源软件的安全风…...
c# datatable 通过反射转成泛型list
在C#中,可以使用反射来将DataTable转换为泛型列表。下面是一个示例代码,展示了如何使用反射来实现这个转换过程: using System; using System.Collections.Generic; using System.Data;public class DataConverter {public List<T> Co…...
如何保证MySQL数据一致性
在当今大数据时代,数据库系统扮演着至关重要的角色,而MySQL作为一种流行的关系型数据库管理系统,在数据一致性方面拥有着丰富的机制和技术。下面简单的探讨MySQL是如何保证数据一致性的。 事务与ACID特性 要了解MySQL如何保证数据一致性&am…...
Android学习之路(27) ProGuard,混淆,R8优化
前言 使用java编写的源代码编译后生成了对于的class文件,但是class文件是一个非常标准的文件,市面上很多软件都可以对class文件进行反编译,为了我们app的安全性,就需要使用到Android代码混淆这一功能。 针对 Java 的混淆&#x…...
进程中线程使用率偏高问题排查
1. top命令查看CPU使用率高的进程 2. top -H -p 15931(进程PID) 查看进程下的线程 3. printf "%x\n" 17503(线程PID) 线程PID 10进制转16进制 0x445f 4. jstack -l 15931(JVM进程PID) 导出java进程栈信息,里面包含线程nid0x445f和所在的类࿰…...
【JavaEE进阶】 图书管理系统开发日记——肆
文章目录 🍃前言🎍约定前后端交互接⼝🍀服务器代码实现🚩控制层🚩业务层🚩数据层 🌴前端代码的修改⭕总结 🍃前言 今天我们来实现修改图书模块 首先我们先来看一下,需要…...
STM32--USART串口(1)串口协议
一、通信接口 全双工:通信双方能够同时进行双向通信; 半双工:通信双方能够进行双向通信,但不能同时通信; 单工:只能从一个设备到另一个设备; 同步:接收方可以在时钟信号的指引下进…...
单臂路由实验(华为)
思科设备参考: 单臂路由实验(思科) 一,实验目的 在路由器的一个接口上通过配置子接口的方式,实现相互隔离的不同vlan之间互通。 二,设备配置 Switch1 <Huawei>sys [Huawei]vlan batch 10 20…...
椭圆曲线密码学(ECC)
一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...
在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能
下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能,包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...
安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件
在选煤厂、化工厂、钢铁厂等过程生产型企业,其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进,需提前预防假检、错检、漏检,推动智慧生产运维系统数据的流动和现场赋能应用。同时,…...
涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战
“🤖手搓TuyaAI语音指令 😍秒变表情包大师,让萌系Otto机器人🔥玩出智能新花样!开整!” 🤖 Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制(TuyaAI…...
Redis数据倾斜问题解决
Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中,部分节点存储的数据量或访问量远高于其他节点,导致这些节点负载过高,影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...
网站指纹识别
网站指纹识别 网站的最基本组成:服务器(操作系统)、中间件(web容器)、脚本语言、数据厍 为什么要了解这些?举个例子:发现了一个文件读取漏洞,我们需要读/etc/passwd,如…...
音视频——I2S 协议详解
I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议,专门用于在数字音频设备之间传输数字音频数据。它由飞利浦(Philips)公司开发,以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...
