题目重点：用活跃递归栈和未访问邻居条件检验发现顺序；若题目给固定邻接顺序，还须按固定顺序模拟。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版是无向图、从 0 访问所有可达点，候选 order 是节点首次发现顺序，邻接访问顺序可以任意选择；不可达节点不应出现在 order。
- 如果原题是‘从 0 到某目标的一条路径’或指定邻接顺序，判定规则不同；没有选项不能回答原选择题编号。
解题路线
- 先用独立可达性搜索核对候选集合正好等于 0 可达节点且无重复、首项为 0。
- 维护 DFS 尚未完成的 stack 和已发现 seen。下一个候选节点若是栈顶邻居，可访问并压栈；否则只有当栈顶不存在任何未访问邻居时才允许弹出回溯。
- 若栈顶仍有未访问邻居却想跳到远处节点，候选顺序不可能由标准 DFS 生成；弹到空栈仍无法抵达候选，也无效。
- 对 n≤4 的无向图枚举每个节点所有邻接顺序，独立递归 DFS 生成真实可能序列，与判定器对照 1,589 个图/序列组合。
手动走一遍
图 0–1、0–2、1–3，顺序 [0,1,3,2] 合法：从 1 访问 3，3 完成后回溯 1、0 再到 2。[0,1,2,3] 不合法：到 1 时未访问邻居 3，不能先弹回 0 去 2。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def valid_dfs_discovery_order(graph: dict[int, set[int]], order: list[int]) -> bool:
"""Training contract: undirected graph, start 0, arbitrary neighbor order."""
if not order or order[0] != 0 or len(order) != len(set(order)):
return False
reachable = {0}
pending = [0]
while pending:
node = pending.pop()
for neighbor in graph.get(node, set()):
if neighbor not in reachable:
reachable.add(neighbor)
pending.append(neighbor)
if set(order) != reachable:
return False
seen = {0}
stack = [0]
for node in order[1:]:
while stack and node not in graph.get(stack[-1], set()):
if any(neighbor not in seen for neighbor in graph.get(stack[-1], set())):
return False
stack.pop()
if not stack:
return False
seen.add(node)
stack.append(node)
return True
复杂度
训练实现先查可达 O(V+E)；逐节点检查回溯时朴素扫描邻居最坏 O(VE)，若维护各节点未访问邻居计数可改为 O(V+E)。栈/seen O(V)。原选择题图很小，正确性优先。
易错点与追问
容易失分的边界
- 把 DFS 首次发现顺序误作从首到尾每对节点都必须有边的路径。
- 栈顶还有未访问邻居却提前回溯。
- 只看图是否连通，不看具体候选顺序。
- 忽略邻接顺序是否在原题固定。
继续深挖
- 若邻接表指定从小到大访问，验证如何简化？
- DFS 完成时间序列与发现序列有何不同？
- 有向图时可达性与回溯规则如何改变？
- 如何将验证降到 O(V+E)？
