A factory has several machines that need to be started. Some machines can start only after specific other machines are already running.

Determine whether every machine can be started while satisfying all startup requirements.

Class

FactoryStartupPlanner

Method

canStartAllMachines

boolean canStartAllMachines( int machineCount, List<String> startupRequirements )

Parameters

• machineCount: The number of machines. Machines are numbered from 0 to machineCount - 1.
• startupRequirements: Each element has the format "machine,requiredMachine", meaning that requiredMachine must be running before machine can start.

Returns

Return true if all machines can be started. Return false if the startup requirements make this impossible.

Requirement Format

• Each element of startupRequirements has the format "machine,requiredMachine".
• For example, "4,2" means machine 2 must be running before machine 4 can start.

Startup Rules

• Initially, no machine is running.
• A machine can start after all machines it requires are running.
• A machine without any startup requirement can start immediately.
• Once started, a machine remains running.
• Machines may be started in any valid order.

Constraints

• 1 ≤ machineCount ≤ 2,000
• 0 ≤ startupRequirements.size() ≤ 5,000
• Each startup requirement contains exactly two machine numbers separated by one comma.
• 0 ≤ machine < machineCount
• 0 ≤ requiredMachine < machineCount
• Every startup requirement pair is unique.
• Requirement strings contain only digits and one comma, with no spaces.
• No parameter contains a null value.

Examples

Example 1

canStartAllMachines( machineCount = 6, startupRequirements = ["2,0", "2,1", "3,2", "5,4"] )

Output: true

Machines 0, 1, and 4 can start first. This allows the remaining machines to start afterward.

Example 2

canStartAllMachines( machineCount = 5, startupRequirements = ["1,0", "3,1", "0,3", "4,2"] )

Output: false

Machines 0, 1, and 3 wait for one another in a circular chain, so they cannot be started.

Example 3

canStartAllMachines( machineCount = 3, startupRequirements = [] )

Output: true

None of the machines has a startup requirement, so every machine can start immediately.

Example 4

canStartAllMachines( machineCount = 7, startupRequirements = [ "1,0", "2,0", "4,3", "5,3", "6,4", "6,5" ] )

Output: true

The requirements form separate startup groups without any circular dependency, so all seven machines can eventually start.