题目来源：课程经典显式栈 DFS 练习，没有直接对应的 LeetCode 原题。本 Lab 特别要求用“顶点 + 下一个邻居下标”的栈帧严格模拟递归，而不是只保证访问到相同的顶点集合。
学习目标
前置知识
完成前建议先阅读第 7.1 节 图的遍历：DFS 与 BFS的"显式栈实现"小节。你需要准备支持 C++17 的编译器；可先运行 make doctor 检查环境。
题目
给定一个无向图和起点 s，不用递归，从 s 开始执行 DFS，并输出顶点的发现顺序。结果必须与“邻居按编号升序访问”的递归 DFS 完全一致；只需遍历从 s 可达的顶点，不要为其他连通分量重新启动 DFS。
输入格式
第一行包含三个整数 n m s，分别表示顶点数、无向边数和 DFS 起点。顶点编号为 0 到 n-1。
接下来 m 行，每行包含两个整数 u v，表示一条无向边。输入保证：
1 <= n <= 1000000；0 <= m <= 1000000；0 <= s, u, v < n；- 不包含自环和重复边；
- 图不保证连通，也不保证从
s能到达全部顶点。
为保证结果唯一，每个顶点的邻居必须按编号升序排序；显式栈必须保存“顶点 + 下一个邻居下标”的递归帧，逐个处理邻居，使访问顺序与递归 DFS 的升序访问一致。
输出格式
输出一行，包含从起点 s 出发能访问到的所有顶点，按首次进入顶点的 DFS 发现顺序排列，顶点间用单个空格隔开，行末无空格。不可达顶点不输出。
样例输入
5 4 0
1 3
0 1
1 4
0 2样例输出
0 1 3 4 2任务
- 读入无向图，构建邻接表并升序排序；
- 用显式栈保存
(顶点, 下一个邻居下标)，起点入栈时立即标记并访问； - 每次只推进当前帧的一个升序邻居，发现新顶点后压入新帧；邻居处理完毕后弹出当前帧；
- 栈空时结束，输出访问顺序。
两个必须
- 发现时标记：否则同一顶点可能被多个邻居重复压栈，额外入栈次数可达
O(m)，在稠密简单图中即为O(n²)； - 递归帧：一次只处理一个邻居，避免“批量入栈”改变 DFS 回溯顺序。
内存建议
深图（如 n = 10^6 的链）上，建议用保存 Frame 的 std::vector<Frame> 作为栈并先 reserve(n)；递归实现会直接栈溢出，本题必须使用显式栈。
正常、边界与错误情况
| 情况 | 预期行为 |
|---|---|
| 一般连通图 | 访问顺序与递归升序 DFS 一致 |
| 百万级长链 | 显式栈正常完成，递归实现会爆栈 |
| 星形图 | 帧栈峰值约为 2，验证逐邻居推进 |
| 单顶点图 | 只输出起点 |
| 非连通图 | 只输出从 s 可达的顶点，不可达顶点不输出 |
| 含环图 | 入栈时标记阻止重复入栈 |
运行与评分
在本 Lab 目录执行：
make doctor
make run
make run CASE=001-sample
make score未安装 Make 时，在仓库根目录执行：
pnpm lab:doctor -- labs/chapter-07/exercise/E-07-05-iterative-dfs
pnpm lab:run -- labs/chapter-07/exercise/E-07-05-iterative-dfs
pnpm lab:score -- labs/chapter-07/exercise/E-07-05-iterative-dfs完成清单
复杂度分析
为了固定访问顺序，排序全部邻接表需要 O(Σ deg(u) log deg(u)) 时间，上界可写为 O(m log n)。排序完成后，每个可达顶点恰好入栈、出栈一次；邻接表中的每条相关记录扫描一次，也就是每条可达无向边最多扫描两个方向，DFS 本身为 O(n + m)。因此包含排序的总时间为 O(n + m log n)。
显式栈、visited 与邻接表共占 O(n + m) 空间。显式栈把系统递归栈换成了堆上自行管理的容器，不再受系统调用栈深度限制，但仍受可用内存限制。
思考与复盘
- 如果不保存“下一个邻居下标”，而是一次性处理全部邻居，会怎样影响交叉边场景的访问顺序？
查看参考答案
一次性压入全部邻居会改变邻接顺序和回溯时机，导致访问序列与递归 DFS 不一致；保存下标才能逐个模拟递归帧。
- 链状图上 BFS 队列只有
O(1)大小，为什么这里仍强调 DFS 的显式栈？
查看参考答案
这里讨论的是 DFS 的递归深度，而不是 BFS 队列。链上递归深度为 O(n)，显式栈把帧放到堆上管理，避免系统调用栈限制。
- 若图是一棵有
10^6个节点的树，递归 DFS 会发生什么？显式栈的空间是O(n)还是O(树高)？
查看参考答案
百万级链状树通常会使递归栈溢出。显式帧栈峰值是当前路径长度 O(树高)，最坏树高为 n，所以最坏仍为 O(n)；邻接表另占 O(n+m)。