There are n microservices numbered from 0 to n - 1. Each microservice may depend on other microservices. A service can start only after all services it depends on have already started.
The system starts services in restart cycles. During one cycle, services are checked from index 0 to index n - 1. If a service is not started yet and all its dependencies are already started, it starts in that same cycle. Otherwise, it is skipped and checked again in the next cycle.
A dependency is considered satisfied if it started in any previous cycle or earlier in the current cycle.
Return the number of cycles needed to start all services using this process. If it is impossible to start every service because of circular dependencies, return -1.
Method Signature
Minimum Restart Cycles
int minimumCycles(int n, List<String> dependencies)
n is the number of microservices.dependencies.size() == ndependencies.get(i) describes the dependencies of service i.- Each string is comma-separated in this format:
"K,dep1,dep2,...".
K is the number of dependencies for service i.- Each
depX is a service index that must start before service i.
- If
K == 0, the string is exactly "0".
- Return the number of cycles required, or
-1 if all services cannot be started.
- dependencies strings contain only digits and commas, with no spaces.
Constraints
1 ≤ n ≤ 100,000dependencies.size() == n0 ≤ K ≤ n - 10 ≤ depX < n- A service will not list itself as a dependency.
- The total number of dependency values across all services is at most
200,000.
- Dependency indices in one string are distinct.
- The output must be deterministic.
Examples
Example 1
minimumCycles(n = 4, dependencies = ["0", "1,0", "1,1", "1,2"])
Output: 1
Explanation: Service 0 starts first, then service 1, then service 2, then service 3, all during the same cycle because services are checked in increasing index order.
Example 2
minimumCycles(n = 4, dependencies = ["1,1", "0", "1,3", "0"])
Output: 2
Explanation: In cycle 1, services 1 and 3 start. Services 0 and 2 were checked before their dependencies started, so they start in cycle 2.
Example 3
minimumCycles(n = 3, dependencies = ["1,2", "1,0", "1,1"])
Output: -1
Explanation: The services form a dependency cycle, so no service in the cycle can be started.