1. 项目概述与问题拆解最近在带学生刷信奥信息学奥林匹克题目P1341“无序字母对”这道题出现的频率不低但很多初学者一看到“欧拉路径”或者“一笔画”这些词就有点发怵。其实这道题的核心逻辑非常经典它把抽象的图论问题包装成了一个具体的字母配对问题非常适合用来理解图的基本操作和深度优先搜索DFS的应用。简单来说题目给你一堆无序的字母对比如 (a, b), (b, c)要求你找出一个字符串使得这个字符串中相邻的两个字母不区分顺序都出现在给定的字母对集合里并且每个字母对恰好用一次。这本质上就是在构建的图中寻找一条欧拉路径或欧拉回路。为什么说它经典因为它几乎涵盖了求解欧拉路径问题的所有标准步骤建图、判断奇度顶点、DFS寻找路径。用C来实现不仅能巩固STL如map,set,vector的使用更能深入理解邻接表存储图和递归回溯的写法。很多同学卡住的地方往往不是算法本身而是如何优雅地处理字符到整数的映射、如何确保字典序最小输出以及DFS递归中边删除的细节。接下来我们就抛开那些复杂的理论直接进入代码实战我会把每一步为什么这么做、可能会踩的坑都讲清楚。2. 核心思路与算法选择2.1 问题本质图论建模拿到“无序字母对”第一步永远是化繁为简把问题映射到已知模型上。我们可以把每个不同的字母看作图中的一个“顶点”Vertex。每一个给定的无序字母对例如ab就在对应的两个顶点‘a’和‘b’之间连上一条“边”Edge。由于是无序对这条边是无向边。题目要求最终字符串相邻字母构成的配对必须来自给定集合且每个配对用一次。这翻译成图论语言就是我们需要找到一条路径它经过图中每条边恰好一次。这妥妥的就是欧拉路径或回路的定义。欧拉回路起点和终点是同一个顶点且经过所有边一次。对应到本题就是找到的字符串首尾字母相同。欧拉路径起点和终点不同且经过所有边一次。对应到本题就是找到的字符串首尾字母不同。所以解题的大方向就明确了判断给定的图是否存在欧拉路径/回路如果存在则找出一条并且要求字典序最小。2.2 算法选择Hierholzer算法寻找欧拉路径最直观的方法是深度优先搜索DFS回溯。但纯回溯的写法容易超时因为要尝试所有可能的起点和顺序。更高效、更标准的算法是Hierholzer算法也叫逐步插入回路法。它的核心思想是“拆圈合并”流程清晰代码实现也相对固定判断存在性根据欧拉路径/回路的判定定理。对于无向图欧拉回路所有顶点的度数与该点相连的边数均为偶数。欧拉路径恰好有0个或2个顶点的度数为奇数。如果有2个奇度顶点它们必然是路径的起点和终点。如果奇度顶点数量不是0或2直接输出No Solution。确定起点为了满足字典序最小我们需要谨慎选择起点。如果存在欧拉回路所有点度为偶那么起点可以是任意点。为了字典序最小我们选择编号最小的顶点作为起点。如果存在欧拉路径两个奇度点那么起点必须是两个奇度点中编号较小的那个。终点则是另一个奇度点。这是保证字典序最小的关键因为DFS会优先尝试小编号的邻居。Hierholzer DFS从选定的起点开始进行深度优先搜索。但与普通DFS遍历顶点不同这里我们遍历的是边。递归函数的核心操作是对于当前顶点u寻找它的一条尚未走过的边(u, v)然后将这条边标记为已走过或删除接着递归地深入顶点v。当从v的递归调用返回后将顶点u压入一个栈或直接逆序记录。最终将这个记录逆序输出就是一条欧拉路径。为什么能保证字典序最小在DFS过程中当我们处于某个顶点u时我们需要枚举它的所有邻居v。如果我们按照邻居编号从小到大的顺序进行枚举那么每次都会优先走“字母序更小”的路径。由于Hierholzer算法最后是逆序记录路径这种“贪心”地先走小号邻居的策略最终生成的路径正是字典序最小的。这一点需要仔细体会。2.3 数据结构设计明确了算法就要设计好数据的“容器”。图的存储使用邻接表。这是处理稀疏图边数相对较少最常用的方式比邻接矩阵节省空间也方便枚举某个顶点的所有邻居。在C中我们可以用一个vectorint G[MAXN]或者vectormultisetint G(MAXN)。考虑到需要快速删除边标记边已访问使用multiset会很方便因为它内部有序且支持erase(iterator)。但本题字母范围小用vector存储后排序再用一个平行的vector或map记录边的访问状态也是常见做法。为了清晰展示我们采用mapint, int作为邻接矩阵来记录两点间的边数因为可能有重边并在DFS时消耗边数。度数的记录用一个数组degree[256]来记录每个字符顶点的度数。因为字母包括大小写ASCII码范围在0-255之间直接开一个大小为256的数组足够用下标就是字符的ASCII码。字符与索引的映射题目输入是字符但我们处理时用整数ASCII码更方便。所以不需要额外的映射结构直接用字符的整型值作为顶点编号即可。输出时再转换回char。路径存储用一个vectorint或string来存储最终路径上的顶点序列。3. 代码实现与逐行解析理论讲完我们直接上代码。我会把关键部分拆开逐一解释。3.1 头文件、全局变量与准备工作#include iostream #include string #include vector #include map #include algorithm using namespace std; const int MAX_CHAR 256; // ASCII码范围足够覆盖大小写字母 mapint, mapint, int graph; // 邻接表graph[u][v]表示边(u,v)的剩余数量 int degree[MAX_CHAR] {0}; // 记录每个顶点的度数 vectorint eulerPath; // 存储欧拉路径 // 深度优先搜索Hierholzer算法核心 void dfs(int u) { // 遍历当前顶点u的所有可能邻居v // 使用引用以便在遍历过程中修改graph for (auto kv : graph[u]) { int v kv.first; if (graph[u][v] 0) { // 如果边(u,v)还有剩余未访问 graph[u][v]--; // 消耗一条边 graph[v][u]--; // 因为是无向图对称边也要消耗 dfs(v); // 递归深入 } } // 当u的所有边都处理完后将u加入路径 // 注意这里是后序加入最终需要逆序输出 eulerPath.push_back(u); }代码解析与注意事项graph的数据结构这里使用了mapint, mapint, int这是一个双重映射。graph[u][v]的值表示顶点u和v之间剩余的边数。这种结构的好处是自动处理了顶点编号字符ASCII码。方便检查边是否存在以及剩余数量。在dfs的for循环中auto kv : graph[u]会遍历u的所有邻居v。由于map默认按键即顶点编号升序排列这就天然实现了按字典序编号序枚举邻居满足了题目对字典序最小的要求。这是一个非常巧妙的点。degree数组下标是字符的ASCII码值是该字符的度数。输入时每读入一条边(a,b)就执行degree[a]; degree[b];。dfs函数这是Hierholzer算法的核心实现。for (auto kv : graph[u])遍历u的所有出边。因为graph[u]本身是一个map遍历顺序是按键邻居顶点编号升序的保证了字典序。if (graph[u][v] 0)检查这条边是否还未被完全使用可能有重边。graph[u][v]--; graph[v][u]--;消耗一条无向边。必须两边同时减这是新手极易出错的地方。dfs(v);递归进入下一个顶点。eulerPath.push_back(u);在递归返回后将当前顶点加入路径。这个顺序导致路径是逆序存储的。3.2 主函数逻辑输入、判断与启动int main() { int n; cin n; // 1. 读入数据建图计算度数 for (int i 0; i n; i) { string s; cin s; int u s[0], v s[1]; // 直接使用字符的ASCII码作为顶点编号 graph[u][v]; graph[v][u]; // 无向图边是双向的 degree[u]; degree[v]; } // 2. 统计奇度顶点的数量和具体顶点 vectorint oddDegVertices; // 注意遍历范围应该是所有可能出现的顶点即所有度数0的顶点 // 为了找到编号最小的起点我们从‘A’到‘z’遍历但实际根据输入 // 更稳妥的方式是遍历所有度数0的点。这里简单起见遍历整个degree数组。 int startVertex -1; int minVertex MAX_CHAR; for (int i 0; i MAX_CHAR; i) { if (degree[i] 0) { minVertex min(minVertex, i); // 记录有度数的最小顶点作为回路起点候选 if (degree[i] % 2 1) { oddDegVertices.push_back(i); } } } // 3. 根据奇度顶点数量判断是否存在欧拉路径/回路 if (oddDegVertices.size() ! 0 oddDegVertices.size() ! 2) { cout No Solution endl; return 0; } // 4. 确定DFS的起点 if (oddDegVertices.size() 2) { // 欧拉路径起点是两个奇度点中较小的那个 startVertex min(oddDegVertices[0], oddDegVertices[1]); } else { // 欧拉回路起点是所有有度数的顶点中最小的那个 startVertex minVertex; } // 5. 执行深度优先搜索 dfs(startVertex); // 6. 检查并输出结果 // 理论上找到的路径长度应该是 边数1 n1 if (eulerPath.size() ! n 1) { // 这种情况通常意味着图不连通但根据题目数据约定如果存在欧拉路径图应该是连通的。 // 不过加上这个检查更稳健。 cout No Solution endl; return 0; } // 因为dfs是后序压入路径所以需要逆序输出 reverse(eulerPath.begin(), eulerPath.end()); for (int node : eulerPath) { cout char(node); } cout endl; return 0; }关键步骤解析输入与建图读入n对字母。将字符直接转为intASCII码作为顶点编号。同时更新graph和degree。奇度顶点统计遍历degree数组范围0-255找出所有度数大于0的顶点并记录其中度数为奇数的顶点到oddDegVertices。同时用一个minVertex记录所有有度数的顶点中编号最小的为后续确定起点做准备。存在性判断如果奇度顶点数量不是0或2直接输出No Solution。确定起点如果有2个奇度顶点起点是它们中编号较小的。这是保证字典序最小的决定性步骤之一。因为从较小的奇度点出发会优先消耗掉与小号邻居相连的边。如果没有奇度顶点欧拉回路起点就是所有有度数的顶点中编号最小的minVertex。执行DFS从确定的起点调用dfs函数。输出结果检查路径长度是否正确。理论上走过n条边会经过n1个顶点。如果长度不对可能图不连通尽管题目数据应保证连通输出无解。由于dfs是后序记录顶点路径是逆序存储的所以需要reverse后再输出。将整数顶点编号强制转换回char输出。3.3 一个完整的、可运行的代码整合将上述部分组合并增加一些健壮性检查和注释得到最终代码#include iostream #include string #include vector #include map #include algorithm using namespace std; const int MAX_CHAR 256; mapint, mapint, int g; // 邻接表g[u][v]表示边(u,v)的剩余数量 int deg[MAX_CHAR] {0}; vectorint path; void dfs(int u) { // 遍历u的所有邻居map保证按顶点编号升序遍历字典序 for (auto p : g[u]) { int v p.first; if (g[u][v] 0) { // 还有边可走 g[u][v]--; g[v][u]--; // 无向边对称处理 dfs(v); } } path.push_back(u); // 后序加入路径 } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; // 读入并建图 for (int i 0; i n; i) { string s; cin s; int u s[0], v s[1]; g[u][v]; g[v][u]; deg[u]; deg[v]; } // 找出所有度数为奇数的顶点以及最小的有度数的顶点 vectorint odd_nodes; int min_node MAX_CHAR; for (int i 0; i MAX_CHAR; i) { if (deg[i] 0) { min_node min(min_node, i); if (deg[i] 1) { // 判断奇数更快的位运算方式 odd_nodes.push_back(i); } } } // 欧拉路径/回路存在性判定 if (odd_nodes.size() ! 0 odd_nodes.size() ! 2) { cout No Solution\n; return 0; } // 确定起点 int start min_node; // 默认回路起点 if (odd_nodes.size() 2) { start min(odd_nodes[0], odd_nodes[1]); // 路径起点取两个奇度点中较小的 } // 开始Hierholzer算法 dfs(start); // 验证路径长度边数1 if (path.size() ! n 1) { // 图可能不连通尽管题目数据应保证连通性 cout No Solution\n; return 0; } // 逆序输出路径 reverse(path.begin(), path.end()); for (int node : path) { cout char(node); } cout \n; return 0; }4. 常见问题与调试技巧即使理解了算法自己实现时还是会遇到各种“坑”。下面是我和学生们在实战中总结的几个典型问题及解决方法。4.1 字典序问题为什么我的输出不是最小这是最常见的问题。确保以下几点起点选择正确如果有两个奇度点起点必须是编号较小的那个。如果所有点度数为偶起点必须是所有出现字母中编号最小的那个。邻居遍历顺序在DFS中枚举当前顶点u的邻居v时必须按照v的编号升序进行。我们代码中使用mapint, int来存储邻居map默认按键升序排列所以for (auto p : g[u])这个循环天然就是按字典序遍历的。如果你使用vector存储邻居务必在DFS前对每个顶点的邻居列表进行排序。重边处理如果存在多条相同的边如两个‘a’ ‘b’对在DFS中必须能够依次访问它们不能只访问一次就认为边没了。我们的代码用g[u][v]记录边数消耗时递减完美处理了重边。4.2 递归深度与栈溢出本题的边数n最大为(2626)^2 / 2级别但实际数据一般不会这么满。DFS的递归深度最多等于路径长度n1。对于n较大如接近1000的情况递归深度可能达到1000以上。虽然通常C的栈空间足够但为了更安全可以考虑以下方法显式栈实现将递归的Hierholzer算法改写成用stack手动维护的迭代形式。这能完全避免递归深度限制但代码稍复杂。编译器优化确保使用递归时开启编译器优化如-O2。系统栈扩容在有些在线评测系统可以设置栈大小如#pragma comment(linker, /STACK:1024000000,1024000000)但这并非标准C且不一定被所有OJ支持。对于信奥比赛递归深度通常不是瓶颈但要有这个意识。4.3 图不连通导致的错误欧拉路径存在的必要条件除了奇度顶点数为0或2还要求所有边所在的顶点属于同一个连通分量。我们的代码在最后检查了path.size() n 1如果不等很可能是因为图不连通存在孤立的边集。虽然根据P1341的题目描述和数据约定如果存在欧拉路径图保证是连通的但加上这个检查是一个好习惯能使程序更健壮。如果你想在DFS前就判断连通性可以这样做从我们确定的start顶点出发做一次DFS或BFS只遍历顶点不关心边。标记所有访问到的顶点。检查所有度数deg[i] 0的顶点是否都被标记了。如果有未被标记的说明图不连通直接输出No Solution。4.4 输入输出与性能关闭同步流在main函数开头使用ios::sync_with_stdio(false); cin.tie(nullptr);可以大幅提升C标准输入输出的速度对于大数据量输入至关重要。使用\n代替endlendl会刷新输出缓冲区较慢。除非需要立即输出否则用\n。字符处理直接使用char的ASCII码作为整数处理避免频繁的char-int转换。4.5 调试建议当你觉得代码逻辑都对但结果不对时可以尝试以下调试方法小数据测试构造几个简单的例子比如ab,bc,cd应该得到abcd或者ab,ac,bc奇度点a和c路径如abc或cba取字典序小的abc。手动模拟你的程序运行。打印中间状态在DFS函数中进入和退出时打印当前顶点观察递归顺序。打印path向量在逆序前后的内容。检查度数和图结构读入数据后打印出每个出现字母的度数以及邻接表g的内容确认建图是否正确。边界条件测试n1的情况测试所有字母都相同的情况如aa,aa测试不存在解的情况。5. 算法扩展与变式思考搞定P1341你对欧拉路径的基本应用就有了扎实的理解。这里可以延伸思考几个相关问题能帮你更深入地掌握这个知识点有向图的欧拉路径如果字母对是有序的即ab和ba不同那么图就变成了有向图。判定条件变为欧拉回路所有顶点的入度等于出度。欧拉路径恰好有一个顶点出度比入度多1起点一个顶点入度比出度多1终点其余顶点入度等于出度。Hierholzer算法同样适用只是建图和消耗边时要注意方向。输出所有方案如果题目不要求字典序最小而是要求输出所有可能的欧拉路径那就需要用到回溯法在DFS时尝试所有可能的边顺序并记录所有完整路径。时间复杂度会指数级增长。实际应用场景欧拉路径/回路算法不仅仅是刷题工具它有很多实际应用比如DNA片段组装将测序得到的短序列看作边拼接成长序列。一笔画问题经典的哥尼斯堡七桥问题。电路板布线需要不重复地走过所有线路。单词接龙寻找一个单词序列使得前一个单词的尾字母是后一个单词的首字母且每个单词用一次。这可以转化为有向图欧拉路径问题。性能优化我们当前使用的mapint, mapint, int在顶点数很少本题只有52个字母时非常方便。但如果顶点编号范围很大但很稀疏这种结构依然高效。如果顶点编号是连续的整数比如0~N-1使用vectormultisetint或vectormapint, int会更节省内存访问也更快。在DFS中删除边时multiset的erase(iterator)操作是O(1)的比修改map的值再判断删除更直接。最后关于这道题我个人的体会是它像是一个“包装精美”的模板题。你一旦看穿它“无序字母对”的外衣认出里面是“无向图欧拉路径”的骨架剩下的就是套用标准流程并处理好字典序这个细节。在信奥学习中这种化归思想非常重要——将新问题转化为已知的经典模型。多练习这类题目不仅能巩固图论算法更能提升你的问题建模能力。在实现时map套map来存图以自动保证字典序这个小技巧值得记住它在很多需要按特定顺序枚举邻居的场景下都很好用。