A small build tool keeps a dependency map: deps[target] is the list of things target is built from (its inputs). Inputs can be other targets or plain source files; a source file simply never appears as a key. The map has no cycles.
Some files were just edited. Every edited item must be rebuilt (or re-read), and so must everything that directly or indirectly uses one of them. Nothing else is touched.
Implement rebuild_order(deps: dict[str, list[str]], changed: list[str]) -> list[str]:
- Return every affected name exactly once: the changed names plus everything that transitively depends on them.
- Order them so that each name comes after all of its inputs that are also in the list.
- Any order that satisfies this is accepted.
deps = {
"app": ["lib", "ui"],
"lib": ["util.c", "math.c"],
"ui": ["theme.css"],
"tests": ["lib"],
}
rebuild_order(deps, ["math.c"])
# ["math.c", "lib", "app", "tests"] ("tests" before "app" is fine too; "ui" is untouched)
rebuild_order(deps, ["theme.css", "util.c"])
# e.g. ["theme.css", "util.c", "ui", "lib", "app", "tests"]
Constraints: up to 10^5 names and 2 * 10^5 dependency links in total; changed may repeat a name or name something nobody depends on. Chains can be 10^5 long, so avoid recursion, and don't rescan the whole list of targets every time you place one.
Show hint
reverse the edges (input -> users), collect the affected set with a BFS from the changed names, then run Kahn's algorithm counting only in-edges that come from inside the affected set.