题目来源：参考 LeetCode 207：课程表进行课程化改编。原题的先修关系
[a, b]表示有向边b → a，并在无环、可以完成课程时返回true；本 Lab 直接输入边u → v，并在存在有向环时输出YES，判定语义相反。
学习目标
前置知识
完成前建议先阅读第 7.1 节 图的遍历：DFS 与 BFS的"DFS 边分类"小节。你需要准备支持 C++17 的编译器；可先运行 make doctor 检查环境。
题目
给定一个含 n 个顶点和 m 条有向边的图，判断其中是否存在有向环。只有当一条边指向当前 DFS 递归栈中的顶点时，才能据此确认有环；指向已经完成的顶点并不能说明有环。自环 u → u 本身就是长度为 1 的有向环。
输入格式
第一行包含两个整数 n m，分别表示顶点数和有向边数。顶点编号为 0 到 n-1。
接下来 m 行，每行包含两个整数 u v，表示一条从 u 指向 v 的有向边。输入保证：
1 <= n <= 10000；0 <= m <= 100000；0 <= u, v < n；- 允许自环（
u == v），不包含重复边； - 图不保证弱连通：必须按编号从
0到n-1依次对未访问顶点启动 DFS，避免漏掉其他弱连通分量中的环。
本题只输出是否存在环，判定结果与出边访问顺序无关，因此无需排序出边列表。
输出格式
输出一行，仅包含 YES 或 NO：
- 若图中存在至少一个有向环，输出
YES； - 否则（图是 DAG，即无环有向图），输出
NO。
样例输入
3 3
0 1
1 2
2 0样例输出
YES任务
- 读入有向图并构建出边邻接表；
- 从
0号顶点开始，依次对未访问顶点启动 DFS； - 顶点有三种状态：
0未访问、1已发现但仍在当前递归栈中、2已完成； - DFS 检查出边时，若指向状态
1的顶点，说明存在后向边，图中含环； - 找到环后即可停止并输出
YES，否则遍历完整森林后输出NO。
为什么只用 visited 不够
有向图中，一条指向“已访问过”顶点的边可能指向当前递归栈中的顶点，也可能指向已经完成的顶点。前者是后向边并能证明存在有向环；后者可能是前向边或交叉边，不能单独证明有环。三色状态负责区分这两种判定所需的情况。
正常、边界与错误情况
| 情况 | 预期行为 |
|---|---|
| 含环图 | 后向边出现，输出 YES |
| DAG（无环） | 全程无后向边，输出 NO |
| 自环 | 指向自身的边即是后向边，输出 YES |
| 单顶点无边 | 无任何边，输出 NO |
| 多分量部分含环 | 任一分量发现环即输出 YES |
| 前向边或交叉边场景 | 指向已完成顶点的边不判环，输出 NO |
运行与评分
在本 Lab 目录执行：
make doctor
make run
make run CASE=001-sample
make score未安装 Make 时，在仓库根目录执行：
pnpm lab:doctor -- labs/chapter-07/exercise/E-07-03-directed-cycle-detection
pnpm lab:run -- labs/chapter-07/exercise/E-07-03-directed-cycle-detection
pnpm lab:score -- labs/chapter-07/exercise/E-07-03-directed-cycle-detection完成清单
复杂度分析
每个顶点进入一次、每条出边扫描一次，且不需要排序邻接表，时间为 O(n + m)；状态数组与邻接表共占 O(n + m) 空间，递归栈最坏深度为 O(n)。递归可用深度取决于系统与编译器；本题测试规模按课程工具链验证，超深图应改用显式栈。
思考与复盘
- 无向图判环为什么只需要"已访问且不是父顶点"？有向图为什么不行？
查看参考答案
无向边以两个方向出现，DFS 从 u 到 v 后会看到指回父顶点的边，因此要排除父边；有向图没有对称父边，指向已完成顶点的边可能只是前向或交叉边，必须识别递归栈状态 1。
- 把 DFS 森林的四类边（树边/后向边/前向边/交叉边）写下来，指出本题测试数据
1→2, 2→3, 1→4, 4→2中每条边的类型，并说明4→2为什么不是后向边。
查看参考答案
按给定顺序，1→2、2→3、1→4 是树边；访问 4 时顶点 2 已完成，且不是 4 的祖先或后代，因此 4→2 是交叉边。后向边必须指向当前递归栈中的祖先。
- 若图中只有前向边和交叉边，一定无环吗？依据是什么？
查看参考答案
是。DFS 中能直接证明有向环的是后向边；没有后向边就不存在回到递归栈祖先的闭路，因此图为 DAG。
- 深链 DAG 上递归会占多深？如何用 07-08 的显式栈改写成非递归版本？
查看参考答案
长度为 n 的链产生 O(n) 递归深度，可能栈溢出。显式栈保存“顶点 + 下一个邻居下标”的帧，逐个推进邻居并在处理完后弹栈即可保持 DFS 顺序。