欧拉路径：从“每条边恰好一次”到字符串与定向构造

觉得“边恰好一次”和 Hierholzer 还陌生？先完成课前零食：从散步到欧拉回路，并运行其中的小实验室。

本节目标

学完后，你应能：

区分欧拉路径（Eulerian trail）、欧拉回路（Eulerian circuit）与哈密顿路径；
从度数与连通性推导无向图、有限有向图的存在条件；
不靠“删边 DFS”实现 $O(V+E)$ 的 Hierholzer 算法；
把“对象首尾相接”“相邻窗口重建”“让入度等于出度”识别成边覆盖问题；
证明构造使用了每条边且仅一次，并处理重边、自环、孤立点和非连通图。

前置知识与课前自测

前置：DFS、栈、图的度数、弱连通。

一条经过每个点恰好一次的路径，和经过每条边恰好一次的路径是同一问题吗？
无向图恰有两个奇度点时，欧拉路径的端点能否任意选择？
有向图所有点都满足入度等于出度，是否一定存在覆盖全部边的欧拉回路？
邻接表中直接删除已走边为什么可能退化到 $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 和每个点的邻接表游标：

栈顶还有未使用边，就使用一条边并把下一点压栈；
栈顶无边可走，说明它在当前剩余图中是死端，把它弹出并追加到答案；
最后反转答案。

为什么“死端倒序入答案”不会破坏相邻性？弹出 $v$ 时，栈中前一个点与 $v$ 之间正是把 $v$ 压栈的那条边；后发现的子回路会在倒序中自然插入。

每条邻接记录只被游标扫过一次，因此时间为 $O(V+E)$，空间为 $O(V+E)$。

核心知识

存在条件

图类型	度数条件	连通条件	起点
无向欧拉回路	所有非零度点为偶数	非零度点连通	任一非零度点
无向欧拉路径	恰有两个奇度点	非零度点连通	任一奇度点
有向欧拉回路	所有点入度 = 出度	非零度点弱连通	任一非零度点
有向欧拉路径	恰有一个点 $\Delta=+1$、一个点 $\Delta=-1$，其余 $\Delta=0$	非零度点弱连通	$\Delta=+1$ 的点

空边图要按题意单独处理：数学上可把单点长度零行走看作回路，但输出协议未必接受。

正确性框架

Hierholzer 的证明可以拆成三件事：

不重复：边一经取出即标记，之后不会再走。
不遗漏：若最终仍有未使用边，连通性保证它能从已构造路线上的某点到达；该点弹栈前却应仍有可走边，矛盾。
顺序合法：答案中相邻顶点对应某次压栈使用的边；倒序弹栈等价于把闭合子回路插入主路线。

实现指南

无向图的一条边在邻接表中出现两次，必须共享同一个 edge_id；标记边而不是标记方向。若题目把一条无向边明确要求来回各走一次，则应建成两条独立有向边，不能共享使用标记。

迭代写法避免深度达到 $E$ 时递归爆栈：

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
原来源：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

“两次且方向相反”不是额外次数约束，而是两种有向对象各用一次。
拆边后入出度天然平衡，题目又保证方案存在，核心只剩线性构造。
重边必须保留为不同邻接记录；用邻接矩阵会丢失重数。

Editorial 与正确性

对每条输入 $u-v$ 加入弧 $u\to v$ 和 $v\to u$，从 1 运行 Hierholzer。

每条弧只被游标消费一次，所以原道路的两个方向各出现一次；算法输出相邻点均由被消费的弧连接。题目保证所有需用边能从 1 所在路线覆盖，故最终路径含 $2M+1$ 个点，开头和结尾均为 1。时间 $O(N+M)$，空间 $O(N+M)$。

实现细节、核心伪代码与参考实现附件

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

复盘与变式

识别信号是“每条无向边按每个方向各一次”。若改成“每条无向边总共一次”，就必须共享边编号并检查奇度点；若要求字典序最小路线，需要先按目标顺序组织邻接边，但仍要在最终答案反转这一点上小心顺序方向。

精选例题 2：Play on Words

来源信息

VJudge：HDU-1116 Play on Words
原来源：Central Europe 1999
大致难度：模型建立；主要考点：单词链转有向欧拉路径、弱连通

题目描述与范围

每个单词是一块牌，若前一个单词的末字母等于后一个单词的首字母，就能相接。判断能否把全部 $N$ 个单词各用一次排成一条链。每组 $1\le N\le10^5$，单词由小写字母组成，长度为 2 到 1000；单词可重复。

Hint 1：点和边分别是什么

字母只有 26 个，单词数量很多。把字母视为点，把整个单词视为从首字母到末字母的一条有向边。

Hint 2：只检查度数够吗

不够。`ab, ba, cd, dc` 的每个字母都平衡，却分成两个连通块。

Hint 3：完整判定

非零度字母忽略方向后连通，并且入出度差满足有向欧拉回路或开放路径条件。

