本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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