# 欧拉路径：从“每条边恰好一次”到字符串与定向构造 ## 本节目标 学完后，你应能： - 区分欧拉路径（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` 的点最多，奇度点也可能合格，上界与补边方式都会改变。 ## 高阶扩展 1：Two Trees——把两套子树约束拼成一张欧拉图 ### 来源信息、题意与范围 - VJudge：[AtCoder-agc018_f Two Trees](https://vjudge.net/problem/AtCoder-agc018_f) - 原题：[AtCoder Grand Contest 018 F](https://atcoder.jp/contests/agc018/tasks/agc018_f) - 官方难度口径：1700 分；主要考点：子树和奇偶、辅助图、欧拉回路定向 给出顶点编号相同的两棵 $N$ 点根树。构造整数 $X_1,ldots,X_N$，使两棵树中每个顶点的整棵子树之和的绝对值都为 $1$；无解时报告。$1\le N\le10^5$，两行父亲数组各恰描述一棵合法根树。
Hint 1：先只看模 2 子树和是 $\pm1$，模 2 都等于 $1$。若 $v$ 有 $c_v$ 个孩子，把孩子子树的奇数和加起来，便能确定 $X_v$ 的奇偶。
Hint 2：两棵树何时立即矛盾 第一棵树给出 $X_v\equiv 1-c_v\pmod2$，第二棵树给出 $X_v\equiv1-d_v\pmod2$。所以所有 $c_v,d_v$ 必须同奇偶。
Hint 3：为什么答案只需 $0,\pm1$ 为两棵树各复制一层顶点。奇数型 $X_v$ 用一条跨层边连接两份 $v$；树边和两条“根到公共点”的边补齐各点度数。若所有度数为偶数，就能沿欧拉回路给跨层边定向。
### Observations 1. 直接同时做两棵树形 DP，会让同一个 $X_v$ 同时受两套祖先关系约束，状态没有局部闭合性；模 2 后，每棵树只留下“孩子数奇偶”这一条必要条件。 2. 条件通过后，不必搜索任意整数。令偶数型点取 $0$、奇数型点取 $\pm1$，问题变成让每棵树每个子树内的符号和为 $\pm1$。 3. “每个子树只剩一个未抵消符号”可由流量守恒表达：欧拉定向令辅助图每点入度等于出度，跨过一棵子树边界的净流恰为 $\pm1$。 ### Editorial、证明与复杂度 设第一、二棵树中 $v$ 的孩子数分别为 $c_v,d_v$。对子树和取模 2 得 $$ X_v+c_v\equiv1\pmod2, \qquad X_v+d_v\equiv1\pmod2. $$ 所以 $c_v\not\equiv d_v\pmod2$ 时无解。 否则建立 $2N+1$ 点辅助图：第一层放第一棵树的全部无向树边，第二层放第二棵树的树边；两棵树的根分别连公共点 $R$。当 $c_v$ 为偶数时，再连跨层边 $P_v-Q_v$。对 $P_v$ 而言，树边加根边共贡献 $c_v+1$ 度：$c_v$ 偶时再加跨层边，$c_v$ 奇时不加，两种情况度数都为偶数；第二层同理。辅助图连通且全点偶度，故存在欧拉回路。 沿回路方向定向所有边。跨层边 $P_v\to Q_v$ 时令 $X_v=1$，反向令 $X_v=-1$；无跨层边令 $X_v=0$。在第一层对任一子树内顶点做“入度 = 出度”求和，内部树边抵消，只剩子树根通向父亲/公共点的一条边与跨层边净流，因此子树内 $X$ 之和为 $\pm1$；第二层完全相同。这同时证明合法性和完备性。建图与 Hierholzer 都是 $O(N)$ 时间、$O(N)$ 空间。 ### 核心伪代码、实现边界与附件 ```text if parity(child_count_tree1[v]) differs from tree2 for some v: report IMPOSSIBLE build two tree layers P and Q plus common vertex R connect both roots to R for each v with even child count: add cross edge P[v] -- Q[v] tour = Euler_circuit(auxiliary_graph) for each v: X[v] = 0 if there is no cross edge otherwise X[v] = +1 or -1 according to its traversal direction ``` 父亲数组含唯一的 `-1` 根；辅助图的无向边必须共享编号。实现采用迭代 Hierholzer，避免 $N=10^5$ 的递归深度。完整 GNU C++17 附件：[AtCoder-agc018_f.cpp](../../参考实现/01-欧拉路径/AtCoder-agc018_f.cpp) ### 复盘与变式 识别信号不是“两棵树”，而是“每个层次集合的和只能为 $\pm1$”。若目标绝对值改成任意 $K>1$，模 2 只给必要条件，单条跨层边也不再足以表达边界净流，本构造失效。 ## 高阶扩展 2：Three Circuits——从构造回路转向压缩拓扑 ### 来源信息、题意与范围 - VJudge：[AtCoder-agc032_c Three Circuits](https://vjudge.net/problem/AtCoder-agc032_c) - 原题：[AtCoder Grand Contest 032 C](https://atcoder.jp/contests/agc032/tasks/agc032_c) - 官方难度口径：800 分；主要考点：欧拉图必要条件、二度点压缩、回路空间拓扑分类 给定简单连通无向图，问能否把全部边不重不漏地分成恰好三条 circuit；circuit 允许重复顶点但不允许重复边。$1\le N,M\le10^5$。
Hint 1：三条闭合行走给度数什么条件 每条 circuit 在每个点贡献偶数度，三者并仍要求原图所有点度数为偶数。
Hint 2：为什么只需关注度数至少 4 的点 度为 2 的点在任何分解中只能把两条关联边接成同一段，可把整条二度链压成一条“拓扑边”。
Hint 3：只有两个四度点时还差什么 设它们为 $A,B$。若存在一条完全避开 $B$、从 $A$ 回到 $A$ 的回路，就可把它与剩余结构拆成三条；否则压缩后只是四条 $A$ 到 $B$ 的链，只能两两配成两条 circuit。
### Observations 1. 先枚举三条回路会面对指数级边划分；度数奇偶直接排除所有非欧拉图。 2. 某点度至少 6 时，一条从该点开始的欧拉回路可按每次回到该点切成至少三段，删掉了全局划分搜索。 3. 若至少三个点度为 4，即使其余全为 2，压缩图也有足够的分叉把回路空间拆成三份；真正临界情形只有恰两个四度点。 ### Editorial、证明与复杂度 先检查所有度为偶数。若有点度至少 6，欧拉回路在该点产生至少三段闭合子行走，可合并多余段得到恰三条。以下最高度数为 4。若四度点至少三个，沿欧拉回路观察它们的重复出现，可以在三个分叉处重新配对边段得到三条 circuit。 若四度点少于两个，压缩全部二度链后的连通偶图至多只有一个分叉，不可能有三条非空 circuit。恰有两个四度点 $A,B$ 时，删除 $B$ 后检查 $A$ 是否仍位于某个环上：若是，该环作为第一条，余下偶度边含连接 $A,B$ 的两组边段，可分成另两条；若否，所有从 $A$ 出发的四条压缩边都通向 $B$，任一 circuit 必须消耗两条 $A-B$ 链，最多只能得到两条。一次 DFS 即可判定，时间 $O(N+M)$、空间 $O(N+M)$。 ### 核心伪代码、实现边界与附件 ```text if some degree is odd: No if some degree >= 6: Yes four = vertices with degree 4 if len(four) >= 3: Yes if len(four) <= 1: No A, B = four if DFS can leave A and return to A without visiting B: Yes else: No ``` 简单图条件让 DFS 中按父点跳过返边足够；若允许重边，必须改用父边编号，否则两条平行边组成的环会被漏掉。完整 GNU C++17 附件：[AtCoder-agc032_c.cpp](../../参考实现/01-欧拉路径/AtCoder-agc032_c.cpp) ### 复盘与变式 这题的迁移点是“先压缩所有行为被迫的二度点，再分类少数分叉点”。若题目要求输出三条 circuit，判定结论仍可用，但还需保存压缩链并在欧拉序上落实切分点。 ## 高阶课后训练：两道降级 CF - [CodeForces-547D Mike and Fish](https://vjudge.net/problem/CodeForces-547D)：把每个输入点看成连接其横坐标点与纵坐标点的边，欧拉交替染边平衡每个坐标上的两色数量。它和二分图章节的 `Fair Share` 共用考虑链，放在这里做迁移训练。 - [CodeForces-527E Data Center Drama](https://vjudge.net/problem/CodeForces-527E)：补齐奇度点，再在需要时补一条边令边数为偶数，最后沿欧拉回路交替定向。重点复盘每一种补边分别修复哪个不变量。 ## 扩展与联系 - **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` 即使不提交，也要自己写出“上界—构造达到上界”的两段证明，并构造一个含多个连通块的测试。