Observations

若把单词当点，边取决于两两能否相接，最坏需要 $O(N^2)$；把单词当边后图固定只有 26 点。
重复单词就是平行边，不能去重，但判定只需累计度数和连通关系。
本题只问存在性，不必真的保存 $10^5$ 条边或构造顺序。

Editorial 与正确性

对单词 $s$ 加一条 $s0\to s{|s|-1}$ 的边，统计入出度，并在忽略方向的 26 点图上合并两个端点。若所有出现过的字母属于同一连通块，且入出度差全部为 0，或恰有一个 $1$ 与一个 $-1$，则有欧拉链；反之，任一合法单词排列本身就是欧拉链，必满足这些条件。

读取成本与字符总数线性；额外算法成本 $O(N+26\alpha(26))$，空间 $O(26)$。

实现细节、核心伪代码与参考实现附件

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

复盘与变式

识别信号是“对象只由首尾决定相容性，且每个对象恰用一次”。若要求输出具体单词顺序，邻接边要保存单词编号并运行 Hierholzer；若要求字典序最小，还要明确比较的是单词本身还是最终拼接串。

精选例题 3：Tanya and Password

来源信息

VJudge：CodeForces-508D Tanya and Password
原题：Codeforces Round 288 (Div. 2)
难度：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

相邻窗口重叠 $k-1$ 个字符时，应把长度 $k-1$ 的窗口视为点、长度 $k$ 的窗口视为边。
字符集大小为 62，二元点最多 $62^2=3844$ 个，完全可以直接编码。
相同三元串是不同出现次数，必须保留平行边。

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$。

实现细节、核心伪代码与参考实现附件

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

复盘与变式

识别信号是“给出全部固定长度窗口并恢复序列”。推广到长度 $k$ 时，点是长度 $k-1$ 的串。若 $k$ 较大，不能直接用 $|\Sigma|^{k-1}$ 数组，应给出现过的窗口哈希编号；若要求字典序最小答案，则要控制边的选择顺序并重新确认反转后的顺序。

精选例题 4：One-Way Reform

来源信息

VJudge：CodeForces-723E One-Way Reform
原题：Codeforces Round 375 (Div. 2)
难度：2200；主要考点：奇偶不变量、补边、欧拉定向构造

题目描述与范围

给一张可不连通的简单无向图，把每条边定向，使入度等于出度的顶点尽量多，并输出最大数量及任一最优定向。每组 $1\le n\le200$，$0\le m\le n(n-1)/2$；所有测试的 $n$ 之和不超过 200。

Hint 1：先找不可逾越的上界

定向后 `入度 + 出度 = 原无向度数`。若两者相等，原度数必须是偶数。

Hint 2：偶度点能否同时达到上界

给每个奇度点连一条虚拟边到新点 0。增广图所有点度数都是偶数。

Hint 3：如何定向

对增广图的每个含边连通块求欧拉回路，按行走方向给真实边定向，最后丢掉虚拟边。

Observations

奇度点无论怎样定向，入度和出度不可能相等，所以答案至多是偶度点数。
补到新点 0 后，奇点度数变偶；奇点总数为偶数，所以 0 的度数也为偶数。
欧拉回路经过一个原顶点时入边和出边配对；删掉虚拟边只会破坏奇度点的平衡，所有原偶度点保持平衡。

Editorial 与正确性

统计原图偶度点数作为答案。为每个奇度点添加边 $0-v$，然后对增广图的所有含边连通块运行无向 Hierholzer，并按实际走边方向记录每条原边的方向。

上界由奇偶性给出。构造中每个原偶度点没有虚拟边，欧拉回路对其贡献成对的一入一出，删虚拟边后仍平衡；因此所有偶度点都达到上界，构造最优。每条增广边只处理一次，时间 $O(n+m)$，空间 $O(n+m)$。

实现细节、核心伪代码与参考实现附件

原图可能有多个全偶度连通块，它们不与虚拟点 0 相连，所以增广图被分成多个含边连通块；必须从每个尚有未用边的点启动一次 Hierholzer。边方向在“取出边并压栈”时记录即可。

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

复盘与变式

本题最重要的不是“会欧拉”，而是先用奇偶性写出答案上界，再用欧拉回路让所有可行点同时达到上界。若目标改成让 |out-in|≤1 的点最多，奇度点也可能合格，上界与补边方式都会改变。

高阶扩展 1：Two Trees——把两套子树约束拼成一张欧拉图

来源信息、题意与范围

VJudge：AtCoder-agc018_f Two Trees
原题：AtCoder Grand Contest 018 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

