POJ 1386 单词接龙：有向图欧拉路径判定与并查集实现

刚看到“Play on Words”，第一反应是单词接龙，第二反应是暴力全排列。POJ 1386 这道题，新手和老手之间只差一层窗户纸：你是不是把它当成字符串题来做。如果你肯停下来把每个单词看成一个零件，问题其实清爽得很——这是一张有向图在问你能不能一笔画完所有边，也就是经典的欧拉路径判定。我第一次做这题时老老实实枚举排列，n 稍微大一点就超时，脸上挂不住。后来才明白，这类“能不能把所有东西串成一条链”的题，十有八九都在考图论建模和并查集。这篇文章就把这道题的完整思路、判定条件、并查集实现、调试经验一次讲透。你如果刚学图论、准备算法竞赛，或者想复习欧拉路径，这篇应该对你有用。

1. 项目概述与问题建模

1.1 题目到底在问什么

给你 n 个单词，问能不能把它们排成一个序列，使得序列中每个单词的最后一个字母，等于下一个单词的第一个字母。注意要求是用完所有单词，且每个单词只能用一次。比如acm、malform、mouse这三个单词，acm结尾是 m，malform开头是 m；malform结尾又是 m，mouse开头也是 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 这条边指向 x，B 这条边从 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、ab，a 点出度是 2、入度是 0，diff 是 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 入度 0，k 点入度 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 完整可提交代码

下面给出这道题可以完整提交的代码。风格偏保守，用的都是 C++98 就支持的语法，在 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->m，ibm对应边 i->m。统计一下，a 点 out=1、in=0，i 点 out=1、in=0，m 点 out=0、in=2。三个出现字母的 diff 分别是 1、1、-2。这里出现了两个 +1 却没有对应的 -1，所以度数条件直接不满足。这组数据肉眼也能看出来，acm尾字母是 m，ibm首字母是 i 而不是 m，不可能直接接上。答案应该是The door cannot be opened.。

第二组两条完全相同的ab边。a 点 out=2、in=0，b 点 out=0、in=2。diff 分别是 2 和 -2，绝对值超过 1，非法。这组数据是专门用来检验你有没有检查 diff 绝对值的。很多人只判断起点终点个数，看见“有出度大的点也有入度大的点”就放行，结果 WA 得莫名其妙。

第三组只有一个aa，自环。a 点 out=1、in=1，diff=0，全部顶点出入平衡，属于欧拉回路情况，可行。输出Ordering is possible.。

第四组是acm、malform、mouse。边是 a->m、m->m、m->e。度数分布是：a out=1 in=0，e out=0 in=1，m out=2 in=2。出现一个 +1 一个 -1，其余平衡，度数条件满足。底图里 a、m、e 三个点都在同一个连通块里，所以最终判定可行。

4.2 把判定过程组装成检查表

我在实战时会把欧拉路径判定顺序固定成一张检查表，每一步做完再进下一步。

1. 建图：每读一个单词，取出首字母 u 和尾字母 v，让 out[u] 加一，in[v] 加一，合并 u、v，标记 used。
2. 度数检查：遍历 26 个字母，只处理 used 的点。统计 diff 等于 1 的起点数量，等于 -1 的终点数量。如果出现绝对值大于 1 的 diff，直接判死。
3. 汇总检查：合法情况只有两种，一是起点数终点数都是 0，二是都是 1。否则判死。
4. 连通性检查：遍历 used 的点，所有点必须在同一个并查集根下。
5. 两个条件同时满足才输出可行，否则输出不可行。

这个顺序不要乱。先判度数可以提前退场，省掉一些无谓的并查集查询。实际代码里因为整体复杂度极低，顺序影响不大，但按这个顺序思考逻辑更顺。

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 问题速查表

我在带人的时候发现，下面几个问题出现频率特别高。整理成表，方便你照着排查。

5.2 自测数据生成与暴力对拍

如果你不确定自己的判定程序对不对，最靠谱的办法是写一个暴力程序对拍。思路很简单：n 很小的时候，把 n 个单词做全排列，检查是否存在一个排列满足相邻项尾首相接。这个暴力解法复杂度是 O(n! * n)，只能在 n 最多 8、9 时跑，但拿来验证欧拉路径程序完全够用。

我实际做法是写个小脚本，随机生成一堆长度 3 到 6 的小写单词，n 取 1 到 8，同时喂给暴力程序和欧拉路径程序，比较两组输出。如果出现不一致，就用那组数据人工分析。这个方法帮我抓到过好几次细微的方向错误。对拍脚本写起来不复杂，核心就一段：

输入 n 和 n 个单词 生成 0 到 n-1 的全排列 对每个排列，检查相邻两个单词是否 尾字母 == 首字母 存在一个满足就输出 possible，否则 impossible

5.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 从这题带走的三个习惯

做完这题，我最想提醒你的是三件事。第一，看到“排列所有元素”先别急着枚举，看看能不能把元素抽象成边或点。字符串、关系对、依赖链，都很适合图论建模。第二，图论题的判定条件要“成对”记忆。欧拉路径是“度数条件 + 连通条件”，缺一个都不成立。第三，并查集这类基础数据结构要滚瓜烂熟，写起来不用过脑子。我后来遇到很多题，第一步建模建完，第二步就是并查集判连通。把这三件事练成本能，比背模板有用得多。

最后分享一个小技巧：做欧拉路径题时，我会顺手画思维导图式的检查表，边画边在代码里对照。先问自己图的点是谁、边是谁，再问走的方向是否重要，然后列度数，最后查连通。这个流程走的次数多了，以后遇到任何“能不能串起来”的题，都能十秒定方案。