# 欧拉路径：从“每条边恰好一次”到字符串与定向构造 ## 本节目标 学完后，你应能： - 区分欧拉路径（Eulerian trail）、欧拉回路（Eulerian circuit）与哈密顿路径； - 从度数与连通性推导无向图、有限有向图的存在条件； - 不靠“删边 DFS”实现 $O(V+E)$ 的 Hierholzer 算法； - 把“对象首尾相接”“相邻窗口重建”“让入度等于出度”识别成边覆盖问题； - 证明构造使用了每条边且仅一次，并处理重边、自环、孤立点和非连通图。 ## 前置知识与课前自测 前置：DFS、栈、图的度数、弱连通。 1. 一条经过每个**点**恰好一次的路径，和经过每条**边**恰好一次的路径是同一问题吗？ 2. 无向图恰有两个奇度点时，欧拉路径的端点能否任意选择？ 3. 有向图所有点都满足入度等于出度，是否一定存在覆盖全部边的欧拉回路？ 4. 邻接表中直接删除已走边为什么可能退化到 $O(E^2)$？
课前自测答案 1. 不是。前者约束顶点，后者约束边；星形图能很快给出反例。 2. 不能，两个奇度点必须分别是起点和终点。 3. 不一定；两组互不连通的有向环满足度数条件，却不能由一次行走覆盖。 4. 若每次从 `vector` 中间擦除或反复从表头寻找未使用边，同一批边可能被重复扫描、搬移。
## 问题动机：为什么普通 DFS 不够 设任务是“从仓库出发，恰好走完每条道路一次”。普通 DFS 的目标是访问顶点，它看见已访问顶点就可能拒绝一条尚未使用的边；即使改成标记边，直接输出 DFS 到达顺序，也可能在某个点过早走进死路。 最小例子是两个环共用一个顶点。若先走完其中一个环，局部上已经回到公共点；另一环仍可插入这条闭合路线。这个“把后来找到的回路插入已有路线”的能力，正是 Hierholzer 算法的核心。 ## 步步式引导 ### 1. 度数为什么限制端点 在无向路径内部，每次进入一个点，都要用另一条尚未使用的边离开，因此被使用的关联边两两配对。只有起点可以多一次“离开”，终点可以多一次“进入”。所以： - 欧拉回路中，所有非孤立点度数为偶数； - 开放欧拉路径中，恰有两个奇度点，且它们是端点。 有向图把“配对”改成一次入边配一次出边。记 $$ \Delta(v)=\operatorname{out}(v)-\operatorname{in}(v). $$ 回路要求所有 $\Delta(v)=0$；开放路径要求恰有一个点 $\Delta(v)=+1$（起点）、一个点 $\Delta(v)=-1$（终点），其余为 $0$。 ### 2. 为什么还要检查连通性 度数只描述每个点附近的平衡，不能把两块互不相连的边粘起来。无向图要求所有非零度点属于同一连通块；有向图只需先检查忽略方向后的弱连通，再结合入出度条件。 > 停顿：为什么有向图不必额外手写一次“强连通检查”？
展开推导 若是开放路径，先补一条“终点到起点”的边，所有点入出度平衡。把图缩成 SCC 后得到 DAG。若仍有多个 SCC，则 DAG 中存在入度为零的源 SCC；其内部总入度等于总出度，但它没有外来边，只要有外出边就矛盾。弱连通排除了孤立的第二块，因此补边后必为一个 SCC。回路情形同理。
### 3. 从删边尝试到 Hierholzer 维护一个栈 `st` 和每个点的邻接表游标： 1. 栈顶还有未使用边，就使用一条边并把下一点压栈； 2. 栈顶无边可走，说明它在当前剩余图中是死端，把它弹出并追加到答案； 3. 最后反转答案。 为什么“死端倒序入答案”不会破坏相邻性？弹出 $v$ 时，栈中前一个点与 $v$ 之间正是把 $v$ 压栈的那条边；后发现的子回路会在倒序中自然插入。 每条邻接记录只被游标扫过一次，因此时间为 $O(V+E)$，空间为 $O(V+E)$。 ## 核心知识 ### 存在条件 | 图类型 | 度数条件 | 连通条件 | 起点 | |---|---|---|---| | 无向欧拉回路 | 所有非零度点为偶数 | 非零度点连通 | 任一非零度点 | | 无向欧拉路径 | 恰有两个奇度点 | 非零度点连通 | 任一奇度点 | | 有向欧拉回路 | 所有点入度 = 出度 | 非零度点弱连通 | 任一非零度点 | | 有向欧拉路径 | 恰有一个点 $\Delta=+1$、一个点 $\Delta=-1$，其余 $\Delta=0$ | 非零度点弱连通 | $\Delta=+1$ 的点 | 空边图要按题意单独处理：数学上可把单点长度零行走看作回路，但输出协议未必接受。 ### 正确性框架 Hierholzer 的证明可以拆成三件事： 1. **不重复**：边一经取出即标记，之后不会再走。 2. **不遗漏**：若最终仍有未使用边，连通性保证它能从已构造路线上的某点到达；该点弹栈前却应仍有可走边，矛盾。 3. **顺序合法**：答案中相邻顶点对应某次压栈使用的边；倒序弹栈等价于把闭合子回路插入主路线。 ## 实现指南 无向图的一条边在邻接表中出现两次，必须共享同一个 `edge_id`；标记边而不是标记方向。若题目把一条无向边明确要求来回各走一次，则应建成两条独立有向边，不能共享使用标记。 迭代写法避免深度达到 $E$ 时递归爆栈： ```text stack = [start] reversed_path = [] while stack is not empty: v = stack[-1] advance cursor[v] past every already-used edge if v has no unused edge: reversed_path.append(stack.pop()) else: edge = take edge at cursor[v] mark edge used stack.append(edge.to) path = reverse(reversed_path) ``` 最终务必检查路径使用边数：有 $E$ 条边时，顶点序列长度应为 $E+1$。它能抓住遗漏连通性检查、起点选错和建图错误。 ## 精选例题 1：Watchcow ### 来源信息 - VJudge：[POJ-2230 Watchcow](https://vjudge.net/problem/POJ-2230) - 原来源：USACO 2005 January Silver - 大致难度：入门建模；主要考点：把无向边拆成两条有向边、Hierholzer ### 题目描述与范围 有 $N$ 个牧场和 $M$ 条双向道路，要求从 1 出发并回到 1，每条道路恰走两次，且两个方向各一次。$2\le N\le 10^4$，$1\le M\le 5\times10^4$；允许重边，题目保证存在方案。输出经过的 $2M+1$ 个顶点。 样例中每条无向边在输出路线里各以两个方向出现一次；输出不唯一。
Hint 1：先改变边的含义 不要在原无向图上要求“同一边使用两次”，而是把它拆成两条独立的弧。
Hint 2：度数还需要检查吗 每条原边贡献一条出弧和一条入弧，所以每个点自动满足入度等于出度。
Hint 3：算法框架 从 1 对拆出的 $2M$ 条弧运行有向 Hierholzer。每条弧只存在于一个邻接表中，可以用游标直接消费，无需 `used` 数组。
### Observations 1. “两次且方向相反”不是额外次数约束，而是两种有向对象各用一次。 2. 拆边后入出度天然平衡，题目又保证方案存在，核心只剩线性构造。 3. 重边必须保留为不同邻接记录；用邻接矩阵会丢失重数。 ### Editorial 与正确性 对每条输入 $u-v$ 加入弧 $u\to v$ 和 $v\to u$，从 1 运行 Hierholzer。 每条弧只被游标消费一次，所以原道路的两个方向各出现一次；算法输出相邻点均由被消费的弧连接。题目保证所有需用边能从 1 所在路线覆盖，故最终路径含 $2M+1$ 个点，开头和结尾均为 1。时间 $O(N+M)$，空间 $O(N+M)$。 ### 实现细节、核心伪代码与参考实现附件 ```text for each road (u, v): add_arc(u, v); add_arc(v, u) stack = [1]; reversed_route = [] while stack: u = stack[-1] if u still has an unused outgoing arc: stack.append(take_one_arc(u)) else: reversed_route.append(stack.pop()) output reverse(reversed_route) ``` 完整 GNU C++17 参考实现见附件：[POJ-2230.cpp](../../参考实现/01-欧拉路径/POJ-2230.cpp) ### 复盘与变式 识别信号是“每条无向边按每个方向各一次”。若改成“每条无向边总共一次”，就必须共享边编号并检查奇度点；若要求字典序最小路线，需要先按目标顺序组织邻接边，但仍要在最终答案反转这一点上小心顺序方向。 ## 精选例题 2：Play on Words ### 来源信息 - VJudge：[HDU-1116 Play on Words](https://vjudge.net/problem/HDU-1116) - 原来源：Central Europe 1999 - 大致难度：模型建立；主要考点：单词链转有向欧拉路径、弱连通 ### 题目描述与范围 每个单词是一块牌，若前一个单词的末字母等于后一个单词的首字母，就能相接。判断能否把全部 $N$ 个单词各用一次排成一条链。每组 $1\le N\le10^5$，单词由小写字母组成，长度为 2 到 1000；单词可重复。
Hint 1：点和边分别是什么 字母只有 26 个，单词数量很多。把字母视为点，把整个单词视为从首字母到末字母的一条有向边。
Hint 2：只检查度数够吗 不够。`ab, ba, cd, dc` 的每个字母都平衡，却分成两个连通块。
Hint 3：完整判定 非零度字母忽略方向后连通，并且入出度差满足有向欧拉回路或开放路径条件。
### Observations 1. 若把单词当点，边取决于两两能否相接，最坏需要 $O(N^2)$；把单词当边后图固定只有 26 点。 2. 重复单词就是平行边，不能去重，但判定只需累计度数和连通关系。 3. 本题只问存在性，不必真的保存 $10^5$ 条边或构造顺序。 ### Editorial 与正确性 对单词 $s$ 加一条 $s_0\to s_{|s|-1}$ 的边，统计入出度，并在忽略方向的 26 点图上合并两个端点。若所有出现过的字母属于同一连通块，且入出度差全部为 0，或恰有一个 $1$ 与一个 $-1$，则有欧拉链；反之，任一合法单词排列本身就是欧拉链，必满足这些条件。 读取成本与字符总数线性；额外算法成本 $O(N+26\alpha(26))$，空间 $O(26)$。 ### 实现细节、核心伪代码与参考实现附件 ```text for each word: add directed edge first_letter -> last_letter update in_degree, out_degree, and undirected DSU connected = all nonzero-degree letters have one DSU root degree_ok = all differences are 0, or exactly one +1 and one -1 answer = connected and degree_ok ``` 完整 GNU C++17 参考实现见附件：[HDU-1116.cpp](../../参考实现/01-欧拉路径/HDU-1116.cpp) ### 复盘与变式 识别信号是“对象只由首尾决定相容性，且每个对象恰用一次”。若要求输出具体单词顺序，邻接边要保存单词编号并运行 Hierholzer；若要求字典序最小，还要明确比较的是单词本身还是最终拼接串。 ## 精选例题 3：Tanya and Password ### 来源信息 - VJudge：[CodeForces-508D Tanya and Password](https://vjudge.net/problem/CodeForces-508D) - 原题：[Codeforces Round 288 (Div. 2)](https://codeforces.com/problemset/problem/508/D) - 难度：2500；主要考点：de Bruijn 式建图、有向欧拉路径、重边 ### 题目描述与范围 未知密码长度为 $n+2$。现在给出它的全部 $n$ 个长度为 3 的连续子串，并保留重复次数；字符来自大小写英文字母与数字。判断是否存在相符的字符串，若存在输出任意一个。$1\le n\le2\times10^5$。
Hint 1：两个三元串何时能相邻 `abc` 后能接 `bcd`，因为前者后两位等于后者前两位。
Hint 2：不要把三元串当点 把长度为 2 的串当点；三元串 `xyz` 是从 `xy` 到 `yz` 的一条边。
Hint 3：怎样恢复答案 求覆盖所有边的欧拉路径。先输出第一个二元点的两个字符，此后每到一个新点，只追加它的第二个字符。
Hint 4：最终保险 度数合法后仍检查欧拉顶点序列长度是否为 $n+1$；否则说明有另一块边没有被覆盖。
### Observations 1. 相邻窗口重叠 $k-1$ 个字符时，应把长度 $k-1$ 的窗口视为点、长度 $k$ 的窗口视为边。 2. 字符集大小为 62，二元点最多 $62^2=3844$ 个，完全可以直接编码。 3. 相同三元串是不同出现次数，必须保留平行边。 ### Editorial 与正确性 定义字符编码 `0..61`，把二元串编码成 `a*62+b`。每个输入三元串建立从前两字符到后两字符的边。按有向欧拉路径条件选起点，运行 Hierholzer；若结果不是 $n+1$ 个点则输出 `NO`。 若算法输出路径 $v_0,v_1,\ldots,v_n$，每条相邻转移对应且只对应一份输入三元串。拼接 $v_0$ 的两个字符，再依次追加 $v_i$ 的末字符，得到长度 $n+2$ 的串，其每个长度 3 窗口恰是路径中的对应边。反过来，任何合法密码的相邻窗口顺序都给出一条欧拉路径。因此算法充要。 时间 $O(n+62^2)$，空间 $O(n+62^2)$，适合 $2\times10^5$。 ### 实现细节、核心伪代码与参考实现附件 ```text encode every length-2 string as a vertex for trigram xyz: add edge xy -> yz check directed Euler degree conditions and select start path = Hierholzer(start) if len(path) != edge_count + 1: print NO else: print first 2-char vertex, then append each later vertex's last char ``` 完整 GNU C++17 参考实现见附件：[CodeForces-508D.cpp](../../参考实现/01-欧拉路径/CodeForces-508D.cpp) ### 复盘与变式 识别信号是“给出全部固定长度窗口并恢复序列”。推广到长度 $k$ 时，点是长度 $k-1$ 的串。若 $k$ 较大，不能直接用 $|\Sigma|^{k-1}$ 数组，应给出现过的窗口哈希编号；若要求字典序最小答案，则要控制边的选择顺序并重新确认反转后的顺序。 ## 精选例题 4：One-Way Reform ### 来源信息 - VJudge：[CodeForces-723E One-Way Reform](https://vjudge.net/problem/CodeForces-723E) - 原题：[Codeforces Round 375 (Div. 2)](https://codeforces.com/problemset/problem/723/E) - 难度：2200；主要考点：奇偶不变量、补边、欧拉定向构造 ### 题目描述与范围 给一张可不连通的简单无向图，把每条边定向，使入度等于出度的顶点尽量多，并输出最大数量及任一最优定向。每组 $1\le n\le200$，$0\le m\le n(n-1)/2$；所有测试的 $n$ 之和不超过 200。
Hint 1：先找不可逾越的上界 定向后 `入度 + 出度 = 原无向度数`。若两者相等，原度数必须是偶数。
Hint 2：偶度点能否同时达到上界 给每个奇度点连一条虚拟边到新点 0。增广图所有点度数都是偶数。
Hint 3：如何定向 对增广图的每个含边连通块求欧拉回路，按行走方向给真实边定向，最后丢掉虚拟边。
### Observations 1. 奇度点无论怎样定向，入度和出度不可能相等，所以答案至多是偶度点数。 2. 补到新点 0 后，奇点度数变偶；奇点总数为偶数，所以 0 的度数也为偶数。 3. 欧拉回路经过一个原顶点时入边和出边配对；删掉虚拟边只会破坏奇度点的平衡，所有原偶度点保持平衡。 ### Editorial 与正确性 统计原图偶度点数作为答案。为每个奇度点添加边 $0-v$，然后对增广图的所有含边连通块运行无向 Hierholzer，并按实际走边方向记录每条原边的方向。 上界由奇偶性给出。构造中每个原偶度点没有虚拟边，欧拉回路对其贡献成对的一入一出，删虚拟边后仍平衡；因此所有偶度点都达到上界，构造最优。每条增广边只处理一次，时间 $O(n+m)$，空间 $O(n+m)$。 ### 实现细节、核心伪代码与参考实现附件 原图可能有多个全偶度连通块，它们不与虚拟点 0 相连，所以增广图被分成多个含边连通块；必须从每个尚有未用边的点启动一次 Hierholzer。边方向在“取出边并压栈”时记录即可。 ```text answer = number of even-degree original vertices add dummy vertex 0 and edge 0-v for every odd-degree vertex v for every augmented connected component: follow an Euler circuit and orient each traversed original edge forward discard dummy edges and output recorded original orientations ``` 完整 GNU C++17 参考实现见附件：[CodeForces-723E.cpp](../../参考实现/01-欧拉路径/CodeForces-723E.cpp) ### 复盘与变式 本题最重要的不是“会欧拉”，而是先用奇偶性写出答案上界，再用欧拉回路让所有可行点同时达到上界。若目标改成让 `|out-in|≤1` 的点最多，奇度点也可能合格，上界与补边方式都会改变。 ## 扩展与联系 - **de Bruijn 图**：固定长度窗口重建、DNA 片段拼接等问题都可使用“前后缀为点、片段为边”。真实数据有错误时，问题会从严格欧拉转向路径覆盖或纠错，不再能直接套本节算法。 - **桥与强连通**：给无向边定向并让可达性尽量强，常需要先找桥；见后续双连通章节。 - **最小字典序**：局部总取最小边并不自动说明最终字符串最小，必须结合 Hierholzer 的逆序输出证明。 - **邮差问题**：若必须覆盖全部边但允许重复且要最短，变成 Chinese Postman Problem；欧拉图只是其零增补特例。 ## 总结与自检 1. 写出四种图/路径组合的度数条件与连通条件。 2. 为什么 Hierholzer 在“无边可走”时才把点加入答案？ 3. `Tanya and Password` 中为什么三元串必须是边而不是点？ 4. `One-Way Reform` 的最优性上界来自什么不变量？ 5. 无向图邻接表中的两条反向记录何时共享 `used`，何时不共享？ ## 课后训练建议 1. 先独立实现一个支持重边、自环的通用无向欧拉函数，并用输出边编号检查每边恰一次。 2. 再做 `Play on Words`，限时 25 分钟完成“点/边选择 + 充要判定”。 3. `Tanya and Password` 卡 30 分钟可依次看 Hint 1–3；复盘重点是窗口重叠建图。 4. `One-Way Reform` 即使不提交，也要自己写出“上界—构造达到上界”的两段证明，并构造一个含多个连通块的测试。