直接同时做两棵树形 DP，会让同一个 $X_v$ 同时受两套祖先关系约束，状态没有局部闭合性；模 2 后，每棵树只留下“孩子数奇偶”这一条必要条件。
条件通过后，不必搜索任意整数。令偶数型点取 $0$、奇数型点取 $\pm1$，问题变成让每棵树每个子树内的符号和为 $\pm1$。
“每个子树只剩一个未抵消符号”可由流量守恒表达：欧拉定向令辅助图每点入度等于出度，跨过一棵子树边界的净流恰为 $\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)$ 空间。

核心伪代码、实现边界与附件

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

复盘与变式

识别信号不是“两棵树”，而是“每个层次集合的和只能为 $\pm1$”。若目标绝对值改成任意 $K>1$，模 2 只给必要条件，单条跨层边也不再足以表达边界净流，本构造失效。

高阶扩展 2：Three Circuits——从构造回路转向压缩拓扑

来源信息、题意与范围

VJudge：AtCoder-agc032_c Three Circuits
原题：AtCoder Grand Contest 032 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

先枚举三条回路会面对指数级边划分；度数奇偶直接排除所有非欧拉图。
某点度至少 6 时，一条从该点开始的欧拉回路可按每次回到该点切成至少三段，删掉了全局划分搜索。
若至少三个点度为 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)$。

核心伪代码、实现边界与附件

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

复盘与变式

这题的迁移点是“先压缩所有行为被迫的二度点，再分类少数分叉点”。若题目要求输出三条 circuit，判定结论仍可用，但还需保存压缩链并在欧拉序上落实切分点。

高阶课后训练：两道降级 CF

CodeForces-547D Mike and Fish：把每个输入点看成连接其横坐标点与纵坐标点的边，欧拉交替染边平衡每个坐标上的两色数量。它和二分图章节的 Fair Share 共用考虑链，放在这里做迁移训练。
CodeForces-527E Data Center Drama：补齐奇度点，再在需要时补一条边令边数为偶数，最后沿欧拉回路交替定向。重点复盘每一种补边分别修复哪个不变量。

扩展与联系

de Bruijn 图：固定长度窗口重建、DNA 片段拼接等问题都可使用“前后缀为点、片段为边”。真实数据有错误时，问题会从严格欧拉转向路径覆盖或纠错，不再能直接套本节算法。
桥与强连通：给无向边定向并让可达性尽量强，常需要先找桥；见后续双连通章节。
最小字典序：局部总取最小边并不自动说明最终字符串最小，必须结合 Hierholzer 的逆序输出证明。
邮差问题：若必须覆盖全部边但允许重复且要最短，变成 Chinese Postman Problem；欧拉图只是其零增补特例。

总结与自检

写出四种图/路径组合的度数条件与连通条件。
为什么 Hierholzer 在“无边可走”时才把点加入答案？
Tanya and Password 中为什么三元串必须是边而不是点？
One-Way Reform 的最优性上界来自什么不变量？
无向图邻接表中的两条反向记录何时共享 used，何时不共享？

课后训练建议

先独立实现一个支持重边、自环的通用无向欧拉函数，并用输出边编号检查每边恰一次。
再做 Play on Words，限时 25 分钟完成“点/边选择 + 充要判定”。
Tanya and Password 卡 30 分钟可依次看 Hint 1–3；复盘重点是窗口重叠建图。
One-Way Reform 即使不提交，也要自己写出“上界—构造达到上界”的两段证明，并构造一个含多个连通块的测试。

01-判定构造与建模.md 26 KB Постоянна връзка История Директен файл

欧拉路径：从“每条边恰好一次”到字符串与定向构造

本节目标

前置知识与课前自测

问题动机：为什么普通 DFS 不够

步步式引导

1. 度数为什么限制端点

2. 为什么还要检查连通性

3. 从删边尝试到 Hierholzer

核心知识

存在条件

正确性框架

实现指南

精选例题 1：Watchcow

来源信息

题目描述与范围

Observations

Editorial 与正确性

实现细节、核心伪代码与参考实现附件

复盘与变式

精选例题 2：Play on Words

来源信息

题目描述与范围

Observations

Editorial 与正确性

实现细节、核心伪代码与参考实现附件

复盘与变式

精选例题 3：Tanya and Password

来源信息

题目描述与范围

Observations

Editorial 与正确性

实现细节、核心伪代码与参考实现附件

复盘与变式

精选例题 4：One-Way Reform

来源信息

题目描述与范围

Observations

Editorial 与正确性

实现细节、核心伪代码与参考实现附件

复盘与变式

高阶扩展 1：Two Trees——把两套子树约束拼成一张欧拉图

来源信息、题意与范围

Observations

Editorial、证明与复杂度

核心伪代码、实现边界与附件

复盘与变式

高阶扩展 2：Three Circuits——从构造回路转向压缩拓扑

来源信息、题意与范围

Observations

Editorial、证明与复杂度

核心伪代码、实现边界与附件

复盘与变式

高阶课后训练：两道降级 CF

扩展与联系

总结与自检

课后训练建议

01-判定构造与建模.md 26 KB

Постоянна връзка История Директен файл