当前位置: 首页 > news >正文

1184. 欧拉回路(欧拉回路,模板题)

活动 - AcWing

给定一张图,请你找出欧拉回路,即在图中找一个环使得每条边都在环上出现恰好一次。

输入格式

第一行包含一个整数 t,t∈{1,2},如果 t=1,表示所给图为无向图,如果 t=2,表示所给图为有向图。

第二行包含两个整数 n,m,表示图的结点数和边数。

接下来 m 行中,第 i 行两个整数 vi,ui,表示第 i 条边(从 11 开始编号)。

  • 如果 t=1 则表示 vi 到 ui 有一条无向边。
  • 如果 t=2 则表示 vi 到 ui 有一条有向边。

图中可能有重边也可能有自环。

点的编号从 1 到 n。

输出格式

如果无法一笔画出欧拉回路,则输出一行:NO。

否则,输出一行:YES,接下来一行输出 任意一组 合法方案即可。

  • 如果 t=1,输出 m 个整数 p1,p2,…,pm。令 e=|pi|,那么 e 表示经过的第 i 条边的编号。如果 pi 为正数表示从 ve 走到 ue,否则表示从 ue 走到 ve。
  • 如果 t=2,输出 m 个整数 p1,p2,…,pm。其中 pi 表示经过的第 i 条边的编号。
数据范围

1≤n≤105
0≤m≤2×105

输入样例1:
1
3 3
1 2
2 3
1 3
输出样例1:
YES
1 2 -3
输入样例2:
2
5 6
2 3
2 5
3 4
1 2
4 2
5 1
输出样例2:
YES
4 1 3 5 2 6

解析: 

一、在无向图中(所有边都是连通的): 

(1)存在欧拉路径的充分必要条件:度数为奇数的点只能有0或2。 

(2)存在欧拉回路(起点和终点相同)的充分必要条件:度数为奇数的点只能有0个。 

二、在有向图中(所有边都是连通的): 

(1)存在欧拉路径的充分必要条件:要么所有点的入度均等于入度;要么除了两个点之外,其余所有的点的出度等于入度,剩余的两个点:一个满足出度比入度多1(起点),另一个满足入度比出度多1(终点)。 

(2)存在欧拉回路(起点和终点相同)的充分必要条件:所有点的入度均等于出度。 

欧拉回路的dfs用边来判重,不能用点。 

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
#include<unordered_set>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 1e5 + 5, M = 4e5 + 5, INF = 0x3f3f3f3f;int n, m;
int h[N], e[M], ne[M], idx;
int din[N], dout[N];
int ans[M], cnt;
bool used[M];
int type;void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}void dfs(int u) {//cout << "_______________________" << u << endl;for (int& i = h[u]; i != -1;) {if (used[i]) {i = ne[i];continue;}int t;if (type == 1) {t = i / 2 + 1;if (i & 1)t = -t;}else t = i + 1;used[i] = 1;if (type == 1) {used[i ^ 1] = 1;}int j = e[i];i = ne[i];dfs(j);ans[++cnt] = t;}
}int main() {cin >> type;cin >> n >> m;memset(h, -1, sizeof h);for (int i = 1,a,b; i <= m; i++) {scanf("%d%d", &a, &b);add(a, b);if (type == 1)add(b, a);din[b]++, dout[a]++;}if (type == 1) {for (int i = 1; i <= n; i++) {if (din[i] + dout[i] & 1) {cout << "NO" << endl;return 0;}}}else {for (int i = 1; i <= n; i++) {if (din[i] != dout[i]) {cout << "NO" << endl;return 0;}}}for (int i = 1; i <= n; i++) {if (h[i] != -1) {dfs(i);break;}}if (cnt < m) {cout << "NO" << endl;return 0;}cout << "YES" << endl;for (int i = cnt; i; i--) {printf("%d ", ans[i]);}return 0;
}

相关文章:

1184. 欧拉回路(欧拉回路,模板题)

活动 - AcWing 给定一张图&#xff0c;请你找出欧拉回路&#xff0c;即在图中找一个环使得每条边都在环上出现恰好一次。 输入格式 第一行包含一个整数 t&#xff0c;t∈{1,2}&#xff0c;如果 t1&#xff0c;表示所给图为无向图&#xff0c;如果 t2&#xff0c;表示所给图为…...

学习 Redis 基础数据结构,不讲虚的。

