Problem
You are given a directed graph of app components. Each node represents a component, and each directed edge u -> v means component v depends on updates from component u. When a component receives a new event, that event must be propagated to all reachable components in dependency order: a component can only process an event after all of its direct prerequisites for that event have been processed.
Implement a function that returns the order in which components process a single event starting from one or more source nodes. If multiple components are ready at the same time, process the component with the smaller node id first. Ignore duplicate events for the same component within the same propagation run.
Constraints
- 1 <= n <= 10^5
- 0 <= len(edges) <= 2 * 10^5
- 0 <= u, v < n
- The graph may contain duplicate edges
- sources contains at least one node
- The graph is guaranteed to be acyclic
Function Signature
def propagate_updates(n, edges, sources):
You are practicing as a guest. Sign up free to run your code against the sample data. Your draft stays right here.