题目来源：课程经典 DFS 时间戳练习；发现时间、完成时间与括号化定理的定义参考 CLRS《Introduction to Algorithms》第 22 章。本 Lab 使用固定扫描顺序与独立测试，没有直接对应的 LeetCode 原题。
学习目标
前置知识
完成前建议先阅读第 7.1 节 图的遍历：DFS 与 BFS的"DFS 时间戳与括号化定理"小节。你需要准备支持 C++17 的编译器；可先运行 make doctor 检查环境。
题目
给定一个可能不连通的无向图。按顶点编号从小到大建立完整 DFS 森林，并在第一次进入顶点时记录发现时间、处理完全部邻居即将返回时记录完成时间。为了让输出唯一，邻居也按编号升序访问。请输出每个顶点的发现时间和完成时间。
输入格式
第一行包含两个整数 n m，分别表示顶点数和无向边数。顶点编号为 0 到 n-1。
接下来 m 行，每行包含两个整数 u v，表示一条无向边。输入保证：
1 <= n <= 10000；0 <= m <= 100000；0 <= u, v < n；- 不包含自环和重复边；
- 图不保证连通：必须按编号从
0到n-1依次对尚未访问的顶点启动 DFS，构造覆盖全部顶点的完整 DFS 森林。
为保证结果唯一，每个顶点的邻居必须按编号升序访问（读入后对邻接表排序即可）。
输出格式
输出两行：
- 第一行包含
n个整数：d[0] d[1] ... d[n-1]，其中d[u]是顶点u的发现时间（进入递归时记录）； - 第二行包含
n个整数：f[0] f[1] ... f[n-1]，其中f[u]是顶点u的完成时间（所有邻居处理完、即将返回时记录）。
完整 DFS 森林中，时间戳使用 1 到 2n，每个顶点恰好分到一个发现时间和一个完成时间。相邻整数之间用单个空格隔开，行末无空格。
样例输入
5 4
1 3
0 1
1 4
0 2样例输出
1 2 8 3 5
10 7 9 4 6任务
- 读入无向图，把每条边写入两个顶点的邻接表，并升序排序；
- 从
0号顶点开始，依次对未访问顶点调用递归dfs(v)； - 进入
dfs(u)时记录d[u] = ++timer，返回前记录f[u] = ++timer； - 输出两行时间戳数组。
正常、边界与错误情况
| 情况 | 预期行为 |
|---|---|
| 连通图 | 从 0 号顶点一次 DFS 覆盖全图，时间戳区间嵌套 |
| 非连通图 | 对每个未访问顶点依次启动 DFS，2n 个时间戳全部填满 |
| 单顶点图 | d[0] = 1，f[0] = 2 |
编号依次为 0-1-...-n-1 的链 | 发现时间沿链递增、完成时间沿链递减，递归深度等于链长 |
以 0 为中心的星形图 | 中心先发现，叶子按编号升序依次发现并完成 |
| 含环图 | 已访问标记阻止重复访问，不产生死循环 |
运行与评分
在本 Lab 目录执行：
make doctor
make run
make run CASE=001-sample
make score未安装 Make 时，在仓库根目录执行：
pnpm lab:doctor -- labs/chapter-07/exercise/E-07-01-dfs-timestamps
pnpm lab:run -- labs/chapter-07/exercise/E-07-01-dfs-timestamps
pnpm lab:score -- labs/chapter-07/exercise/E-07-01-dfs-timestamps完成清单
复杂度分析
为了固定访问顺序，排序全部邻接表需要 O(Σ deg(u) log deg(u)) 时间，上界可写为 O(m log n)。排序完成后，每个顶点进入一次，邻接表中的每条记录扫描一次，也就是每条无向边分别从两个方向扫描，DFS 本身为 O(n + m)；因此包含排序的总时间为 O(n + m log n)。
邻接表占 O(n + m) 空间，visited、时间戳数组与最坏递归栈各占 O(n) 空间。递归可用深度取决于操作系统、编译器和栈帧大小；本题测试规模控制在课程工具链可验证范围，更深的图请参考 07-08 的显式栈实现。
思考与复盘
- 在非连通图上只从
0出发跑一次 DFS，后面分量的时间戳会变成什么？
查看参考答案
后续分量不会被访问，d/f 保持未初始化或占位值，无法形成完整的 1..2n 时间序列；必须按编号扫描所有顶点并为每个未访问顶点启动新的 DFS。
- 为什么只有
d[u] < d[v] < f[v] < f[u]才能说明u是v的祖先，而单独比较f[u] > f[v]不够？
查看参考答案
祖先关系要求 u 先发现、v 在 u 完成前完成，四个时间点严格嵌套。仅比较完成时间也可能来自不同 DFS 树或无祖先关系的交叉边。
- 如果不在递归返回前递增计时器，而只记录“最后检查到一条邻接记录的时刻”，孤立顶点和叶子的完成时间应如何定义？括号化定理还能直接使用吗？
查看参考答案
孤立顶点和叶子可能没有“最后一条邻接记录”，完成时间会缺失或与发现时间混淆；没有统一的退出时间就无法形成成对括号，括号化定理不能直接使用。