Recompute Dependent Cells on Change

Problem
A spreadsheet's cells can reference other cells in their formulas. When one cell's value changes, recompute exactly the cells that transitively depend on it — in an order that respects dependencies, and each affected cell only once. Cells that don't depend on the change must not be recomputed.

Input / Output

• Input: the dependency graph of cells and the id of the changed cell.
• Output: the updated values of the affected cells.

Constraints

• Avoid recomputing unaffected cells.
• Formulas form a DAG; a dependency cycle is an error to detect.

Example

• If C = A + B and D = C * 2, changing B recomputes C then D, in that order.