题目重点：Senior coding 题目说某 cache entry 变化要更新相关依赖项，提 BFS/DFS；用边方向、受影响集合和拓扑重算拆解歧义。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版 A dependsOn B 表示 B 变化可能影响 A；维护 reverseEdges[B]→{A}，从变化的 B 沿 dependent 边找受影响项。
- 若只是标脏/invalidate，图可含环，visited 防重复；若要按依赖顺序重算，训练版要求相关子图为 DAG 或定义 SCC 固定点策略。
- 返回/输出受影响 cache keys 的稳定顺序，题目未明确，训练版按输入顺序 tie-break。
解题路线
- 先把依赖方向画一条例边：priceSummary 依赖 nightlyPrice；nightlyPrice 改变时应更新 priceSummary，而非再沿 nightlyPrice 的原始依赖向下。
- 为每个 dependency 建反向邻接表；值变化时从源 BFS/DFS 收集受影响集合并 visited 去重。
- 若只 invalidate，收集后统一标脏并让后续读取重算；若立即 recompute，在受影响子图按 dependency→dependent 的拓扑序执行，保证每个节点读到已更新上游。
- 检测环：环内如果重算函数依赖彼此，单次拓扑不可行；可拒绝环、将 SCC 作为整体迭代至收敛，或改为懒失效，具体按接口要求。
- 批量变更多个源时先合并受影响集合，避免重复更新；测试菱形依赖、孤立节点、环和无依赖源。
手动走一遍
训练图 A→B、A→C、B→D、C→D（箭头表示上游变化传到 dependent）：A 改变后 BFS 找 {B,C,D}，D 只处理一次。立即重算须先 B/C 后 D；仅 BFS 访问顺序不能自动保证所有依赖已就绪。
规模与取舍
建立反向边 O(V+E)；一次传播 O(Va+Ea)，Va/Ea 为受影响子图，额外 visited O(Va)；若多源频繁更新，可批处理并缓存版本。
易错点与追问
容易失分的边界
- 把 dependency 与 dependent 边画反。
- 没有 visited，在环或菱形图重复/无限更新。
- 遍历找到受影响集合后按任意 BFS 顺序重算 D。
- 值未改变仍无条件触发全图重算。
- 在无接口证据时断言一定允许环/一定要求拓扑输出。
继续深挖
- 环形依赖如何定义语义？
- 并发更改两个上游如何合并版本？
- 传播过程中读取缓存怎样保证一致视图？
- 何时用失效而非立即重算？
