题目重点：新边source→target前检查target可达source，解释输入DAG前提与原子更新。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 描述键入items edge、validate嵌入、directional graph和不形成Infinite loop；本文将核心规范为DAG插入边防环，原节点schema/判题接口未知。
- 输入图已是DAG，插入source→target；合法重复边幂等成功，新节点可创建，自环拒绝；正式政策未公开，均为训练合同。
- 单线程可变邻接字典；并发与事务另外讨论，代码不自称具备数据库线程安全。
解题路线
- 已有DAG加一条边若产生环，环一定包含新边；因此必须已有target→…→source路径。反之若该路径存在，加source→target闭合成环。先从target做可达搜索即可，没必要每次求所有拓扑排列。
- 先查重复边：已存在且输入DAG，则不改变任何东西，返回true。自环source==target会在初始栈target就命中source并拒绝；未知节点不存在返回路径时可成功插入。
- 搜索以visited防重复；所有检查完成后再改变graph。不能先加边后忘记失败时rollback，否则下一次查询基于污染状态。缺target仅作为无出边节点查，不在检查阶段偷偷插入空节点。
- “没有Infinite loop”不是只保证自己的BFS结束：visited能让任意含环输入搜索结束，但并不证明图本来无环。若原输入未保证DAG，需先全图校验或维护可信不变量。
- 并发两个插入可能各自看到旧快照都通过，合并后成环。需要同一锁/串行事务，或图版本CAS失败重试；数据库事务隔离级别应覆盖跨边依赖，简单atomic counter不能证明DAG完整性。
- 很多插入可维护拓扑编号，顺序方向正确时快速通过，逆序才在受影响区搜索/重排；不能不重排就永久用旧编号拒绝所有逆序合法边。附代码为正确基线，独立参考枚举节点排列判是否存在完整拓扑序。
手动走一遍
已有a→b,b→c，插c→a时从a可达c，拒绝且图不变；插a→c合法。已有a→b和c→d时插d→a合法，没有a→d路径。并发原空图中a→b与b→a各自读取旧图都通过，说明检查+更新必须有一致性合同。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def insert_if_acyclic(graph, source, target):
"""Input graph is already a DAG; graph maps nodes to sets of out-neighbors."""
if target in graph.get(source, ()):
return True
stack = [target]
seen = set()
while stack:
node = stack.pop()
if node == source:
return False
if node not in seen:
seen.add(node)
stack.extend(graph.get(node, ()))
# Change state only after the reachability check succeeds.
graph.setdefault(source, set()).add(target)
graph.setdefault(target, set())
return True
复杂度
单次搜索O(V+E)最坏、O(V)visited；若重复边O(1)期望检查。M次基线O(M(V+E))，维护动态图拓扑的代价依受影响范围/实现，不许以BFS为由宣称常量插入。
易错点与追问
容易失分的边界
- 搜索source→target方向反了。
- 先修改后失败不回滚。
- 输入含环仍声称验证新图DAG。
- visited保证结束当防环证明。
- 并发只保护插入那一行。
继续深挖
- 原图不保证DAG怎样先验证？
- 怎样返回造成环的见证路径？
- 拓扑顺序维护怎样减少搜索？
- 数据库事务怎样避免write skew？
