Service Startup Planner

SnowflakePhone screenMedium

You are planning the startup of n services numbered 0 to n - 1. A service can only start after every service it requires has started. ServiceGraph(n) begins with no requirements; requirements are added one at a time, and the plan is queried as calls arrive.

Part 1: Startup order

Implement add_dependency and start_order.

add_dependency(service, requires) records that service can only start after requires has started, and returns True. If the requirement would make the plan impossible — a cycle, including service == requires — nothing is recorded and it returns False. Recording the same requirement twice returns True.

start_order() returns every service in the order they start: repeatedly start the smallest-numbered service whose requirements have all started. Services with no requirements are included.

Example 1
init
[5]
operations
[["add_dependency",[0,3]],["add_dependency",[3,0]],["add_dependency",[4,2]],["add_dependency",[0,3]],["start_order",[]]]
Output
[true,false,true,true,[1,2,3,0,4]]
Why: The edge 3 requires 0 would close a cycle with 0 requires 3, so it is rejected; the repeated 0 requires 3 is accepted. Services 1, 2 and 3 are ready first: 1 starts, then 2, then 3, which unblocks 0. Service 4 (waiting on 2) is also ready, but 0 is smaller, giving [1, 2, 3, 0, 4].

Constraints

1 <= n <= 10^3
0 <= service < n
0 <= requires < n
1 <= len(operations) <= 10^3