刚看到“Play on Words”第一反应是单词接龙第二反应是暴力全排列。POJ 1386 这道题新手和老手之间只差一层窗户纸你是不是把它当成字符串题来做。如果你肯停下来把每个单词看成一个零件问题其实清爽得很——这是一张有向图在问你能不能一笔画完所有边也就是经典的欧拉路径判定。我第一次做这题时老老实实枚举排列n 稍微大一点就超时脸上挂不住。后来才明白这类“能不能把所有东西串成一条链”的题十有八九都在考图论建模和并查集。这篇文章就把这道题的完整思路、判定条件、并查集实现、调试经验一次讲透。你如果刚学图论、准备算法竞赛或者想复习欧拉路径这篇应该对你有用。1. 项目概述与问题建模1.1 题目到底在问什么给你 n 个单词问能不能把它们排成一个序列使得序列中每个单词的最后一个字母等于下一个单词的第一个字母。注意要求是用完所有单词且每个单词只能用一次。比如acm、malform、mouse这三个单词acm结尾是 mmalform开头是 mmalform结尾又是 mmouse开头也是 m所以它们可以排成acm - malform - mouse。这题就是给你一堆单词让你回答“行”还是“不行”。很多人第一反应是 DFS 搜索排列顺序或者直接全排列枚举。这思路在 n 等于 5、6 的时候还行数据一大就崩。POJ 1386 的 n 可以到十万级别排列数量是 n 的阶乘想都不用想。所以必须换一个视角把问题从“排列单词”转成“图上的路径”。1.2 把单词抽象成一张有向图关键转化是这样每个单词看成一条有向边边从首字母指向尾字母。点就是 26 个字母中实际出现过的那些。举个例子acm这个单词就是一条从 a 指向 m 的边。mouse就是一条从 m 指向 e 的边。那一堆单词合在一起就得到一张有向图顶点是最多 26 个字母边数是 n。为什么要这么转化因为在单词接龙里两个单词能不能相邻只取决于前一个的尾字母和后一个的首字母。想一想如果单词 A 的尾字母是 x单词 B 的首字母也是 x那么在图上A 这条边指向 xB 这条边从 x 出发两条边在顶点 x 处首尾相接。这不就是在图里沿着边往下走吗所以“把所有单词排成一串”等价于“在图上找一条路径把每条边恰好走一遍”。每条边恰好走一遍因为每个单词只能用一次路径可以经过同一个顶点多次因为字母可以重复出现。1.3 欧拉路径这里的主角图论里有个专门的名字经过每条边恰好一次的路径叫欧拉路径。如果路径最后回到起点连成一个圈就叫欧拉回路。题目没有要求回到起点所以欧拉路径和欧拉回路都算成立。判断一张有向图是否存在欧拉路径有非常成熟的数学条件不需要真的去搜路径。这个条件分两块一是所有顶点的入度出度之间的平衡关系二是图的底图连通性。这块我放在下一章详细说因为很多人栽就栽在只记条件、不理解条件最后边界情况一出来就错。这里先记住建模结论就好26 个字母是顶点单词是边判断欧拉路径是否存在。2. 核心算法原理欧拉路径判定的两层逻辑2.1 度数条件为什么入度必须等于出度想象你手里拿着一支笔在一张有向图上画欧拉路径。从起点出发画第一条边到达某个顶点如果不巧这个顶点就是终点那你的路径到此结束。除了终点以外每当你进入一个顶点你必须还能从它这里出去否则就卡死了。因为路径中每经过一个非起终点顶点都是“从一条边进来再从一条边出去”所以进入次数和出去次数必须相等。A 进入次数就是入度 in[u]出去次数就是出度 out[u]。所以对非起终点必须有 in[u] out[u]。那么起点和终点呢起点是第一步出发的地方它的出度会比入度多 1因为多出来那一次“出去”没有对应的“进来”。终点反过来入度比出度多 1。把这两个特例放进整个图来看就有两种情况是合法的。存在欧拉回路的情况所有顶点都满足 in[u] out[u]起点和终点是同一个点所以没有出度比入度多 1 的点。存在欧拉路径但不是回路的情况恰好有一个顶点满足出度 - 入度 1这就是起点恰好有一个顶点满足入度 - 出度 1这就是终点其余顶点全部出入相等。所以判断度数条件时我会写一个循环统计每个出现过的字母的出度入度差值 diff。如果 diff 全部是 0或者正好有一个 1 和一个 -1其他都是 0度数条件就满足。这里要特别小心diff 的绝对值大于 1 的情况绝对不能忽略。比如两条ab、aba 点出度是 2、入度是 0diff 是 2而不是 1。这种情况虽然有“出度比入度多”的顶点但它不是合法起点根本无法一笔画。有些人只统计出度大于入度的点数和入度大于出度的点数不看差值具体多大这就会漏判。2.2 连通性条件为什么要用“弱连通”度数条件过了图就一定存在欧拉路径吗不是。举个反例图里有 A、B、C、D 四个顶点边是 A-B、B-A 和 C-D、D-C各自围成一个环。所有顶点出入度都相等度数条件完美满足但你能从第一个环走到第二个环吗不能因为两个环之间没有任何边相连。所以光是度数平衡不够还要保证整张图是一个整体这个“整体”指的是底图连通。底图是什么就是把有向边上的方向全部忽略只看顶点之间有没有边连着。在无向意义下所有出现过字母的顶点必须连通这叫弱连通。为什么是弱连通而不是强连通举个例子边 A-B这个图里 A 到 B 可达但 B 到 A 不可达它不是强连通的但它显然是合法欧拉路径。所以强连通的要求太强了不需要。为什么弱连通加上度数条件就足够直观地说度数条件保证了路径不会走进死胡同除了终点每个顶点被进入多少次就一定能出去多少次。弱连通保证所有边都长在同一片区域里。两边一凑就能从度数为 1 的起点出发沿着合法的方向走最终把所有边走完。理解充分性有个更形象的办法先把起点到终点那条主线走一遍如果还有没走过的边就说明某个经过的顶点还有没走的边。因为那个顶点出入度平衡你可以从它出发走一个环回到它再继续原来的路径。这个过程叫回退拼接是 Hierholzer 算法的基础。条件满足时这个拼接一定能成功所以判定条件既是必要的也是充分的。2.3 边界情况最容易翻车的地方先说只有一个单词的情况。比如ok只有单独一条边 o-k显然能排输出可行。在图论模型里o 点出度 1 入度 0k 点入度 1 出度 0恰好一个 1 一个 -1底图连通判定合法没问题。再说自环。单词aa自环 a-a出度入度都加 1两边平衡底图就一个点连通可行。它表示单词aa自己就能作为序列而且如果是多个aa也可以一直排列aa的尾字母 a 正好接下一个aa的头字母 a。还要小心完全没出现过的字母。比如只有 b 和 c 相关的单词a 从来没出现过。这时并查集里有 26 个点但只有那两三个字母是真正参与的。判断连通时如果默认拿 a 做基准就会把本来合法的图误判成不连通。所以一定要用 used 数组标记哪个字母出现过遍历时跳过没出现过的字母。3. 工具选型与代码实现并查集实战3.1 为什么选并查集而不是 DFS 判连通判断弱连通有两种常规做法一种是建邻接表或无向化处理然后从某个出现过的字母出发做 DFS/BFS看能不能访问到所有出现过的字母另一种是并查集。两种都能过我推荐并查集原因有三个。第一代码短不容易出幺蛾子。第二这题顶点只有 26 个但思路可以平移到任意规模并查集在稀疏图上效率很高路径压缩后单次操作接近 O(1)整道题复杂度只有 O(n α(n))n 是十万也没压力。第三并查集天然适合“多组端点是否属于同一连通块”的查询很多图论题里都能复用值得当成基础组件刻进肌肉记忆。3.2 并查集三件套初始化、查找、合并完整代码前先看标准的三个函数模板。注意这题顶点是 26 个字母我用 0 到 25 表示 a 到 z。int fa[26]; int find(int x) { return fa[x] x ? x : (fa[x] find(fa[x])); } void unite(int x, int y) { x find(x); y find(y); if (x ! y) fa[x] y; }find 里那个三元表达式就是在做路径压缩查找 x 的根时顺手把沿途每个点的父节点直接指向根下次再查就快很多。初始化要记得让每个 fa[i] i表示一开始每个点都是自己的连通分量的根。unite 负责合并两个点所在的连通块先找根如果根不同就合并。3.3 完整可提交代码下面给出这道题可以完整提交的代码。风格偏保守用的都是 C98 就支持的语法在 POJ 这类老 OJ 上不会踩新标准的坑。输入的单词我用 char 数组临时收用 strlen 取长度因为只需要首字母和尾字母整个单词内容其实不用存。#include cstdio #include cstring const int MAXN 26; int fa[MAXN]; int in[MAXN], out[MAXN], used[MAXN]; int find(int x) { return fa[x] x ? x : (fa[x] find(fa[x])); } void unite(int x, int y) { x find(x); y find(y); if (x ! y) fa[x] y; } int main() { int T; scanf(%d, T); while (T--) { int n; scanf(%d, n); memset(in, 0, sizeof(in)); memset(out, 0, sizeof(out)); memset(used, 0, sizeof(used)); for (int i 0; i 26; i) fa[i] i; char word[1005]; for (int i 0; i n; i) { scanf(%s, word); int len strlen(word); int u word[0] - a; int v word[len - 1] - a; out[u]; in[v]; used[u] used[v] 1; unite(u, v); } int startCnt 0, endCnt 0; bool degreeOk true; for (int i 0; i 26; i) { if (!used[i]) continue; int diff out[i] - in[i]; if (diff 1) startCnt; else if (diff -1) endCnt; else if (diff ! 0) degreeOk false; } if (!((startCnt 0 endCnt 0) || (startCnt 1 endCnt 1))) { degreeOk false; } int root -1; bool connected true; for (int i 0; i 26; i) { if (!used[i]) continue; int r find(i); if (root -1) root r; else if (r ! root) { connected false; break; } } if (degreeOk connected) { printf(Ordering is possible.\n); } else { printf(The door cannot be opened.\n); } } return 0; }3.4 关键行代码解读上面的代码有四个细节必须看懂不然下次自己写还是会错。第一个细节是used[u] used[v] 1。为什么必须有这行并查集初始化时 26 个点都是独立根如果不标记哪些字母出现过后面判断连通时会拿一堆从未出现在单词里的字母当“孤立点”导致本来连通的图被判成不连通。标记之后统计和判连通都只关注出现过的字母。第二个细节是度数循环里的continue。跳过未出现字母之后对出现过的字母计算dif out[i] - in[i]。等于 1 记作起点等于 -1 记作终点等于 0 是正常点如果出现其他值如 2、-3直接判degreeOk false。这样就把我前面强调的“差值大于 1”的情况拦住了。第三个细节是最后连通性判断。我取第一个出现过的字母的根作为基准之后每个出现过的字母的根必须和它一样。有人喜欢把root初始化成find(0)这其实是挖坑因为 0 号字母 a 可能从来没出现过它自成连通块会导致所有图都判不连通。第四个细节是输出。题目要求严格区分两种输出多一个空格少一个句点都会 WA。写代码时最好直接复制题面的句子保持大小写和句号。4. 实操过程与核心细节4.1 构造一组样例完整推演自己学算法题目光看别人代码远不够我建议拿几组数据手动跑一遍。下面是我常用的四组数据覆盖了多种情况。4 2 acm ibm 2 ab ab 1 aa 3 acm malform mouse第一组有两个单词acm对应边 a-mibm对应边 i-m。统计一下a 点 out1、in0i 点 out1、in0m 点 out0、in2。三个出现字母的 diff 分别是 1、1、-2。这里出现了两个 1 却没有对应的 -1所以度数条件直接不满足。这组数据肉眼也能看出来acm尾字母是 mibm首字母是 i 而不是 m不可能直接接上。答案应该是The door cannot be opened.。第二组两条完全相同的ab边。a 点 out2、in0b 点 out0、in2。diff 分别是 2 和 -2绝对值超过 1非法。这组数据是专门用来检验你有没有检查 diff 绝对值的。很多人只判断起点终点个数看见“有出度大的点也有入度大的点”就放行结果 WA 得莫名其妙。第三组只有一个aa自环。a 点 out1、in1diff0全部顶点出入平衡属于欧拉回路情况可行。输出Ordering is possible.。第四组是acm、malform、mouse。边是 a-m、m-m、m-e。度数分布是a out1 in0e out0 in1m out2 in2。出现一个 1 一个 -1其余平衡度数条件满足。底图里 a、m、e 三个点都在同一个连通块里所以最终判定可行。4.2 把判定过程组装成检查表我在实战时会把欧拉路径判定顺序固定成一张检查表每一步做完再进下一步。建图每读一个单词取出首字母 u 和尾字母 v让 out[u] 加一in[v] 加一合并 u、v标记 used。度数检查遍历 26 个字母只处理 used 的点。统计 diff 等于 1 的起点数量等于 -1 的终点数量。如果出现绝对值大于 1 的 diff直接判死。汇总检查合法情况只有两种一是起点数终点数都是 0二是都是 1。否则判死。连通性检查遍历 used 的点所有点必须在同一个并查集根下。两个条件同时满足才输出可行否则输出不可行。这个顺序不要乱。先判度数可以提前退场省掉一些无谓的并查集查询。实际代码里因为整体复杂度极低顺序影响不大但按这个顺序思考逻辑更顺。4.3 易错点清单代码层面容易踩的坑第一多组数据之间必须重置所有全局数组。in、out、used都要清空fa要重新初始化。有些同学只在开头初始化一次第二组数据就全乱了。我一直习惯在 while 循环开头一次性memset加初始化 fa。第二读入单词时注意数组长度。POJ 这题单词长度好像不会特别夸张但稳妥起见开 1005 或者更大别开个 50 就硬怼。用scanf(%s, word)读入省去处理行尾换行符的麻烦。如果开char word[1005]%s会自动补终止符strlen不会越界。第三建边时别把方向写反。单词是“第一个字母指向最后一个字母”所以 u 是首字母v 是尾字母。如果你把out[v]、in[u]那整张图的方向就全反了在一些对称数据上可能碰巧没错但只要有个非对称例子就会 WA。第四使用find后要小心路径压缩对后面判断的影响。并查集合并完之后某些点的父节点不是根所以判断连通性前最好都调一次find(i)确保拿到的是压缩后的根。我的代码里就是这么做的。5. 常见问题与排查记录5.1 问题速查表我在带人的时候发现下面几个问题出现频率特别高。整理成表方便你照着排查。现象可能原因解决办法样例过不了输出全是 The door cannot be opened度数条件中把未出现字母也算进去或 diff 绝对值大于 1 没被拒绝用 used 过滤增加 else if (diff ! 0) 分支明明能接上的数据却判不行并查集根比较拿未出现字母当基准通常是用 0 号节点做 root取第一个 used 字母的根做基准多个单词两个互不相连的环程序说可行只判了度数没判连通性补并查集连通性检查单个单词输出正确但多组数据有问题数组没在每组数据开头清空memset 和 fa 初始化移到 while 循环内用 WIndows 或老编译器出现编译错误代码用了 C11 特性比如 int i{}、autoPOJ 这种老 OJ 建议用纯 C98 风格运行时间不稳定用了 cin/cout 且没有加解绑语句换 scanf/printf5.2 自测数据生成与暴力对拍如果你不确定自己的判定程序对不对最靠谱的办法是写一个暴力程序对拍。思路很简单n 很小的时候把 n 个单词做全排列检查是否存在一个排列满足相邻项尾首相接。这个暴力解法复杂度是 O(n! * n)只能在 n 最多 8、9 时跑但拿来验证欧拉路径程序完全够用。我实际做法是写个小脚本随机生成一堆长度 3 到 6 的小写单词n 取 1 到 8同时喂给暴力程序和欧拉路径程序比较两组输出。如果出现不一致就用那组数据人工分析。这个方法帮我抓到过好几次细微的方向错误。对拍脚本写起来不复杂核心就一段输入 n 和 n 个单词 生成 0 到 n-1 的全排列 对每个排列检查相邻两个单词是否 尾字母 首字母 存在一个满足就输出 possible否则 impossible5.3 一条真实的调试线索我记得自己最初写这道题时连度数条件都写对了但漏了连通性检查。当时我拿一组数据测试图是两个分开的环A 环 3 个顶点 3 条边B 环也是 3 个顶点 3 条边所有顶点出入度全相等程序输出Ordering is possible.。我盯着屏幕觉得不对因为单词接龙根本不可能从一个环跑到另一个环。打印出并查集结果后才发现两个环根本不在同一个根下面。后来在判定里加上连通性检查这组数据才正确输出不可行。这个案例我一直记着因为它完美展示了“必要条件凑一起就是充分条件”这个数学结论在代码里要如何落实两个条件少一个都不行。6. 从这题延伸出去6.1 几种经典变式欧拉路径的考法远不止这一种。最常见的是无向图一笔画判断一个无向图能不能不重复地走完所有边条件是奇度点的数量必须是 0 或 2。如果是 0说明存在欧拉回路随便从哪个点出发都行如果是 2必须从一个奇度点出发走到另一个奇度点结束。这种题在地图类游戏、迷宫路径规划里很常见。另一种变式是要求输出具体方案而不是只回答能不能。这时候要用到 Hierholzer 算法从一个起点出发深搜把走过的边删掉当某个点无路可走时就把这段路倒着放进答案栈最后栈里就是一条欧拉路径。如果还要求字典序最小就先把邻接表按字典序排序再按排序后的顺序做遍历。很多 OJ 上的“输出欧拉回路”题都可以套这个模板。还有一种变式是有向图加上了点权或边权让路径上的累计值最大化或最小化。这类题经常伪装成动态规划但底子还是欧拉路径的连通性和度数条件。遇到时先检查能否走通再考虑最优化。6.2 欧拉路径的现实场景别觉得欧拉路径只是竞赛题。字符串拼接问题在代码里很常见比如把碎片拼回完整文本、把一批短序列合并成一条长链都可以建模成“找一条路径经过所有边”。DNA 测序里有一类组装算法叫 de Bruijn 图方法核心就是先把测序片段切成固定长度的 k-mer每个 k-mer 作为边然后在这个图上找欧拉路径拼出完整序列。我在业务里也遇到过类似需求把一批带首尾关联的数据记录串成完整日志链当时第一反应就是我在这题里练熟的建模思路。电路板上的布线、清扫机器人的路径规划本质上也在找一种“每条路都要走且尽量少重复”的走法。6.3 从这题带走的三个习惯做完这题我最想提醒你的是三件事。第一看到“排列所有元素”先别急着枚举看看能不能把元素抽象成边或点。字符串、关系对、依赖链都很适合图论建模。第二图论题的判定条件要“成对”记忆。欧拉路径是“度数条件 连通条件”缺一个都不成立。第三并查集这类基础数据结构要滚瓜烂熟写起来不用过脑子。我后来遇到很多题第一步建模建完第二步就是并查集判连通。把这三件事练成本能比背模板有用得多。最后分享一个小技巧做欧拉路径题时我会顺手画思维导图式的检查表边画边在代码里对照。先问自己图的点是谁、边是谁再问走的方向是否重要然后列度数最后查连通。这个流程走的次数多了以后遇到任何“能不能串起来”的题都能十秒定方案。
