← 返回 roblox 的题目列表Build Order with Missing and Circular Dependencies
类型:online_judge
Problem Description
You are given a list of dependency declarations declarations. Each declaration is a list of strings:
The first element is a component name, i.e. a node.
The remaining elements are the components it depends on. Those dependencies must be built before this component.
Return a valid build order such that every component appears after all of its dependencies.
The build process is level-based:
At each step, all components whose dependencies have already been satisfied become buildable at the same time.
Within the same level, output components in the order their declarations appear in the input as the first element.
The final answer is the concatenation of all levels.
Return ["Error"] if either of the following occurs:
Missing dependency: a component is listed as a dependency but is never declared as the first element of any declaration.
Circular dependency: the dependency graph contains a cycle, so no valid build order exists.
You may assume:
declarations is a non-empty 2D string array.
Each declaration contains at least one string.
Component names are non-empty strings.
In valid input, each component is declared at most once. If a component is declared multiple times as the first element, it may be treated as an error.
1 <= declarations.length <= 10^5.
The total number of strings across all declarations is at most 2 * 10^5.
Input Format
Standard input contains a JSON 2D string array, for example:
[["hair", "head"], ["torso"], ["leg", "torso"], ["head"]]
Output Format
Print a JSON string array.
If an error exists, print:
["Error"]
Example 1
Input:
[["head"], ["torso"], ["leg"]]
Output:
["head", "torso", "leg"]
Example 2
Input:
[["head", "leg"], ["leg", "head"]]
Output:
["Error"]
Explanation: head depends on leg, and leg depends on head, so there is a cycle.
Example 3
Input:
[["head"], ["leg", "torso"]]
Output:
["Error"]
Explanation: torso is used as a dependency but is never declared.
Example 4
Input:
[["hair", "head"], ["torso"], ["leg", "torso"], ["head"]]
Output:
["torso", "head", "hair", "leg"]
Explanation: The first buildable level is torso and head, ordered by declaration order. The second level is hair and leg, also ordered by declaration order.
Example
Input
[["head"], ["torso"], ["leg"]]
Output
["head", "torso", "leg"]