学习 Redis 基础数据结构&#xff0c;不讲虚的。 一个群友给我发消息&#xff0c;“该学的都学了&#xff0c;怎么就找不到心意的工作&#xff0c;太难了”。 很多在近期找过工作的同学一定都知道了&#xff0c;背诵八股文已经不是找工作的绝对王牌。企业最终要的是可以创造价…...

Android 11 webview webrtc无法使用问题

问题&#xff1a;Android 11 webview 调用webrtc无法使用, 看logcat日志会报如下错误 [ERROR:address_tracker_linux.cc(245)] Could not send NETLINK request: Permission denied (13) 查了下相关的网络权限都有配置了还是不行&#xff0c;还是报这个权限问题 原因&#xff1…...

嵌入式单片机中晶振的工作原理

晶振在单片机中是必不可少的元器件&#xff0c;只要用到CPU的地方就必定有晶振的存在&#xff0c;那么晶振是如何工作的呢&#xff1f; 什么是晶振 晶振一般指晶体振荡器&#xff0c;晶体振荡器是指从一块石英晶体上按一定方位角切下的薄片&#xff0c;简称为晶片。 石英晶体谐…...

AWS配置内网EC2服务器上网【图形化配置】

第一种方法&#xff1a;创建EC2选择启用分配公网ip 1. 创建vpc 2. 创建子网 3. 创建互联网网关 创建互联网网关 创建互联网网关 &#xff0c;设置名称即可 然后给网关附加到新建的vpc即可 4. 给新建子网添加路由规则&#xff0c;添加新建的互联网网关然后点击保存更改 5. 新建…...

Android中的MVVM

演变 开发常用的框架包括MVC、MVP和本文的MVVM&#xff0c;三种框架都是为了分离ui界面和处理逻辑而出现的框架模式。mvp、mvvm都由mvc演化而来&#xff0c;他们不属于某种语言的框架&#xff0c;当存在ui页面和逻辑代码时&#xff0c;我们就可以使用这三种模式。 model和vie…...

制作耳机壳的UV树脂和塑料材质相比劣势有哪些?

以下是UV树脂相比塑料材质可能存在的劣势&#xff1a; 价格较高&#xff1a;相比一些常见的塑料材质&#xff0c;UV树脂的价格可能较高。这主要是因为UV树脂的生产过程较为复杂&#xff0c;需要较高的技术和设备支持。加工难度大&#xff1a;虽然UV树脂的加工过程相对简单&…...

CSP-202012-1-期末预测之安全指数

CSP-202012-1-期末预测之安全指数 题目很简单&#xff0c;直接上代码 #include <iostream> using namespace std; int main() {int n, sum 0;cin >> n;for (int i 0; i < n; i){int w, score;cin >> w >> score;sum w * score;}if (sum > 0…...

Doris中的本地routineload环境,用于开发回归测试用例

----------------2024-2-6-更新-------------- doris的routineload&#xff0c;就是从kafka中加载数据到表&#xff0c;特点是定时、周期性的从kafka取数据。 要想在本地开发测试routine load相关功能&#xff0c;需要配置kafka环境&#xff0c;尤其是需要增加routine load回…...

【开源项目阅读】Java爬虫抓取豆瓣图书信息

原项目链接 Java爬虫抓取豆瓣图书信息 本地运行 运行过程 另建项目&#xff0c;把四个源代码文件拷贝到自己的包下面 在代码爆红处按ALTENTER自动导入maven依赖 直接运行Main.main方法&#xff0c;启动项目 运行结果 在本地磁盘上生成三个xml文件 其中的内容即位爬取…...

基于opencv-python模板匹配的银行卡号识别(附源码)

目录 介绍 数字模板处理 银行卡图片处理 导入数字模板 模板匹配及结果 介绍 我们有若干个银行卡图片和一个数字模板图片&#xff0c;如下图 我们的目的就是通过对银行卡图片进行一系列图像操作使得我们可以用这个数字模板检测出银行卡号。 数字模板处理 首先我们先对数…...

JAVA设计模式之建造者模式详解

建造者模式 1 建造者模式介绍 建造者模式 (builder pattern), 也被称为生成器模式 , 是一种创建型设计模式. 定义: 将一个复杂对象的构建与表示分离&#xff0c;使得同样的构建过程可以创建不同的表示。 **建造者模式要解决的问题 ** 建造者模式可以将部件和其组装过程分开…...

ElasticSearch查询语句用法

查询用法包括&#xff1a;match、match_phrase、multi_match、query_string、term 1.match 1.1 不同字段权重 如果需要为不同字段设置不同权重&#xff0c;可以考虑使用bool查询的should子句来组合多个match查询&#xff0c;并为每个match查询设置不同的权重 {"query&…...

