如果只是问“这张有向图里有没有环”，我相信大多数人都能在一分钟内给出解法：拓扑排序，或者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; vector<int> g[MAXN]; int state[MAXN]; // 0=未访问, 1=灰(递归栈中), 2=黑(处理完) int pos[MAXN]; // 记录每个节点在path数组中的下标 vector<int> 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 -> 2，2 -> 3，3 -> 4，4 -> 2，2 -> 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——2，DFS从1进入2，2的邻居里有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进入2，2的邻接表里有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栈，能帮你少走很多弯路。