CF2110E Melody 题解 / Hierholzer 算法学习笔记

zrl123456 · 2025-11-21 20:57:13 · 题解

:::::info[题目基本信息] 考察：图论，欧拉回路（2300）。
题目简介：
给定序列 \{a_n\},\{b_n\}，判断是否 n 阶排列 \{p_n\} 满足以下条件，若存在构造一种方案：

• \forall i\in[2,n],a_{p_i}=a_{p_{i-1}}\lor b_{p_i}=b_{p_{i-1}}
• \forall i\in[3,n],(a_{p_{i-2}}\ne a_{p_{i-1}}\lor a_{p_{i-1}}\ne a_{p_i})\land(b_{p_{i-2}}\ne b_{p_{i-1}}\lor b_{p_{i-1}}\ne b_{p_i})

数据范围：

• 1\le n\le 2\times 10^5
• \forall i\in[1,n],1\le v_i,p_i\le 10^9
• \forall i,j\in[1,n],i\ne j,a_i\ne a_j\lor b_i\ne b_j

  ::::: 见二建图还在追我，先对 \{a_n\} 和 \{b_n\} 离散化，然后接下来把它们分别看成一个二分图的左部点和右部点，然后这 n 个对就是 n 条边，那么我们要求的就是这个二分图的欧拉路径。
  首先需要保证这个图联通并最多有两个点度数为奇数，然后跑 Hierholzer 算法。
  :::::success[Hierholzer 算法简介] 先讨论欧拉图（寻找欧拉回路）的情况，因为半欧拉图（寻找欧拉路径）的情况可以在两个度数为奇数的点之间连一条边转化为欧拉图情况。
  一个图是欧拉图有一条等价转化：整个图可以被拆解成若干个不共边的回路（仅讨论连通图）。
  ::::success[证明]

• 是欧拉图推拆解回路：
  众所周知，欧拉图的所有点度均为偶数，那么我们随便取一个度不为 0 的点 u，随便找到一个与其相连的边 (u,v) 并删除它，那么这时整个图有两个点度为奇数，这时递归 v 也一定能找到一条与其相连的边，这样递归下去直到回到点 u，这时我们找到了一个回路，不断操作，最终能删空图，命题也证毕。
• 拆解回路推是欧拉图：
  考虑合并这些回路，随便取两个回路，若两个回路共点直接合并，否则由于整个图联通，那么这两点间必定有一条路径，这条路径上的边肯定都属于一个回路，故一定有方法合并这两个回路，证毕。 :::: 好的，那么我们根据上述拆解回路推是欧拉路的证明我们容易得到 Hierholzer 算法的具体流程：先从一个点开始找到一条回路，然后在该回路周围找到一个共点回路合并它们即可。
  这个过程实际可以使用 DFS 实现，具体实现见代码。
  最终时间复杂度为 \Theta(n+m)。
  ::::: 这样我们就做完了这道题。
  时间复杂度为 \Theta(n\log n)，空间复杂度为 \Theta(n)。

code