美国服务器如何

美国服务器在被选择名单里排名很高&#xff0c;那么美国服务器如何&#xff0c;美国服务器 适用于哪些场景&#xff0c;认可度高吗?接下来小编为您整理发布美国服务器如何的详细情况。 美国服务器通常以其高性能、高可靠性和安全性而受到认可&#xff0c;它们适用于多种业务场…...

远程主机可能不符合glibc和libstdc++ VS Code服务器的先决条件

报错信息 VSCode无法连接远程服务器&#xff0c;终端一直提醒&#xff1a; [22:46:01.906] > Waiting for server log... [22:46:01.936] > Waiting for server log... [22:46:01.951] > [22:46:01.967] > Waiting for server log... [22:46:01.982] > [22:…...

【python基础】sys.argv[]的使用方法

文章目录 前言一、sys.argv是什么&#xff1f;二、实例 前言 本文主要讲解sys.argv[]的使用方法。 一、sys.argv是什么&#xff1f; sys.arg[]的作用就是存储在运行python脚本时候从外部往被运行的py文件里面传递的参数&#xff0c;是一个列表对象。利用好这个属性可以极大的增…...

Element-Ui el-date-picker日期传值异常问题解决办法

首先&#xff0c;只要非常简单的组件引入写法&#xff1a; 然后myDate在data()中是字符串类型 myDate: ‘’ 然后增加一个方法在提交表单到后台的时候&#xff0c;用来转化日期对应到myDate成字符串类型&#xff0c;并且对应到java类 function checkType(value) {if (typeo…...

GO语言集成开发 JetBrains GoLand 2023 中文

JetBrains GoLand 2023是一款专为Go语言开发者打造的集成开发环境&#xff08;IDE&#xff09;。它基于IntelliJ IDEA平台&#xff0c;提供了丰富的功能和工具&#xff0c;旨在提高开发效率和质量。GoLand 2023具备强大的Go语言支持&#xff0c;包括语法高亮、自动补全、代码提…...

详细关于如何解决mfc140.dll丢失的步骤,有效修复mfc140.dll文件丢失的问题。

mfc140.dll文件是Microsoft Visual Studio 2015程序集之一&#xff0c;它包含用于支持多种功能的代码和库。当这个mfc140.dll文件丢失时&#xff0c;可能会导致相关程序运行出错甚至无法运行。很多用户可能会遇到mfc140.dll丢失的问题&#xff0c;但是这并不是不可解决的困难。…...

聚簇索引、非聚簇索引、回表、索引下推、覆盖索引

聚簇索引&#xff08;主键索引&#xff09; 非叶子节点上存储的是索引值&#xff0c;叶子节点上存储的是整行记录。 非聚簇索引&#xff08;非主键索引、二级索引&#xff09; 非叶子节点上存储的都是索引值&#xff0c;叶子节点上存储的是主键的值。非聚簇索引需要回表&…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:

一、属性动画概述NETX 作用&#xff1a;实现组件通用属性的渐变过渡效果&#xff0c;提升用户体验。支持属性&#xff1a;width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项&#xff1a; 布局类属性&#xff08;如宽高&#xff09;变化时&#…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...

pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)

目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 &#xff08;1&#xff09;输入单引号 &#xff08;2&#xff09;万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...

深入浅出Diffusion模型:从原理到实践的全方位教程

I. 引言&#xff1a;生成式AI的黎明 – Diffusion模型是什么&#xff1f; 近年来&#xff0c;生成式人工智能&#xff08;Generative AI&#xff09;领域取得了爆炸性的进展&#xff0c;模型能够根据简单的文本提示创作出逼真的图像、连贯的文本&#xff0c;乃至更多令人惊叹的…...

Visual Studio Code 扩展

Visual Studio Code 扩展 change-case 大小写转换EmmyLua for VSCode 调试插件Bookmarks 书签 change-case 大小写转换 https://marketplace.visualstudio.com/items?itemNamewmaurer.change-case 选中单词后&#xff0c;命令 changeCase.commands 可预览转换效果 EmmyLua…...

Qt的学习(二)

1. 创建Hello Word 两种方式&#xff0c;实现helloworld&#xff1a; 1.通过图形化的方式&#xff0c;在界面上创建出一个控件&#xff0c;显示helloworld 2.通过纯代码的方式&#xff0c;通过编写代码&#xff0c;在界面上创建控件&#xff0c; 显示hello world&#xff1b; …...