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

欧拉路径 欧拉图 小记

欧拉路径 & 欧拉图 小记

P7771 【模板】欧拉路径

欧拉路径:一个图中经过每条边恰好一次的路径,允许经过重复点。

欧拉回路:起点与终点相同的欧拉路径。

对于连通图,欧拉路径有如下判定:

  1. 对于无向图,恰好有两个点度数为奇数时,存在起点与终点不同的欧拉路径,且起点与终点就是这两个奇度数的点。
  2. 对于无向图,所有点度数均为偶数时,存在欧拉回路。
  3. 对于有向图,存在一个点 \(x\) 满足 \(deg_{out}+1=deg_{in}\),且存在一个点 \(y\) 满足 \(deg_{in}+1=deg_{out}\),且其他点入度等于出度,则存在起点与终点不同的欧拉路径,且 \(x\) 是起点,\(y\) 是终点。
  4. 对于有向图,所有点入度等于出度,存在欧拉回路。

寻找欧拉路径

基本思想:定义递归函数 \(dfs(x)\) 返回一个 \(x\) 的环,过程如下,先找到一个 \(x\) 的环 \(T\) 使得每条边都没有被走过,然后对于环上的每一个点 \(y\),将 \(dfs(y)\) 返回的环插入 \(T\) 中。

算法实际上不太一样,对于 \(dfs(x)\)

  1. 首先遍历每条未走过的出边(可能之前调用过 \(x\) 导致一些出边已走过)到 \(v\)
  2. 调用 \(dfs(v)\)
  3. 当所有出边都遍历完后,将 \(x\) 加入答案序列。

最后倒序输出答案序列即题目所需的答案。

本题还要求字典序最小,因此需要将出边排序,用 vector 记录出边。

实现上对于每一个点 \(x\) 记录 \(cur_x\) 表示当前弧,因为一个递归树中可能出现标号为 \(x\) 的点的子树内又出现了标号为 \(x\) 的点。

http://www.hskmm.com/?act=detail&tid=24995

相关文章:

  • OI 笑传 #16
  • cf296b
  • 第一次使用Ttpora
  • Apache反向代理
  • 原版 Sunshine+虚拟显示器实现熄屏串流
  • 2025国庆Day4
  • gis坐标计算
  • day17 课程()
  • NKOJ全TJ计划——NP11744
  • ROIR 2025
  • trick 小记
  • python编写AI生常用匡架及使用指令集
  • 123123
  • 1005模拟赛总结
  • 2025.10.5 2024CCPC郑州
  • 20250531MATLAB三维绘图 - 教程
  • 概率期望dp 复习笔记
  • 2025.10
  • PCIe扫盲——物理层逻辑部分基础(一)
  • 仅需3%训练数据的文本归一化技术
  • 价值原语博弈协议:价值原语共识锚定原则
  • 实用指南:工作流引擎-16-开源审批流项目之 整合Flowable官方的Rest包
  • 25fall做题记录-October - Amy
  • 嗯嗯
  • PCIe扫盲——AckNak 机制详解(二)
  • ASP.NET Core SignalR 身份认证集成指南(Identity + JWT) - 详解
  • utorrent 2.2.1
  • 2025热缩管厂家 TOP 企业品牌推荐排行榜,氟橡胶,双壁,线缆标识,防滑花纹,DR 耐油橡胶,PVDF,标识,航插用,军用热缩管公司推荐!
  • 市场交易反心理特征之八:劣仓驱逐良仓
  • 做题笔记18