如果只是问“这张有向图里有没有环”我相信大多数人都能在一分钟内给出解法拓扑排序或者DFS配一个访问标记。但题目一旦变成“把环上的点按顺序输出”很多人会在同一个地方卡住。“Round Trip II输出有向图的环”就是这样一个看着基础、真动手才发现有细节的问题。我最早做这道题时第一反应是拓扑排序结果排了半天只得到一个“有环”的结论却完全不知道环长什么样回来补了一课才把DFS栈方案彻底吃透。这篇文章就围绕“怎么把有向图中的环真正抓出来并输出”展开覆盖原理、完整代码、边界输入处理和常见的坑适合正在刷图论题、或者工作中需要做环检测与路径还原的读者参考。1. 拓扑排序能判“有环”却给不出“环在哪”1.1 拓扑排序的工作原理与局限拓扑排序的本质是反复删除“当前入度为0”的节点每删一个节点就把它指向的邻居的入度减一。如果最后所有节点都被删掉了那么这个有向图是无环的如果队列提前空了剩下那些节点就是某个环上的节点。问题恰恰出在这里拓扑排序能非常肯定地告诉你“这张图有环”但它从来没有记录“我从哪个点进入这个环环上的顺序是什么”。举个例子图里有三条边1 - 2、2 - 3、3 - 1。三个节点的入度全都是1没有入度为0的起点拓扑排序一开始就无操作算法结束只剩“有环”这个结论。可题目要的是输出“1 2 3”这样的路径拓扑排序里根本没有任何结构能还原这条路径。有人可能会说那我先用拓扑排序把非环节点删掉剩下的节点不就是环吗对剩下的子图确实是环相关节点但如果图和多个环交叠比如两个环共享一段路径剩余子图里就不能直接读出一条干净的环。这个思路用来判断有环没问题用来“输出环”就太绕了。1.2 为什么输出环必须回到DFS输出环真正需要的是一台能记录“递归过程中当前路径”的机器。DFS天然满足这个要求我们从某个节点出发沿邻接边一直往下走边走的顺序就构成了当场的调用栈。如果在这个过程中某个节点的邻接点恰好是调用栈里已经存在的节点那就说明从这个“已经存在”的节点到当前节点之间有一条封闭的回路这正是一个环。同样是1 - 2、2 - 3、3 - 1这个例子DFS从1出发调用栈是[1, 2, 3]在3的邻接表里看到1而此时1就在栈中于是路径[1, 2, 3]就是我们要找的环。所以很多有过实战经验的人都会形成一个习惯题目里出现“任意输出一个环”或者“输出环上一个节点”时不要先想拓扑排序直接上DFS栈记录路径判断和输出一气呵成。这也是Round Trip II和单纯判环题最本质的区别。2. 三色标记法让递归栈变成一台可以回放路径的摄像机2.1 三种状态的含义与设计逻辑DFS过程中每个节点其实会经历三个阶段还没碰到过、正在递归栈中、以及它的所有邻居都已经处理完。这三个阶段正好对应三种标记0白色节点尚未被访问。1灰色节点当前正处在递归调用栈中也就是“正在这条路径上”。2黑色节点的所有邻接分支都已展开完毕确定不会从这里找到新的环标记为“已退役”。有人会问为什么不能用两种状态用一个“已访问过”不是足够吗不够。假设只记录“访问过”当从一个节点u访问邻居v时遇到v已经被访问过我们判断不了v到底在不在当前这个DFS的调用路径上。v可能是一个已经全部处理完的黑色节点也可能是几层递归之前还没返回的灰节点。前者是历史信息后者才是环的证据。所以必须把“正在栈中”和“已经离开栈”分开灰和黑缺一不可。2.2 灰色节点的命中规则三色标记法的核心判断逻辑非常简洁当DFS从u访问邻居v时如果v的状态是白色就正常递归进去如果v的状态是黑色说明这个方向已经被彻底搜过直接跳过如果v的状态是灰色说明v就在当前的递归栈里那从v到u之间的整段路径加上u→v这条边就构成了一个环。这里的关键是“栈中路径和节点的位置关系”。我们需要一个容器保存当前递归栈中的节点顺序比如数组或vector。每进入一个新节点就push_back放到尾部递归返回时就pop_back撤掉。这样当我们在u的表面发现v是灰色时v在容器里的位置就是环的起点下标。从那个下标一直输出到容器末尾自然就是一条从v到u的连续路径而u到v的边又真实存在这一整段就是一个合法环。整个过程相当于一台摄像机把深浅调用全部录下来发现重复片段时直接截取回放给他们看。2.3 没有环时的处理如果整张图搜完都没有出现灰色命中那就说明图是无环的。要注意的是有向图可能是非连通的所以必须从每个尚未访问的节点都启动一次DFS而不是只从一个起点搜。每次新的DFS开始路径容器应该是空的状态数组跨图保留已经确认无环的黑色节点不必再搜。3. 完整实现从邻接表建图到输出环的C与Python代码3.1 C版本邻接表加pos数组下面是我在实际测试中使用的C实现节点编号从1开始假设输入格式是第一行两个整数n和m表示节点数和边数接下来m行每行两个整数a、b表示一条从a到b的有向边。#include bits/stdc.h using namespace std; const int MAXN 200005; vectorint g[MAXN]; int state[MAXN]; // 0未访问, 1灰(递归栈中), 2黑(处理完) int pos[MAXN]; // 记录每个节点在path数组中的下标 vectorint path; // 当前递归栈路径 bool dfs(int u) { state[u] 1; pos[u] path.size(); path.push_back(u); for (int v : g[u]) { if (state[v] 0) { if (dfs(v)) return true; } else if (state[v] 1) { int start pos[v]; cout path.size() - start \n; for (int i start; i (int)path.size(); i) { cout path[i] (i 1 (int)path.size() ? \n : ); } return true; } } path.pop_back(); pos[u] -1; state[u] 2; return false; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; for (int i 0; i m; i) { int a, b; cin a b; g[a].push_back(b); } for (int i 1; i n; i) { if (state[i] 0 dfs(i)) { return 0; } } cout NO CYCLE\n; return 0; }这个代码有几个地方值得说清楚。pos数组是优化重点如果每次发现灰节点都去遍历path找下标最坏情况会多出O(n)的扫描当图规模到20万时这部分开销不小。用pos把“节点→栈中位置”的关系提前记下来命中灰节点时能O(1)拿到起点下标。还要注意path的保存顺序先标记状态和记录位置再检查邻居递归返回时要先pop_back再标记黑色。保持“path尾部永远是当前活跃递归链”这条纪律后面的截取才会正确。3.2 Python版本简洁但注意递归深度很多读题人用Python刷题这里给一份等价实现。考虑到有向图规模可能较大我推荐在系统允许递归深度的情况下使用或者直接把DFS写成显式栈。import sys sys.setrecursionlimit(1 25) n, m map(int, input().split()) g [[] for _ in range(n 1)] for _ in range(m): a, b map(int, input().split()) g[a].append(b) state [0] * (n 1) pos [-1] * (n 1) path [] def dfs(u): state[u] 1 pos[u] len(path) path.append(u) for v in g[u]: if state[v] 0: if dfs(v): return True elif state[v] 1: start pos[v] cycle path[start:] print(len(cycle)) print(*cycle) return True path.pop() pos[u] -1 state[u] 2 return False for i in range(1, n 1): if state[i] 0 and dfs(i): break else: print(NO CYCLE)两种语言的核心逻辑完全一致。我的建议是比赛或工作里如果追求稳健和高性能用C版本如果只是写临时数据处理的脚本Python版本读起来更直观但要注意sys.setrecursionlimit递归层数超过阈值会直接栈溢出。3.3 验证一个稍复杂的实例拿一个非平凡的例子跑一下能加深理解。假设图有5个节点和5条边1 - 22 - 33 - 44 - 22 - 5。从1开始DFS路径会变成[1, 2, 3, 4]在4的邻接表里看到2此时2是灰节点pos[2] 1输出path[1]到path[3]得到的环是“2 3 4”长度3。请注意这里没有输出节点1因为1不在环上它只是通向环的入口路径。这正是“输出环上的点”这个需求里最容易踩的认知偏差很多人以为要从起点开始输出实际上要从环入口开始环路才是完整的。4. 边界输入实测自环、重边、多环和非连通图分别怎么处理4.1 自环长度为一的环到底算不算如果输入存在一条边u - u那么DFS在u的邻居中看到u自己此时u是灰节点且pos[u]正好是当前path的倒数第二个位置输出结果是长度为1的环只包含单个节点u。有些题目把自环视为合法环有些题目明确要求环长度至少为2还有的题目会约定输入中不存在自环。Round Trip II这类题通常默认允许所有有向环但具体到其他变体建议读题时先确认。如果题目不接受长度1的环判断条件可以改成state[v] 1 path.size() - pos[v] 1。不要把条件写在所有地方否则会误伤正常环。4.2 重边不会影响正确性但可能影响统计假如有两条边a - b重复出现DFS第一次遍历到b时b已经入栈第二次再看到b状态不再是灰色除非b还在递归栈中未返回这取决于边的顺序。大多数情况下重边不会造成环的误判因为状态标记是基于节点的不是基于边的。只要我们的目标是“输出一个环”重边可以完全忽略。如果目标是统计环的数量那是另一个更复杂的图论问题不能靠简单的DFS状态判断完成这一点要有预期。4.3 多环并存输出哪个环由搜索顺序决定一张有向图可以同时存在多个环比如1 - 2 - 3 - 1和4 - 5 - 4。DFS从编号1开始搜会先进入左边的环输出“1 2 3”。如果题目只要求输出任意一个环这完全满足。但要注意环与环可能共享节点例如1 - 2 - 3 - 1和2 - 4 - 2。从1出发进入2后DFS会优先沿着2的邻接表展开可能先搜到4再搜到2从而输出“2 4”这个环也可能因邻接表顺序不同先展开3而输出“2 3 1”。因此多环图中“输出哪个环”由邻接表顺序和节点选择的先后顺序决定。如果题目要求输出字典序最小的环需要在找到环后做一步旋转把环的起点调整到最小节点再和其他环比较。绝大多数题目不要求这个但知道这里有差异能避免在调试时困惑。4.4 非连通图外层循环的兜底有向图不一定连通比如节点1、2、3构成一个环节点4、5完全独立。如果只从1开始DFS后两个节点永远不会被访问环就被漏掉了。所以主函数里必须用一个循环从1到n逐个检查state[i] 0再启动DFS。这个循环不是可选项而是标准写法。另一个隐藏问题是启动新一轮DFS时path应该是空的。因为每个起点都会创建一条全新的递归调用链上一轮的路径已经在返回时被pop干净。如果发现自己写的代码里path没有清空多半是回溯逻辑写漏了。4.5 测试大图时的性能观察当n为20万、m为20万时上述C代码实测能在几十毫秒到几百毫秒内完成取决于内存和编译优化。这里有几个关键点邻接表用vector开好避免频繁动态扩容ios::sync_with_stdio(false)和cin.tie(nullptr)可以大幅加快输入pos数组避免在截取环时反复查找。如果n达到百万级别vector邻接表的内存开销会显著上升可以考虑压缩邻接表或者用数组模拟链式前向星。不过对于绝大多数算法题场景20万规模已经是常见上限vector方案已经足够。5. 无向版Round Trip I和有向版的判断差异一个parent引发的血案5.1 无向图的回边陷阱无向图找环和有向图找环表面上看都是DFS加状态标记实际判断条件差一个关键参数。无向图里当我们从节点u走到邻居v时v可能刚刚是从自己这个方向走过来的父节点。比如图里只有一条无向边1——2DFS从1进入22的邻居里有1而1此时是灰节点。如果照搬有向图的逻辑看到灰节点就输出环那么这条根本不构成环的边会被误判成一个长度为2的“假环”。所以无向图的DFS必须额外记录当前节点的父节点判断环的条件要写成state[v] 1 v ! parent。5.2 有向图为什么不需要parent判断在有向图中边是有方向的。u到v有边不代表v到u就必然存在边。当我们从u开始DFS通过边u - v进入v时v的邻接表里就算有一个指向u的边那也只是正常的有向回边说明确实构成了一个有向环路。DFS不需要知道v是谁带入的只需要关心v是否已经在当前递归栈中。这一点正是两个版本最核心的差异。5.3 把无向图逻辑强行套到有向图会发生什么我见过不止一个人把无向图的parent判断直接搬进有向图版本结果明明有环却检测不到。举个具体例子三条边1 - 2、2 - 1、1 - 3。从1进入22的邻接表里有1因为1是父节点条件v ! parent把它跳过这个长度为2的环就被漏掉了。反向操作同样危险把有向图的逻辑直接用于无向图会把平凡的无向边误判成环。因此拿到题先明确图的方向性再写判断条件这个坑能避免很多无意义的调试时间。6. 再次踩坑后的经验小结与进阶方向6.1 每次都会有人踩的五个细节汇总一下我反复遇到过的错误按频率排序忘记外层循环遍历所有节点导致非连通图漏环。回溯时只把节点标记为黑忘记从path中pop破坏了“path尾部是当前递归栈”的不变式。图规模较大时用遍历path的方式找环起点造成不必要的O(n)开销。自环和长度2的环没有根据题目要求做过滤输出后被判错。对无向图和有向图使用了同一套判断逻辑得出完全错误的结论。这些问题都不难修但它们很容易在紧张编码时集体爆发。我自己的习惯是把模板写好先在小图上手动验证一次再跑随机图对比一个暴力解法的结果确认无问题后再提交。6.2 输出环场景的进阶方向如果题目进一步要求“输出所有环”或“输出最小环”单纯靠DFS栈就不够用了。输出所有环理论上可以用回溯枚举但环数量可能是指数级的实际中很少这么干通常需要借助强连通分量先把图缩成DAG再在每个强连通分量内部做进一步分析。最小环则可以考虑从每个点出发跑BFS找回到自身的最短路径或用Floyd算法的变种。这些都属于延伸内容核心基础仍然是“如何在DFS路径里识别并截取一个环”。把这套三色标记法彻底弄熟再去看这些变体思路会顺畅很多。6.3 一点个人体会Round Trip II这类题目之所以经典是因为它把图论里两个常见概念——判环和记录路径——放在了一起。算法竞赛和实际工程里很多问题表面是“找环”骨子里是“还原过程”。我后来做依赖关系分析、死锁检测之类的任务时也经常用这套DFS栈思路不仅要告诉用户系统里有循环依赖还要把循环依赖链一条条打出来。三色标记法那条“灰节点命中即环相遇”的经验在这些场景里依然有效。养成先明确要的是“结论”还是“路径”的习惯再决定用拓扑排序还是DFS栈能帮你少走很多弯路。